An Efficient Algorithm for Approximate Betweenness Centrality Computation

作者：Chehreghani Mostafa Haghir^*

来源：Computer Journal, 2014, 57(9): 1371-1382.

DOI：10.1093/comjnl/bxu003

• graphs
• network analysis
• social networks
• centrality
• betweenness centrality
• approximate algorithms

Centrality indices are essential in network analysis and betweenness centrality, which is based on shortest paths, is one of the most important measures. It has been widely used in different areas like social network analysis, World Wide Web and route planning. However, even for mid-size networks, it is computationally expensive to compute exact betweenness scores. In this paper, we propose a generic randomized framework for unbiased estimation of betweenness scores. The proposed framework can be adapted with various sampling techniques and give algorithms with different characteristics. We discuss the conditions a promising sampling technique should satisfy to minimize the approximation error, and propose a sampling method that partially satisfies the conditions. We perform extensive experiments on synthetic networks as well as networks from the real world, and show that, compared with existing exact and inexact algorithms, our method works with higher accuracy or gives significant speedups.

• 出版日期2014-9