Centrality scaling in large networks

Mária Ercsey-Ravasz & Zoltán Toroczkai
Physical review letters 105.3 (2010): 038701
Publication Date: 
July, 2010

Betweenness centrality lies at the core of both transport and structural vulnerability properties of complex networks; however, it is computationally costly, and its measurement for networks with millions of nodes is nearly impossible. By introducing a multiscale decomposition of shortest paths, we show that the contributions to betweenness coming from geodesics not longer than L obey a characteristic scaling versus L, which can be used to predict the distribution of the full centralities. The method is also illustrated on a real-world social network of 5.5×106 nodes and 2.7×107 links.