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

Question

我正在使用常规 NxN 网络，我需要确定其稳健性的衡量标准(即承受故障的能力)。为此，我使用了 average node connectivity ，由 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

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

(无耻的插件:因为你正在处理具有单位容量的平面图，如果你急于求成，你可以实现我和 Philip Klein 的线性时间最大流量算法，但我希望通常的算法是在实践中大致是线性时间。)