Python：如何计算网络鲁棒性的快速度量？

Question

我正在使用常规 NxN 网络，我需要确定其稳健性的衡量标准（即承受故障的能力）。为此，我使用 average node connectivity, which is described by this function.

但是，事实证明此计算极其缓慢且计算量大，如下所示。我应该运行下面的脚本 60,000 次，所以时间是一个非常关键的因素。为此我愿意缩小网络的规模，但我想在网络规模和计算需求之间找到最佳折衷。

我的问题：

有没有更快的方法得出相同的结果？或者您是否建议采取另一种措施来避免长时间的计算？

脚本和时间：

'''
Timing the average node connectivity function
'''

from __future__ import division
import networkx as nx
import time

#Lattice network
N=10 #This can be 10, 20, 30, ...
G=nx.grid_2d_graph(N,N)
pos = dict( (n, n) for n in G.nodes() )
labels = dict( ((i, j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds.sort()
vals.sort()
pos2=dict(zip(vals,inds))

start_time = time.clock()
conn=nx.average_node_connectivity(G)
print('N: '+str(N))
print('Avg node conn: '+str(round(conn, 3)))
print("--- %s seconds ---" % (time.clock() - start_time))

前两个时间：

N: 10
Avg node conn: 3.328
--- 6.80954619325 seconds --- #This must be multiplied by 60,000

N: 20
Avg node conn: 3.636
--- 531.969059161 seconds --- #This must be multiplied by 60,000

Answer 1

这里计算的平均节点连通性是 G 的所有对节点的本地节点连通性的平均值。所以这个函数将遍历所有可能的对，这使得它很慢.一个建议是根据需要保留网络的大小，然后从所有可能的节点对中随机抽样并根据该样本计算连接估计。

Answer 2

NetworkX 函数必须使用有向字母，因此它使用计算 V*(V-1) 流的强力算法。由于你有一个无向图，你可以改为计算 V-1 流中的 Gomory--Hu tree，然后使用树结构快速确定最小切割（实际上，你可以从 G--H 树计算平均节点连接在线性时间或可能是线性时间，但我希望二次方可能没问题）。

(无耻的插件：因为你正在使用具有单位容量的平面图，如果你对速度不顾一切，你可以实现我和 Philip Klein 的线性时间最大流量算法，但我希望通常的算法在实践中将大致是线性时间。）

Python：如何计算网络鲁棒性的快速度量？

Python: how to compute a fast measure of robustness on a network?

python

algorithm

performance

networkx

computation