Class GedWalk

Nested Relationships

Nested Types

Inheritance Relationships

Base Type

Class Documentation

class GedWalk : public NetworKit::Algorithm

Public Types

enum GreedyStrategy


enumerator LAZY
enumerator STOCHASTIC
enumerator lazy
enumerator stochastic
enum BoundStrategy


enumerator NO
enumerator SPECTRAL
enumerator GEOMETRIC
enumerator no
enumerator spectral
enumerator geometric
enumerator adaptiveGeometric

Public Functions

GedWalk(const Graph &G, count k = 1, double initEpsilon = 0.1, double alpha = -1., BoundStrategy bs = BoundStrategy::GEOMETRIC, GreedyStrategy gs = GreedyStrategy::LAZY, double spectralDelta = 0.5)

Finds a group of k vertices with at least ((1 - 1/e) * opt - epsilon) GedWalk

centrality score, where opt is the highest possible score. The algorithm is based on the paper “Group

Centrality Maximization for Large-scale Graphs”, Angriman et al., ALENEX20. It implements two independent greedy strategies (lazy and stochastic). Furthermore, it allows to compute the

GedWalk score of a given set of nodes.

Note: if the graph is weighted, all weights should be in (0, 1].

  • G – A (weakly) connected graph.

  • k – The desired group size.

  • epsilon – Precision of the algorithm.

  • alpha – Exponent to compute the GedWalk score.

  • bs – Bound strategy to compute the GedWalk bounds, default: BoundStrategy::GEOMETRIC.

  • gs – Greedy strategy to be used (lazy or stochastic), default: GreedyStrategy::LAZY.

  • spectralDelta – Delta to be used for the spectral bound.

virtual void run() override

Run the algorithm.

inline double getApproximateScore() const

Return the approximate GedWalk score of the computed group.


The approximate score of the computed group.

template<class InputIt>
double scoreOfGroup(InputIt first, InputIt last, double scoreEpsilon = .1)

Return the GedWalk score of the input group.

  • first/last – The range that contains the input group.

  • scoreEpsilon – The precision of the score to be computed.

inline std::vector<node> groupMaxGedWalk() const

Return the computed group.


The computed group.

inline const std::vector<double> &boundOfMarginalGains() const

Public Members

double stocEpsilon = 0.1