Advances in Exact and Approximate Group Closeness Centrality Maximization
This work provides faster algorithms for graph analysis tasks, but it is incremental as it builds on prior exact and approximation methods.
The paper tackles the NP-hard Group Closeness Centrality Maximization problem by proposing two new techniques to improve an existing exact algorithm, achieving speedups of up to 22.3 times, and enhancing an approximation algorithm with speedups of up to 2.9 times without compromising its guarantee.
In the NP-hard \textsc{Group Closeness Centrality Maximization} problem, the input is a graph $G = (V,E)$ and a positive integer $k$, and the task is to find a set $S \subseteq V$ of size $k$ that maximizes the reciprocal of group farness $f(S) = \sum_{v \in V} \min_{s \in S} \text{dist}(v,s)$. A widely used greedy algorithm with previously unknown approximation guarantee may produce arbitrarily poor approximations. To efficiently obtain solutions with quality guarantees, known exact and approximation algorithms are revised. The state-of-the-art exact algorithm iteratively solves ILPs of increasing size until the ILP at hand can represent an optimal solution. In this work, we propose two new techniques to further improve the algorithm. The first technique reduces the size of the ILPs while the second technique aims to minimize the number of needed iterations. Our improvements yield a speedup by a factor of $3.6$ over the next best exact algorithm and can achieve speedups by up to a factor of $22.3$. Furthermore, we add reduction techniques to a $1/5$-approximation algorithm, and show that these adaptations do not compromise its approximation guarantee. The improved algorithm achieves mean speedups of $1.4$ and a maximum speedup of up to $2.9$ times.