Centrality scaling in large networks

 

MARIA ERCSEY-RAVASZ

ICENSA, DEPARTMENT OF PHYSICS, UNIVERSITY OF NOTRE

 

Betweenness centrality is one of the most studied quantities in network research, as it lies at the core of both transport and structural vulnerability properties of complex networks. However, it is computationally expensive, its determination for networks with millions of nodes is near impossible and existing approximation methods are mainly sampling based and ill controlled. Here we introduce a range-limited method that takes into account only geodesics of length at most L, but it returns l-centrality values for all nodes and edges and for every 1 ? l ? L. We show both analytically and numerically that l-centrality values obey a scaling form as function of l, that can be used to reliably predict the distribution of the full, diameter-range centralities, and also to identify high betweenness edges or nodes. The efficiency of the method is illustrated on different random graph models and a real-world social network inferred from mobile-phone trace-logs having a giant cluster with more than 5.5 ×106 nodes and 2.7 × 107 links.