  Closeness is an important centrality measure widely used in the analysis of
real-world complex networks. In particular, the problem of selecting the k most
central nodes with respect to this measure has been deeply analyzed in the last
decade. However, even for not very large networks, this problem is
computationally intractable in practice: indeed, Abboud et al have recently
shown that its complexity is strictly related to the complexity of the
All-Pairs Shortest Path (in short, APSP) problem, for which no subcubic
"combinatorial" algorithm is known. In this paper, we propose a new algorithm
for selecting the k most closeness central nodes in a graph. In practice, this
algorithm significantly improves over the APSP approach, even though its
worst-case time complexity is the same. For example, the algorithm is able to
compute the top k nodes in few dozens of seconds even when applied to
real-world networks with millions of nodes and edges. We will also
experimentally prove that our algorithm drastically outperforms the most
recently designed algorithm, proposed by Olsen et al. Finally, we apply the new
algorithm to the computation of the most central actors in the IMDB
collaboration network, where two actors are linked if they played together in a
movie.
