Theoretically and Empirically High Quality Estimation of Closeness Centrality

In the field of network analysis, centrality values of graph nodes, which represents the importance of nodes, have been widely studied. In this paper, we focus on one of the most basic centrality measures: closeness centrality. Since the exact computation of closeness centrality for all nodes of a network is prohibitively costly for massive networks, algorithms for estimating closeness centrality have been studied. In previous works, theoretical bounds on relative error have been improved. However, for complex networks such as social networks, empirical estimation qualities have hardly been improved since the sampling-based algorithm was proposed. In this paper, we propose simple and highly scalable algorithms for estimating closeness centrality of undirected networks. Our algorithms have theoretically and empirically better estimation quality than previous ones. As a result, our algorithms achieve strong quality guarantees and experimentally small relative errors at the same time. Also, our algorithms can be extended to strongly connected directed networks. Moreover, we can apply our algorithms to weighted centrality, in which nodes may have different weight, with slight modification.