Class GroupClosenessLocalSearch¶

Nested Relationships¶

Inheritance Relationships¶

Class Documentation¶

class GroupClosenessLocalSearch : public NetworKit::Algorithm¶

Public Functions

template<class InputIt>
inline GroupClosenessLocalSearch(const Graph &G, InputIt first, InputIt last, bool runGrowShrink = true, count maxIterations = std::numeric_limits<count>::max())¶

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.

Parameters:

• 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.

GroupClosenessLocalSearch(const Graph &G, const std::vector<node> &group, bool runGrowShrink = true, count maxIterations = std::numeric_limits<count>::max())¶

virtual void run() override¶

Runs the algorithm.

std::vector<node> groupMaxCloseness() const¶

Returns the computed group.

count numberOfIterations() const¶

Returns the number of iterations performed by the algorithm.

class GroupClosenessLocalSearchInterface : public NetworKit::Algorithm¶

Public Functions

template<class InputIt>
inline GroupClosenessLocalSearchInterface(InputIt first, InputIt last)¶

Public Members

std::unordered_set<node> group¶

count nIterations¶