A faster algorithm for betweenness centrality*
Ulrik Brandes · Journal of Mathematical Sociology · 2001
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.
Cited by 4,936 works. doi:10.1080/0022250x.2001.9990249 Open-access PDF
Authors
References
- Introduction to Algorithms
- Social Network Analysis
- Social Network Analysis: Methods and Applications
- Authoritative sources in a hyperlinked environment
- Centrality in social networks conceptual clarification
- A Set of Measures of Centrality Based on Betweenness
- Data Structures and Algorithms
- Structural Models: An Introduction to the Theory of Directed Graphs.
- Social Network Analysis: A Handbook.
- Fibonacci heaps and their uses in improved network optimization algorithms