Given a connected graph G = (V , E), where V denotes the set of nodes and E the set of edges of the graph, the length (that is, the number of edges) of the shortest path between two nodes v and w is denoted by d (v, w ). The closeness centrality of a vertex v is then defined as n−1 w ∈V d (v,w ) , where n = |V |. 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 analyzed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the article, we prove that it is not solvable in time O(|E| 2−ϵ ) on directed graphs, for any constant ϵ > 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 Internet Movie Database (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. Graphs 53:3 and hundreds of millions of edges. The new approach combines the BFS-based algorithm with a pruning technique: during the algorithm, we compute and update upper bounds on the closeness of all the nodes, and we exclude a node v from the computation as soon as its upper bound is "small enough," that is, we are sure that v does not belong to the top k nodes. We propose two different strategies to set the initial bounds, and two different strategies to update the bounds during the computation: this means that our algorithm comes in four different variations. The experimental results show that different variations perform well on different kinds of networks, and the best variation of our algorithm drastically outperforms both a probabilistic approach (Okamoto et al. 2008) , and the best exact algorithm available until now (Olsen et al. 2014) . We have computed for the first time the 10 most central nodes (with respect to the closeness measure) in networks with millions of nodes and hundreds of millions of edges, and we have done so in very little time. A significant example is the wiki-Talk network, which was also used in (Sariyüce et al. 2013) , where the authors propose an algorithm to update closeness centralities after edge additions or deletions. Our performance is about 30,000 times better than the performance of the textbook algorithm: if only the most central node is needed, we can recompute it from scratch more than 150 times faster than the geometric average update time in (Sariyüce et al. 2013) . Moreover, our approach is not only very efficient, but it is also very easy to code, making it a very good candidate to be implemented in existing graph libraries. We provide an implementation of it in NetworKit (Staudt et al. 2016 ) and of one of its variations in Sagemath (Csárdi and Nepusz 2006) . We sketch the main ideas of the algorithm in Section 4, and we provide all details in Sections 5-8. We experimentally evaluate the efficiency of the new algorithm in Section 9. Also, our approach can be easily extended to any centrality measure in the form c (v) = w v f (d (v, w ) ), where f is a decreasing function. Apart from Lin's index, almost all the approaches that try to generalize closeness centrality to disconnected graphs fall under this category. The most popular among these measures is harmonic centrality (Marchiori and Latora 2000), defined as h(v) = w v 1 d (v,w ) . For the sake of completeness, in Section 9, we show that our algorithm performs well also for this measure. In the last part of the article (Sections 10 and 11), we consider two case studies: the actor collaboration network (1,797,446 vertices, 72,880,156 edges) and the Wikipedia citation network (4,229,697 vertices, 102,165,832 edges). In the actor collaboration network, we analyze the evolution of the 10 most central vertices, considering snapshots taken every 5 years between 1940 and 2014. The computation was performed in little more than 45 minutes. In the Wikipedia case study, we consider both the standard citation network, that contains a directed edge (p, q) if p contains a link to q, and the reversed network, that contains a directed edge (p, q) if q contains a link to p. For most of these graphs, we are able to compute the 10 most central pages in a few minutes, making them available for further analyses.
Bergamini et al. proposed a faster method to identify top-k nodes in undirected networks by approximating the upper bound on closeness centrality using BFT REF .
Computing top-k Closeness Centrality Faster in Unweighted Graphs
TKDD
Computer Science Mathematics