Range-limited Centrality Measures in Complex Networks

Details Range-limited Centrality Measures in Complex Networks Range-limited Centrality Measures in Complex Networks

2011-11-23

arxiv.org/abs/1111.5382v1

Physics

Physics and Society

14 pages, 8 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Range-limited Centrality Measures in Complex Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Range-limited Centrality Measures in Complex Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Range-limited Centrality Measures in Complex Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-376467