如何在使用模块 NetworkX 时粗略估计计算时间

Question

你好我正在处理一个有点大（抱歉用词不明确）图，它有29,981个节点和150,000 个有向边 在里面。

我正在使用模块 networkx 处理它，该模块现在在图论学家中使用得相当广泛。

今天早上我在 Jupyter 中执行了以下脚本，但无法估计何时完成：

import netowkx as nx
import pickle

# to read the graph
with open ('/home/zachary/H{}'.format("29981"), 'rb') as fp:
    H = pickle.load(fp)     

print(list(nx.simple_cycles(H)))

如何大致猜出这个脚本的完成时间？

我有点知道big O和small O的..但是通常这种理论知识在我的脑海中还没有成熟到工业上使用这些知识来计算和估计计算时间。

Answer 1

如 NetworkX documentation 中所述，simple_cycles 使用 Johnson 算法查找基本循环。算法的复杂度为 O((V+E).(1+C)) 其中

V为顶点数；
E为边数；
C循环次数。

在您的情况 V+E ~= 150,000 中，假设 python 进程未超载，我们可以预期运行宁时间为 150,000.K.C.

要尝试找到 K 的估计值，您可以运行较小图形上的算法，使用 10 (V+E = 10, 100, 1000 ...) 的幂来确保运行 simple_cycles 的 ning 时间与 (V+E)(1+C) 成正比，得到 K 的粗略值，并根据您期望的周期数估计图表的运行ning 时间寻找。更准确地说，如果我们记下 R(V+E,C) 每个实验较小图的实际运行宁时间，以及 C0, C1, ...Cn 它们各自的周期数，那么我们期望有

R(100,C1)  / R(10,C0)  ~= 10.K.[(1+C1) / (1+C0)]
R(1000,C1) / R(100,C0) ~= 10.K.[(1+C2) / (1+C1)]
...

如果 simple_cycles 运行ning 时间没有表现出 Johnson 算法的复杂性，那么有一个 non-algorithmic 因素正在减慢 down/preventing 计算 - 这个然后需要进行调查。

Follow-up 这些是使用您提供的图表进行的一些调查的结果。我尝试使用 NetworkX 库计算较小子图的循环数，并在下面重现了一些有趣的结果。每个子图都有节点和边的数量以及计算的循环数。

\#Nodes  | \#Edges | \#Cycles (computed)
----------------------------------------
   1,000 |     186 |                17
   2,000 |     675 |                37
   3,000 |   1,460 |                72
   4,000 |   2,538 |             2,147   
   4,250 |   2,881 |         2,351,883

我在 #Nodes = 4000 停了下来，几分钟内我无法得到任何结果。

让我们为这些值中的每一个计算值

log10(C)/E with C = \#Cycles and E = \#Edges.

E = \#Edges | C = \#Cycles (computed) |  log(C)/E  | 
----------------------------------------------------
        186 |                      17 |     0.0067 |
        675 |                      37 |     0.0023 |
      1,460 |                      72 |     0.0013 |
      2,538 |                   2,147 |     0,0013 |
      2,881 |               2,351,883 |     0,0022 |

正如我们所见，至少对于 G 的边小于 ~2,500 的子图，循环数大致遵循以下幂律

log10(C) = 0.0013.E => C = 1.003^E

经验值 1.003 来自您图表的拓扑结构（作为旁注，maximum theoretical number of cycles given the number of edges 估计为 1.443^E。）。

请注意，我们不知道这个常量是否随着图表变大而保持不变 - 这将是一件有趣的事情来检查，但使用与 brute-force 不同的方法（我们已经有当我们达到 5000 个边缘时，十亿个循环中的一千个）。

在这种情况下（并且仅在这种情况下）常数不会随着图形变大到 G 的 150,000 条边而改变，大约循环数将是... ~10^359

=> 看来您实际上遇到了算法复杂性的瓶颈。考虑到这一点，我不知道您希望选择哪种替代方案来继续前进 - 也许存在 non-exponential 近似算法？

备注
为了试验 G 的子图，我使用了以下命令 - 指定目标节点数，例如 3,000 个节点：

 H = G.copy()
 H.remove_nodes_from(list(nodes)[3000:])
 len(list(nx.simple_cycles(H)))

如何在使用模块 NetworkX 时粗略估计计算时间

How to Estimate Roughly The Computation Time While Using Module NetworkX

python

scalability

time-complexity

networkx