A divide-and-conquer algorithm for betweenness centrality
MetadataShow full item record
CitationDóra Erdös, Vatche Ishakian, Azer Bestavros, Evimaria Terzi. 2015. "A Divide-and-Conquer Algorithm for Betweenness Centrality.." SDM, pp. 433 - 441.
Given a graph G we define the betweenness centrality of a node v in V as the fraction of shortest paths be- tween all node pairs in V that contain v. For this setting we describe Brandes++, a divide-and-conquer algorithm that can efficiently compute the exact values of between- ness scores. Brandes++ uses Brandes– the most widely- used algorithm for betweenness computation – as its subroutine. It achieves the notable faster running times by applying Brandes on significantly smaller networks than the input graph, and many of its computations can be done in parallel. The degree of speedup achieved by Brandes++ depends on the community structure of the input network. Our experiments with real-life net- works reveal Brandes++ achieves an average of 10-fold speedup over Brandes, while there are networks where this speedup is 75-fold. We have made our code public to benefit the research community.
Proceedings of the 2015 SIAM International Conference on Data Mining