A Divide-and-Conquer Algorithm for

Abstract. The problem of efficiently computing the betweenness cen-trality of nodes has been researched extensively. To date, the best known exact and centralized algorithm for this task is an algorithm proposed in 2001 by Brandes [7]. The contribution of our paper is Brandes++, an algo-rithm for exact efficient computation of betweenness centrality. The crux of our algorithm is that we create a sketch of the graph, that we call the skeleton, by replacing subgraphs with simpler graph structures. De-pending on the underlying graph structure, using this skeleton and by keeping appropriate summaries Brandes++ we can achieve significantly low running times in our computations. Extensive experimental evalua-tion on real life datasets demonstrate the efficacy of our algorithm for different types of graphs. We release our code for benefit of the research community.