David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

Approximating Betweenness Centrality

Betweenness is a centrality measure based on shortest paths, widely used in complex network analysis. It is computationally-expensive to exactly determine betweenness; currently the fastest-known algorithm by Brandes requires O(nm) time for unweighted graphs and O(nm + n2 log n) time for weighted graphs, where n is the number of vertices and m is the number of edges in the network. These are also the worst- case time bounds for computing the betweenness score of a single vertex. In this paper, we present a novel approximation algorithm for computing betweenness centrality of a given vertex, for both weighted and unweighted graphs. Our approximation algorithm is based on an adaptive sampling technique that significantly reduces the number of single-source shortest path computations for vertices with high centrality. We conduct an extensive experimental study on real-world graph instances, and ob observe that our random sampling algorithm gives very good betweenness approximations for biological networks, road networks and web crawls.

Publication History

Versions of this paper appeared as:
  1. D.A. Bader, S. Kintali, K. Madduri, and M. Mihail, ``Approximating Betweenness Centrality,'' The 5th Workshop on Algorithms and Models for the Web-Graph (WAW2007), San Diego, CA, December 11-12, 2007.

Download this report in Adobe PDF


 
 

Last updated: September 15, 2007

 




Computational Biology



Parallel Computing



Combinatorics