  Closeness centrality, first considered by Bavelas (1948), is an importance
measure of a node in a network 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 applies
to undirected graphs, 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.
