A faster algorithm for betweenness centrality

The betweenness centrality index is essential in the analysis of social net works, but costly to compute. Currently, the fastest known algorithms requi re circle minus (n(3)) time and circle minus (n(2)) space, where n is the n umber of actors in the network. 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 + n(2) l og n) time on unweighted and weighted networks, respectively, where m is th e number of links. Experimental evidence is provided that this substantiall y increases the range of networks for which centrality analysis is feasible .