Ercsey-Ravasz Mária, Lichtenwalter Ryan N, Chawla Nitesh V, Toroczkai Zoltán
Faculty of Physics, Babeş-Bolyai University, Kogalniceanu street 1, RO-400084 Cluj-Napoca, Romania.
Phys Rev E Stat Nonlin Soft Matter Phys. 2012 Jun;85(6 Pt 2):066103. doi: 10.1103/PhysRevE.85.066103. Epub 2012 Jun 6.
Here we present a range-limited approach to centrality measures in both nonweighted and weighted directed complex networks. We introduce an efficient method that generates for every node and every edge its betweenness centrality based on shortest paths of lengths not longer than ℓ=1,...,L in the case of nonweighted networks, and for weighted networks the corresponding quantities based on minimum weight paths with path weights not larger than w(ℓ)=ℓΔ, ℓ=1,2...,L=R/Δ. These measures provide a systematic description on the positioning importance of a node (edge) with respect to its network neighborhoods one step out, two steps out, etc., up to and including the whole network. They are more informative than traditional centrality measures, as network transport typically happens on all length scales, from transport to nearest neighbors to the farthest reaches of the network. We show that range-limited centralities obey universal scaling laws for large nonweighted networks. As the computation of traditional centrality measures is costly, this scaling behavior can be exploited to efficiently estimate centralities of nodes and edges for all ranges, including the traditional ones. The scaling behavior can also be exploited to show that the ranking top list of nodes (edges) based on their range-limited centralities quickly freezes as a function of the range, and hence the diameter-range top list can be efficiently predicted. We also show how to estimate the typical largest node-to-node distance for a network of N nodes, exploiting the afore-mentioned scaling behavior. These observations were made on model networks and on a large social network inferred from cell-phone trace logs (∼5.5×10(6) nodes and ∼2.7×10(7) edges). Finally, we apply these concepts to efficiently detect the vulnerability backbone of a network (defined as the smallest percolating cluster of the highest betweenness nodes and edges) and illustrate the importance of weight-based centrality measures in weighted networks in detecting such backbones.
在此，我们提出一种针对非加权和加权有向复杂网络中中心性度量的范围受限方法。我们引入了一种高效方法，对于非加权网络，基于长度不超过(\ell = 1,\ldots,L)的最短路径，为每个节点和每条边生成其介数中心性；对于加权网络，则基于路径权重不大于(w(\ell)=\ell\Delta)（(\ell = 1,2,\ldots,L = R/\Delta)）的最小权重路径生成相应的量。这些度量提供了关于节点（边）相对于其网络邻域在一步之外、两步之外等直至包括整个网络的定位重要性的系统描述。它们比传统中心性度量更具信息性，因为网络传输通常发生在所有长度尺度上，从传输到最近邻到网络的最远端。我们表明，对于大型非加权网络，范围受限的中心性遵循通用标度律。由于传统中心性度量的计算成本高昂，这种标度行为可用于有效估计所有范围内节点和边的中心性，包括传统的中心性。这种标度行为还可用于表明，基于其范围受限中心性的节点（边）排名前列的列表作为范围的函数会迅速冻结，因此直径 - 范围前列列表可以有效地预测。我们还展示了如何利用上述标度行为估计具有(N)个节点的网络中典型的最大节点间距离。这些观察结果是在模型网络以及从手机追踪日志推断出的大型社交网络（约(5.5×10^6)个节点和约(2.7×10^7)条边）上得出的。最后，我们应用这些概念来有效地检测网络的脆弱性骨干（定义为具有最高介数的节点和边的最小渗流簇），并说明基于权重的中心性度量在加权网络中检测此类骨干的重要性。
