igraph估计大型网络的网络中心性度量需要多长时间？

Question

我有一个由300000个节点和800000个边组成的网络。对于R中的igraph，计算每个节点的网络中心性(包括封闭度和中间度)需要多长时间。

Answer 1

中间度和贴近度的运行时间都是二次型的，因此随着节点数的增加，运行时间会大幅度增加。这些作者估计，对于有325,000条边的图，估计有7,000秒。一个有80万条边的图形将花费更长的时间。

igraph对大型图确实有特定的函数-- estimate_betweenness和estimate_closeness，手册称它们在运行时不是二次型的。定义一个截止点，这是计算中包含的最大路径长度。传统上，中间性考虑任意长度的路径。定义一个截止点大大减少了运行时：

> lg <- erdos.renyi.game(300000,800000,type="gnm")
> ptm <- proc.time()
> igraph::estimate_betweenness(lg, cutoff = 3)[1:10]
 [1]  29  12  14  90  29  98  69  48 200  86
> proc.time() - ptm
   user  system elapsed 
 27.605   0.327  30.113 

~30秒。这是在双核macbook上播放的。随着截止时间的增加，运行时也会增加。

当然，权衡是，您有一个等于估计每个节点之间的得分，而不是一个直接的计算。

参考资料：

作者声明:张建民(音译)。大型网络的核心:算法和观测。“2011年SIAM国际数据挖掘会议记录”(第119至130页)。工业和应用数学学会。链接