A faster algorithm for betweenness centrality*

TLDR

Betweenness centrality is essential for social network analysis but traditionally requires O(n³) time and O(n²) space, limiting its use on large networks. The study introduces faster algorithms for computing betweenness centrality on large, sparse networks. The algorithms use O(n+m) memory and run in O(nm) time for unweighted graphs and O(nm + n² log n) for weighted graphs. Experiments show the new methods greatly extend the size of networks for which betweenness can be feasibly computed.

Abstract

Motivated by the fast‐growing need to compute centrality indices on large, yet very sparse, networks, new algorithms for betweenness are introduced in this paper. They require O(n + m) space and run in O(nm) and O(nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links. Experimental evidence is provided that this substantially increases the range of networks for which centrality analysis is feasible. The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require ?(n 3) time and ?(n 2) space, where n is the number of actors in the network.