PRESTO: Fast and Effective Group Closeness Maximization

Given a graph and an integer
$k$
, the goal of
group closeness maximization
is to find, among all possible sets of
$k$
vertices (called
seed sets
), a set that has the
highest
group closeness centrality. Existing techniques for this NP-hard problem strive to quickly find a seed set with a
high
, but not necessarily the highest centrality. We propose
PRESTO
, a new solution that can efficiently provide both approximate and exact answers to the group closeness maximization problem.
PRESTO
continuously calculates the centrality of different seed sets until a time limit is reached or it identifies a seed set with the highest possible centrality. It prioritizes seed sets to quickly find ones that are highly central and thus can be used as accurate approximate answers to the problem. Furthermore,
PRESTO
can proactively discard large groups of seed sets that cannot have the highest centrality, thereby drastically speeding up the discovery of approximate and exact answers. In our evaluations, compared to other state-of-the-art solutions,
PRESTO
finds seed sets that have up to 39% higher centrality.