Measuring similarities between vertices is an important task in network analysis, which has numerous applications. One major approach to define a similarity between vertices is by accumulating weights of walks between them that encompasses personalized PageRank (PPR) and Katz similarity. Although many effective methods for PPR based on efficient simulation of random walks have been proposed, these techniques cannot be applied to other walk-based similarity notions because the random walk interpretation is only valid for PPR.

Revealing important vertices is a fundamental task in network analysis. As such, many indicators have been proposed for doing so, which are collectively called centralities. However, the abundance of studies on centralities blurs their differences.

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.