A divide-and-conquer algorithm for betweenness centrality

Abstract

Given a set of target nodes S in a graph G we define the betweenness centrality of a node ν with respect to S as the fraction of shortest paths among nodes in S that contain v. For this setting we describe Brande S++, a divide-and-conquer algorithm that can efficiently compute the exact values of betweenness 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 as well as the size of S. Our experiments with real-life networks 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.