Approximating Betweenness Centrality

@incollection{citeulike:2810173, abstract = {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 + n 2logn) 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 observe that our random sampling algorithm gives very good betweenness approximations for biological networks, road networks and web crawls.}, author = {Bader, David and Kintali, Shiva and Madduri, Kamesh and Mihail, Milena}, citeulike-article-id = {2810173}, doi = {10.1007/978-3-540-77004-6_10}, journal = {Algorithms and Models for the Web-Graph}, keywords = {approximation-algorithms, betweenness-centrality, graph-algorithms}, pages = {124--137}, posted-at = {2008-05-21 17:10:03}, priority = {2}, title = {Approximating Betweenness Centrality}, url = {http://dx.doi.org/10.1007/978-3-540-77004-6_10}, year = {2007} }

TY - CHAP ID - citeulike:2810173 L3 - citeulike-article-id:2810173 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 + n 2logn) 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 observe that our random sampling algorithm gives very good betweenness approximations for biological networks, road networks and web crawls. JF - Algorithms and Models for the Web-Graph EP - 137 TI - Approximating Betweenness Centrality SP - 124 KW - approximation-algorithms KW - betweenness-centrality KW - graph-algorithms AU - Bader, David AU - Kintali, Shiva AU - Madduri, Kamesh AU - Mihail, Milena PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-77004-6_10 ER -