标题： 有限范围的中心性度量在复杂网络中 显示英文标题

标题： Range-limited Centrality Measures in Complex Networks

摘要： 此处我们提出一种范围受限的方法，用于无权重和有权重的有向复杂网络中的中心性度量。 我们引入了一种高效的方法，该方法基于长度不超过$\ell = 1,...,L$的最短路径，为每个节点和每条边生成其介数中心性；在无权重网络中，对于有权重网络，相应的量则基于路径权重不超过$w_{\ell}=\ell \Delta$、$\ell=1,2...,L=R/\Delta$的最小权重路径。 这些度量提供了对节点（边）相对于其网络邻域1步、2步等的位置重要性的系统描述，直至整个网络。 我们展示了范围受限的中心性在大型无权重网络中遵循普遍的标度定律。 由于传统中心性度量的计算成本较高，这种标度行为可以被利用来高效估计所有范围内的节点和边的中心性，包括传统的中心性。 这种标度行为还可以被用来证明，基于其范围受限中心性的节点（边）排名前列表会随着范围的变化而迅速冻结，因此可以高效预测直径范围的排名前列表。 我们还展示了如何利用上述标度行为来估计包含$N$个节点的网络中的典型最大节点间距离。 这些观察结果在模型网络和一个从手机通话记录日志推断出的大规模社交网络（$\sim 5.5\times 10^6$个节点和$\sim 2.7\times 10^7$条边）中得到了说明。 最后，我们将这些概念应用于高效检测网络的脆弱性骨干（定义为最高介数节点和边的最小渗透簇），并说明了基于权重的中心性度量在检测此类骨干中的重要性。 显示英文摘要

摘要： Here we present a range-limited approach to centrality measures in both non-weighted 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 $\ell = 1,...,L$ in case of non-weighted networks, and for weighted networks the corresponding quantities based on minimum weight paths with path weights not larger than $w_{\ell}=\ell \Delta$, $\ell=1,2...,L=R/\Delta$. These measures provide a systematic description on the positioning importance of a node (edge) with respect to its network neighborhoods 1-step out, 2-steps out, etc. up to including the whole network. We show that range-limited centralities obey universal scaling laws for large non-weighted 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 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 aforementioned scaling behavior. These observations are illustrated on model networks and on a large social network inferred from cell-phone trace logs ($\sim 5.5\times 10^6$ nodes and $\sim 2.7\times 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.