Identifying high betweenness centrality nodes in large social networks

This paper proposes an alternative way to identify nodes with high betweenness centrality. It introduces a new metric, kappa-path centrality, and a randomized algorithm for estimating it, and shows empirically that nodes with high kappa-path centrality have high node betweenness centrality. The randomized algorithm runs in time O( kappa(3) n(2-2 alpha)log n) and outputs, for each vertex v, an estimate of its kappa-path centrality up to additive error of +/- n(1/2+alpha) with probability 1 - 1/n(2). Experimental evaluations on real and synthetic social networks show improved accuracy in detecting high betweenness centrality nodes and significantly reduced execution time when compared with existing randomized algorithms.