Edith Cohen, Daniel Delling, Thomas Pajor, and Renato F. Werneck
21 May 2014
Closeness centrality, first considered by Bavelas (1948), is an importance measure of nodes in social and massive graphs, which is based on the distances from the node to all other nodes. The classic definition, proposed by Bavelas (1950), Beauchamp (1965), and Sabidussi (1966), is (the inverse of) the average distance to all other nodes.
We propose the first highly scalable (near linear-time processing and linear space overhead) algorithm for estimating, within a small relative error, the classic closeness centralities of all nodes in the graph. Our algorithm provides strong probabilistic guarantees on the approximation quality for all nodes of any undirected graph, as well as for centrality computed with respect to round-trip distances in directed graphs.
For directed graphs, we also propose an efficient algorithm that approximates generalizations of classic closeness centrality to outbound and inbound centralities. Although it does not provide worst-case theoretical approximation guarantees, it is designed to perform well on real networks.
We perform extensive experiments on large networks, demonstrating high scalability and accuracy.