  In network analysis and graph mining, closeness centrality is a popular
measure to infer the importance of a vertex. Computing closeness efficiently
for individual vertices received considerable attention. The NP-hard problem of
group closeness maximization, in turn, is more challenging: the objective is to
find a vertex group that is central as a whole and state-of-the-art heuristics
for it do not scale to very big graphs yet.
  In this paper, we present new local search heuristics for group closeness
maximization. By using randomized approximation techniques and dynamic data
structures, our algorithms are often able to perform locally optimal decisions
efficiently. The final result is a group with high (but not optimal) closeness
centrality.
  We compare our algorithms to the current state-of-the-art greedy heuristic
both on weighted and on unweighted real-world graphs. For graphs with hundreds
of millions of edges, our local search algorithms take only around ten minutes,
while greedy requires more than ten hours. Overall, our new algorithms are
between one and two orders of magnitude faster, depending on the desired group
size and solution quality. For example, on weighted graphs and $k = 10$, our
algorithms yield solutions of $12,4\%$ higher quality, while also being
$793,6\times$ faster. For unweighted graphs and $k = 10$, we achieve solutions
within $99,4\%$ of the state-of-the-art quality while being $127,8\times$
faster.
