  Given a connected graph $G=(V,E)$, the closeness centrality of a vertex $v$
is defined as $\frac{n-1}{\sum_{w \in V} d(v,w)}$. This measure is widely used
in the analysis of real-world complex networks, and the problem of selecting
the $k$ most central vertices has been deeply analysed in the last decade.
However, this problem is computationally not easy, especially for large
networks: in the first part of the paper, we prove that it is not solvable in
time $\O(|E|^{2-\epsilon})$ on directed graphs, for any constant $\epsilon>0$,
under reasonable complexity assumptions. Furthermore, we propose a new
algorithm for selecting the $k$ most central nodes in a graph: we
experimentally show that this algorithm improves significantly both the
textbook algorithm, which is based on computing the distance between all pairs
of vertices, and the state of the art. For example, we are able to compute the
top $k$ nodes in few dozens of seconds in real-world networks with millions of
nodes and edges. Finally, as a case study, we compute the $10$ most central
actors in the IMDB collaboration network, where two actors are linked if they
played together in a movie, and in the Wikipedia citation network, which
contains a directed edge from a page $p$ to a page $q$ if $p$ contains a link
to $q$.
