为什么 networkx 在查找直径时说我的有向图已断开连接？

Question

我正在爬取 slideshare.net 图，从我的节点开始，跟踪 BFS 中的所有用户，直到访问的节点数为 1000。我通过以下方式执行 BFS：

from urllib.request import urlopen
from collections import deque
import sys
import json
import codecs
import csv
import io
import hashlib
import time
import xml.etree.ElementTree as etree
queue = deque(["himanshutyagi11"])
while len_visitedset < 1ooo:
        vertex = queue.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        length_visited = len(visited)
        print(vertex,length_visited)
        crawl(vertex)

crawl() 是一个函数，在该函数中我按照说明进行 slideshare api 查询 here 通过使用我的 shared_secret 和 api_key 创建查询负载（给定在 api 注册时），发送查询并解析存储在变量 'response' 中的 XML 响应。解析后，我将当前节点的联系人添加到队列中。

request_timestamp = int(time.time())
request_hash_string = shared_secret+str(request_timestamp)
request_hash_value = hashlib.sha1(request_hash_string.encode('utf-8')).hexdigest()
request_url = 'https://www.slideshare.net/api/2/get_user_contacts?username_for='+username+'&api_key='+api_key+'&hash='+request_hash_value+'&ts='+str(request_timestamp)
response = etree.parse(urlopen(request_url)).getroot()
# Append all the adjacent nodes of this user to the queue.
    for child in response:
        friend_name = child[0].text
        queue.appendleft(friend_name)
edge_file = open('non_anonymized.csv','a')
    for child in response:
        f_name = child[0].text                              # Name of friend is stored in variable 'f_name'
        edge_file.write(username+','+f_name+'\n')          # username is the name of user currently being crawled
    edge_file.close()

在抓取的同时，我还创建了一个 edgelist.csv 文件，其中包含图中的所有边。这个文件好像没问题。还有其他功能，如 degree()、in_degree()、average_clustering() 似乎工作正常。

然后我使用 networkx 创建一个图，它有 1000 个节点。但是如果我尝试使用以下函数找到该图的直径：

diameter = nx.diameter(graph)

使用上面的代码，我无法找到我的图形的直径，这没有 return 任何东西，我的程序卡在这一行。对可能发生的事情有任何见解吗？我的是一个连通图。我正在使用 to_undirected() 函数将其转换为无向的。我用有向图累了运行它，我得到了以下错误
networkx.exception.NetworkXError: Graph not connected: infinite path length

我的问题是，我用的是BFS爬虫，怎么断网呢

Python 3.4
Networkx 1.9.1

Answer 1

直径的源代码是here。它依赖于 eccentricity ，这是源代码中的函数。 eccentricity 找到从一个节点到所有其他节点的最短路径。您收到的错误消息来自这部分代码：

if L != order:
    msg = "Graph not connected: infinite path length"
    raise networkx.NetworkXError(msg)

此处 L 是从给定节点可达的节点数，order 是网络中的节点数。 L != order 表示存在无法从给定节点访问的节点。在无向网络的情况下，这意味着网络未连接。但是，在您的情况下，您有一个定向网络。对于有向网络 L != order 意味着网络不是 "strongly-connected"。它实际上可能是弱连接，你的大概是。

所以您遇到了一条不太准确的错误消息。

对于您创建的有向网络，直径是无限大的：如果有一个节点 u 没有到 v 的路径，这意味着一个无限大的直径。

Answer 2

我来晚了，但遇到了同样的问题，估计其他人可能也会遇到。

Joel 已经解释了问题的根源。直径函数依赖于强连接的网络。

对于弱连通图，可以使用：diameter = nx.diameter(net.to_undirected())

Answer 3

您无法计算 1) 弱连通有向图或 2) 不连通图的直径，但您可以像这样使用最大最短路径：

diameter = max([max(j.values()) for (i,j) in nx.shortest_path_length(G)])

这会找到包含 G 中任意两个节点之间最短路径的列表的最大距离（使用 Dijkstra 算法计算），而不管它们属于哪个组件。从技术上讲，断开连接的图形的直径是无限的，这就是 NetworkX 的内置方法不起作用的原因。上面的方法会找出G内所有分量中最大的直径，但不是G本身的直径

为什么 networkx 在查找直径时说我的有向图已断开连接？

Why does networkx say my directed graph is disconnected when finding diameter?

python

networkx

network-analysis