Our paper “Computing Top-k Closeness Centrality Faster in Unweighted Graphs” has been accepted for ALENEX 2016 (Algorithms Engineering and Experiments).
Thanks to all the coauthors Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi and Henning Meyerhenke. This work is the result of a merge between our work (see here) and the work by Elisabetta and Henning. It’s a pleasure to start this new collaboration.
This is the abstract of the final paper.
Centrality indices are widely used analytic measures for the importance of nodes in a network.
Closeness centrality is very popular among these measures. For a single node v, it takes the sum of
the distances of v to all other nodes into account. The currently best algorithms in practical applications
for computing the closeness for all nodes exactly in unweighted graphs are based on breadth-first search (BFS) from every node. Thus, even for sparse graphs, these algorithms require quadratic running time in the worst case,
which is prohibitive for large networks.In many relevant applications, however, it is unnecessary to compute closeness values for all nodes. Instead,
one requires only the k nodes with the highest closeness values in descending order.
Thus, we present a new algorithm for computing this top-k ranking in unweighted graphs. Following the rationale of previous work, our algorithm significantly reduces the number of traversed edges. It does so by computing upper bounds on the closeness and stopping the current BFS search when k nodes already have higher closeness than the bounds computed for the other nodes.In our experiments with real-world and synthetic instances of various types, one of these new bounds is good for small-world graphs with low diameter (such as social networks), while
the other one excels for graphs with high diameter (such as road networks). Combining them
yields an algorithm that is faster than the state of the art for top-k computations for all test instances,
by a wide margin for high-diameter graphs.Finally, we prove that the quadratic worst-case complexity cannot be improved on directed, disconnected graphs, under reasonable complexity assumptions.