用图形工具计算(1M,3M)-graph上的中间度

Question

我试图计算1M节点3M边图上的中间度。我正在使用图形工具和下面的代码行：

from graph_tool.all import *
g = load_graph("youtube.graphml")
scores = graph_tool.centrality.betweenness(g)

在性能比较页面中，据报道，要在(40k，300 k)-directed_graph上计算中间度，图形工具大约需要4分钟。https://graph-tool.skewed.de/performance

由于图形工具使用了具有O(VE)复杂度的Brandes算法，因此我预期的估计运行时间为：

(1M/40k)*(3M/300k)*4m=25*10*4m=1000m~17h 

我发现这个计算与下面的stack帖子是一致的，其中对于一个(2m，5米)的-graph，用户使用NetworkX给出了大约6个月的运行时间，这比图形工具的x180慢。因此：

6 months = 180 days(NetworkX) ~ 1 day(graph-tool)

关键是我的程序从两天开始运行在一台4核机器上，所以我开始怀疑我的推理是否有意义。

此外，在有向图上执行图形工具基准测试，而Brandes算法具有O(VE+V(V+E)logV)的复杂性。考虑到这一点，预期的运行时间不应该比以前编写的更短吗？更重要的是，使用图形工具和四核机器计算(1M,3M)-network上的中心度是否可行？

我使用的是Intel(R) Core(TM) i7-6700HQCPU@ 2.60GHz

Answer 1

• 最后，算法停止了

- It took slightly more than **2 days** (a couple of hours more). 

​

• 我当时无法得到结果，：

- During the computation the UI crashed and I was not able to reconnect to the ipython notebook kernel which was running the program (which however kept running).

​

• 一旦我得到实际结果，我就会更新这篇文章。

UPDATE --我用一台16核机器重新计算了之间的距离，用了大约18小时。