A faster algorithm for betweenness centrality

A faster algorithm for betweenness centrality,10.1080/0022250X.2001.9990249,Journal of Mathematical Sociology,Ulrik Brandes

A faster algorithm for betweenness centrality   (Citations: 385)
BibTex | RIS | RefWorks Download
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 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 ) time and ?(n ) space, where n is the number of actors in the network.
Journal: Journal of Mathematical Sociology - J MATH SOCIOL , vol. 25, no. 2, pp. 163-177, 2001
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: