使用图工具计算 (1M,3M)-图上的介数中心性
Compute betweenness centrality on a (1M,3M)-graph using graph-tool
我正在尝试计算 1M 节点 3M 边图的介数中心性。 我正在使用图形工具和以下代码行：
from graph_tool.all import *
g = load_graph("youtube.graphml")
scores = graph_tool.centrality.betweenness(g)
在其性能比较页面中，据报道计算 (40k, 300k)-directed_graph 上的介数，图形工具大约需要 4 分钟。 https://graph-tool.skewed.de/performance
由于图形工具使用复杂度为 O(VE) 的 Brandes 算法，我预计的时间约为 运行：
(1M/40k)*(3M/300k)*4m=25*10*4m=1000m~17h
我发现此计算与以下 post 一致，其中对于 (2M,5M)-graph，用户使用 NetworkX 给出了大约 运行 6 个月的时间，比图形工具慢 180 倍。因此：
6 months = 180 days(NetworkX) ~ 1 day(graph-tool)
关键是我的程序 运行 从 2 天开始就在 4 核机器上，所以我开始怀疑我的推理是否有任何意义。
此外，图形工具基准测试是在有向图上执行的，Brandes 算法的复杂度为 O(VE+V(V+E)logV)。鉴于这一点，预期的 运行 时间不应该比之前写的还要小吗？更重要的是 使用图形工具和 4 核机器在 (1M,3M) 网络上计算介数中心性完全可行吗？
我使用的是 Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
最终算法停止:
- 花费的时间比2略多
天（再过几个小时）。
我无法得到结果：
- 在计算过程中
UI 崩溃了，我无法重新连接到 ipython 笔记本
内核是 运行 程序（但是保留了 运行）。
我会在得到实际结果后立即更新此post。
更新
我使用 16 核机器重新计算了介数，大约花了 18 小时。
我正在尝试计算 1M 节点 3M 边图的介数中心性。 我正在使用图形工具和以下代码行：
from graph_tool.all import *
g = load_graph("youtube.graphml")
scores = graph_tool.centrality.betweenness(g)
在其性能比较页面中，据报道计算 (40k, 300k)-directed_graph 上的介数，图形工具大约需要 4 分钟。 https://graph-tool.skewed.de/performance
由于图形工具使用复杂度为 O(VE) 的 Brandes 算法，我预计的时间约为 运行：
(1M/40k)*(3M/300k)*4m=25*10*4m=1000m~17h
我发现此计算与以下
6 months = 180 days(NetworkX) ~ 1 day(graph-tool)
关键是我的程序 运行 从 2 天开始就在 4 核机器上，所以我开始怀疑我的推理是否有任何意义。
此外，图形工具基准测试是在有向图上执行的，Brandes 算法的复杂度为 O(VE+V(V+E)logV)。鉴于这一点，预期的 运行 时间不应该比之前写的还要小吗？更重要的是 使用图形工具和 4 核机器在 (1M,3M) 网络上计算介数中心性完全可行吗？
我使用的是 Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
最终算法停止:
- 花费的时间比2略多 天（再过几个小时）。
我无法得到结果：
- 在计算过程中 UI 崩溃了，我无法重新连接到 ipython 笔记本 内核是 运行 程序（但是保留了 运行）。
我会在得到实际结果后立即更新此post。
更新 我使用 16 核机器重新计算了介数，大约花了 18 小时。