NetworkX平均最短路径长度和直径需要永远

Question

我有一个由未加权边构建的图（a），我想计算主图（a）中最大连通图（giantC）的平均最短路径长度。但是，到目前为止，该脚本已经运行了3个多小时（在Colab和本地进行了尝试），对于diameter和average\u shortest\u path\u length都没有输出任何结果。

我使用的是networkx==2.5，python==3.6。9

这是我的剧本

import logging
import networkx as nx 
from networkx.algorithms.distance_measures import diameter
from networkx.algorithms.shortest_paths.generic import average_shortest_path_length


# graph is built from a json file as follows 
with open('graph.json') as f:
     graph_dict = json.load(f)

_indices = graph_dict['indices']
s_lst, rs_lst= _indices[0], _indices[1]    

graph_ = nx.Graph()
for i in range(len(s_lst)):
     graph_.add_edge(s_lst[i], rs_lst[i])


# fetch the hugest graph of all graphs
connected_subgraphs = [graph_.subgraph(cc) for cc in 
nx.connected_components(graph_)]
logging.info('connected subgraphs fetched.')
Gcc = max(nx.connected_components(graph_), key=len)
giantC = graph_.subgraph(Gcc)
logging.info('Fetched Giant Subgraph')

n_nodes = giantC.number_of_nodes()
print(f'Number of nodes: {n_nodes}') # output is 106088

avg_shortest_path = average_shortest_path_length(giantC)
print(f'Avg Shortest path len: {avg_shortest_path}')

dia = diameter(giantC)
print(f'Diameter: {dia}')

有没有办法让它更快？或者是计算giantC图的直径和最短路径长度的替代方法？

Answer 1

对于将来的读者，如果您想从NetworkX图形中获取最大的连接子图

import networkx as nx
import logging


def fetch_hugest_subgraph(graph_):
    Gcc = max(nx.connected_components(graph_), key=len)
    giantC = graph_.subgraph(Gcc)
    logging.info('Fetched Giant Subgraph')
    return giantC

如果您想计算图形的平均最短路径长度，我们可以通过采样来实现

from statistics import mean
import networkx as nx


def write_nodes_number_and_shortest_paths(graph_, n_samples=10_000,
                                          output_path='graph_info_output.txt'):
    with open(output_path, encoding='utf-8', mode='w+') as f:
        for component in nx.connected_components(graph_):
            component_ = graph_.subgraph(component)
            nodes = component_.nodes()
            lengths = []
            for _ in range(n_samples):
                n1, n2 = random.choices(list(nodes), k=2)
                length = nx.shortest_path_length(component_, source=n1, target=n2)
                lengths.append(length)
            f.write(f'Nodes num: {len(nodes)}, shortest path mean: {mean(lengths)} \n')

Joris Kinable（在评论中）告诉我，计算avg_shortest_path_length的复杂性为O（V^3）； V=节点数。这同样适用于计算你的重力直径