Defined in File GroupClosenessLocalSearch.hpp
public NetworKit::Algorithm
(Class Algorithm)
Public Functions
Local search approximation algorithm for Group Closeness Maximization presented in “Group-Harmonic and Group-Closeness Maximization – Approximation and Engineering”, Angriman et al., ALENEX 2021. The algorithm evaluates all possible swaps between a vertex in the group and the vertices outside, and performs a swap iff the decrement in farness is at least $$(1 - 1 / (k \cdot (n - k)))$$, where $$k$$ is the number of vertices in the group. Thus, even in a best-case scenario the time complexity of this algorithm is $$O(n \cdot k)$$. To keep the number of swaps low, it is recommended to use this algorithm as a refinement step of an already good solution computed by a faster algorithm e.g., greedy (GroupCloseness), or GrowShrink (GroupClosenessGrowShrink). In undirected graphs the approximation ratio is 1/5, on directed graphs it has not been demonstrated.
G – A graph.
first, last – A range that contains the initial group of nodes.
runGrowShrink – Whether or not to run the Grow-Shrink algorithm on the initial group.
maxIterations – Maximum number of swaps allowed. Prevents the algorithm from performing too many swaps by giving up the approximation guarantee.
Runs the algorithm.