1

我正在抓取 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 查询 ，使用我的 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)

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

我的问题是，由于我使用 BFS 进行爬网，它如何断开连接。

Python 3.4
Networkx 1.9.1

4

3 回答 3

5

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

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

这L是从给定节点可到达的order节点数，是网络中的节点数。 L != order表示存在无法从给定节点到达的节点。在无向网络的情况下，这意味着网络未连接。但是，在您的情况下，您有一个定向网络。对于有向网络L != order意味着网络不是“强连接”的。它实际上可能是弱连接的，而你的可能是。

因此，您遇到了一个不太准确的错误消息。

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

于 2015-10-14T04:12:03.840 回答
3

我迟到了，但遇到了同样的问题，并且认为其他人可能仍然会遇到它。

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

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

于 2018-07-10T22:51:56.740 回答
1

您无法计算 1) 弱连接有向图或 2) 断开连接图的直径，但您可以使用最大最短路径，如下所示：

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

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

于 2021-10-19T19:16:51.423 回答