Python：如何在网络上计算快速稳健度量？

Question

我正在使用一个常规的 NxN 网络，并且需要确定其强韧性（即抵御故障的能力）的度量。为此，我正在使用平均节点连通性，该指标由此函数描述。

然而，如下所示，这个计算过程非常缓慢且计算需求量大。我应该运行下面的脚本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

- FaCoffee

---

在这个上下文中，“健壮性”对您意味着什么？ - Joel

能够承受故障。 - FaCoffee

所以我假设David提供的是你想要的内容 - 但你应该知道，可能会发生许多不同的“故障”。根据你的理解，这可能是或不是正确的计算量。我们可能在谈论节点失败。我们可能在谈论边缘失败。承受故障可能意味着整个网络仍然保持连接，或者只是大部分网络保持连接，或者可能意味着路径长度不会变长...等等。 - Joel

Answer 1

那个NetworkX函数需要使用有向图，因此它正在使用计算V *（V-1）流的暴力算法。由于您有一个无向图，因此可以使用V-1流来计算Gomory--Hu tree，然后使用树结构快速确定最小割（实际上，您可以在线性或者可能是线性对数时间内从G-H树中计算平均节点连通性，但我认为二次方时间可能会足够）。 （自吹自擂：由于您正在处理具有单位容量的平面图，如果您迫切需要速度，您可以实现我的和Philip Klein的线性时间最大流算法，但我希望通常算法在实践中大致为线性时间。）

- David Eisenstat

---

这里有一个真正熟悉这个问题的人。非常好的答案！我不会删除我的回答，但这个更加详细。 - benbo

Answer 2

这里计算的平均节点连接度是G中所有节点对的局部节点连接度的平均值。因此，该函数将遍历所有可能的节点对，这使得它非常缓慢。一个建议是保持网络大小不变，然后从所有可能的节点对中随机抽样，并基于该样本计算连接度估计。

- benbo