An Efficient Estimation of a Node’s Betweenness

Betweenness Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen wide and increasing applications across several disciplines of late. In conjunction with the big data problems, there came the need to analyze large complex networks. Exact computation of a node’s betweenness is a daunting task in the networks of large size. In this paper, we propose a non-uniform sampling method to estimate the betweenness of a node. We apply our approach to estimate a node’s betweenness in several synthetic and real world graphs. We compare our method with the available techniques in the literature and show that our method fares several times better than the currently known techniques. We further show that the accuracy of our algorithm gets better with the increase in size and density of the network.