TY - GEN
T1 - Approximating betweenness centrality
AU - Bader, David A.
AU - Kintali, Shiva
AU - Madduri, Kamesh
AU - Mihail, Milena
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=38149071742&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149071742&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-77004-6_10
DO - 10.1007/978-3-540-77004-6_10
M3 - Conference contribution
AN - SCOPUS:38149071742
SN - 9783540770039
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 124
EP - 137
BT - Algorithms and Models for the Web-Graph - 5th International Workshop, WAW 2007, Proceedings
PB - Springer Verlag
T2 - 5th Workshop on Algorithms and Models for the Web-Graph, WAW 2007
Y2 - 11 December 2007 through 12 December 2007
ER -