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.
