Class GedWalk¶

Nested Relationships¶

Inheritance Relationships¶

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

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¶