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

Question

您好，我正在处理一个大的（抱歉有不明确的术语）图，它有29981个节点，其中有150000个有向边。在

我用模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和{}有点了解。。但通常这种理论知识在我的头脑中还没有成熟到工业上用这些知识来计算和估计计算时间。在

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的运行时间与(V+E)(1+C)成比例，得到一个粗略的值K，并根据预期找到的循环数来估计图的运行时间。更准确地说，如果我们注意到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的运行时间没有表现出Johnson算法的复杂性，那么有一个非算法因素会减慢/阻止计算-这将需要进行研究。在

跟进 这些是用你提供的图表进行调查的结果。我试图用NetworkX库计算较小子图的循环数，并在下面复制了一些有趣的结果。每个子图的节点数和边数以及计算的循环数。在

^{pr2}$

我在#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 |

如我们所见，至少对于小于~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）。在

请注意，我们不知道这个常数是否会随着图形变大而保持不变-这将是一个有趣的检查，但使用的方法不同于这个强力方法（当我们达到5000条边时，我们已经有了十亿分之一的周期）。在

在这种情况下（而且仅在这种情况下）常数不会随着图形的增大而改变，直到G的150000条边，循环的近似数量将是。。。~10^359

=>；似乎您实际上遇到了算法复杂度的问题。考虑到这一点，我不知道你希望选择哪一种方法向前推进——也许存在非指数近似算法？在

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

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