Class GroupHarmonicCloseness

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

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