我有一个包含 300000 个节点和 800000 个边的网络。 R中的igraph包计算每个节点的网络中心性度量(包括接近度和介数)需要多长时间。
最佳答案
介数和接近度的运行时间都是二次方的，因此随着节点数量的增加而大幅增加。 These authors计算具有 325,000 条边的图的介数估计需要 7,000 秒。具有 800,000 条边的图将花费更长的时间。
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 Air 上。随着截止值的增加，运行时间也会增加。
当然，权衡是您需要估计每个节点的介数分数，而不是直接计算。
引用:
Kang, U.、Papadimitriou, S.、Sun, J. 和 Tong, H.(2011 年 4 月)。大型网络的中心性:算法和观察。 2011 年 SIAM 国际数据挖掘 session 论文集(第 119-130 页)。工业与应用数学学会。 Link
关于r - igraph r 估计大型网络的网络中心性度量需要多长时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41753929/