# Class GedWalk¶

## Class Documentation¶

class GedWalk : public NetworKit::Algorithm

Public Types

enum GreedyStrategy

Values:

enumerator LAZY
enumerator STOCHASTIC
enumerator lazy
enumerator stochastic
enum BoundStrategy

Values:

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

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

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

Returns:

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.

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

Returns:

The computed group.

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

Public Members

double stocEpsilon = 0.1