Networkx从未完成计算200万个节点的中介中间性

Networkx从未完成计算200万个节点的中介中间性

TL /
DR：中间性中心度是一个非常慢的计算，因此您可能希望使用近似度量，方法是考虑

myk

节点子集，该子集的

myk

数目比网络中的节点数少很多，但又足够大，具有统计意义（
NetworkX为此提供了一个选项：

betweenness_centrality(G, k=myk)

。

---

我很惊讶这花了很长时间。中间性中心是一个缓慢的计算。networkx使用的算法为

O(VE)

，其中

V

顶点数和

E

边数。就你而言

VE =10^13

。我希望导入图形需要花费

O(V+E)

时间，因此，如果花费的时间足够长，您可以知道它不是瞬时的，那

O(VE)

将会很痛苦。

如果具有1％的节点和1％的边缘（即20,000个节点和50,000个边缘）的简化网络将花费时间X，则所需的计算将花费10000X。如果X是一秒钟，那么新的计算将接近3个小时，我认为这是非常乐观的（请参阅下面的测试）。因此，在确定代码有问题之前，请在一些较小的网络上运行它，并估算网络的运行时间。

一个很好的选择是使用近似度量。标准的中介度度量考虑每对节点及其之间的路径。Networkx提供了一种替代方法，该方法使用仅

k

节点的随机样本，然后查找这些

k

节点与网络中所有其他节点之间的最短路径。我认为这应该可以加快运行

O(kE)

速度

所以你会用的是

betweenness_centrality(G, k=k)

如果您想限制结果的准确性，可以用较小的值进行多次调用

k

，确保它们相对接近，然后取平均结果。

---

这是我对运行时间的一些快速测试，随机图为（V，E）=（20,50）; （200,500）；和（2000,5000）

import timefor n in [20,200,2000]:    G=nx.fast_gnp_random_graph(n, 5./n)    current_time = time.time()    a=nx.betweenness_centrality(G)    print time.time()-current_time>0.00247192382812>0.133368968964>15.5196769238

因此，在我的计算机上，处理大小为您的0.1％的网络需要15秒。建立与您的网络大小相同的网络大约需要1500万秒。这是1.5 * 10 ^ 7秒，比pi *10 ^ 7秒的一半还少。因为pi * 10 ^ 7秒非常接近一年中的秒数，所以我的计算机大约要花6个月的时间。

因此，您将需要使用近似算法。