Class GroupHarmonicCloseness¶

Nested Relationships¶

Inheritance Relationships¶

Class Documentation¶

class GroupHarmonicCloseness : public NetworKit::Algorithm¶

Public Functions

GroupHarmonicCloseness(const Graph &G, count k = 1)¶

Approximation algorithm for the group-harmonic maximization problem. The computed solutions have a guaranteed $\lambda(1 - \frac{1}{2e})$ (directed graphs) and $\lambda(1 - \frac{1}/{e})/2$ (undirected graphs) approximation ratio, where $\lambda$ is the ratio between the minimal and the maximal edge weight. The algorithm is the one proposed in Angriman et al., ALENEX 2021. The worst-case running time of this approach is quadratic, but usually much faster in practice.

Parameters:

• G – The input graph.

• k – Size of the group of nodes.

virtual void run() override¶

Runs the algorithm.

const std::vector<node> &groupMaxHarmonicCloseness() const¶

Returns the computed group.

Returns:

The computed group.

Public Static Functions

template<class InputIt>
static double scoreOfGroup(const Graph &graph, InputIt first, InputIt last)¶

Computes the group-harmonic score of the group of nodes in the given range.

Parameters:

• graph – The input Graph.

• first, last – The range that contains the vertices in the group.

Returns:

The score of the group of nodes in the given range.

class GroupHarmonicClosenessInterface : public NetworKit::Algorithm¶

Public Members

std::vector<node> group¶