Approximating betweenness centrality

David A. Bader, Shiva Kintali, Kamesh Madduri, Milena Mihail

Research output: Chapter in Book/Report/Conference proceedingConference contribution

223 Scopus citations


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 worstcase 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 observe that our random sampling algorithm gives very good betweenness approximations for biological networks, road networks and web crawls.

Original languageEnglish (US)
Title of host publicationAlgorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783540770039
StatePublished - 2007
Event5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007 - San Diego, CA, United States
Duration: Dec 11 2007Dec 12 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4863 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Approximating betweenness centrality'. Together they form a unique fingerprint.

Cite this