A faster algorithm for betweenness centrality*
Top Cited Papers
Open Access
- 1 June 2001
- journal article
- research article
- Published by Taylor & Francis in The Journal of Mathematical Sociology
- Vol. 25 (2) , 163-177
- https://doi.org/10.1080/0022250x.2001.9990249
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.Keywords
This publication has 14 references indexed in Scilit:
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Eccentricity and centrality in networksSocial Networks, 1995
- Semirings for social networks analysisThe Journal of Mathematical Sociology, 1994
- Theoretical Foundations for Centrality MeasuresAmerican Journal of Sociology, 1991
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- The gatekeeper, pair-dependency and structural centralityQuality & Quantity, 1980
- Centrality in social networks conceptual clarificationSocial Networks, 1978
- A Set of Measures of Centrality Based on BetweennessSociometry, 1977
- The Centrality Index of a GraphPsychometrika, 1966
- A Mathematical Model for Group StructuresHuman Organization, 1948