Class PageRankNibble¶

Inheritance Relationships¶

Class Documentation¶

class PageRankNibble : public NetworKit::SelectiveCommunityDetector¶

Variant of PageRank-Nibble algorithm due to Andersen, Chung and Lang. Paper: Local Graph Partitioning using PageRank Vectors. URL: http://www.math.ucsd.edu/~fan/wp/localpartition.pdf Simplifications according to D. Gleich’s code at URL https://gist.github.com/dgleich/6201856.

Public Functions

PageRankNibble(const Graph &g, double alpha, double epsilon)¶

Parameters:

• Graph – g for which PageRank-Nibble is to be performed. Is treated as unweighted in current implementation.

• alpha – Loop probability of random walk; smaller values tend to produce larger communities.

• eps – Tolerance threshold for approximation of PageRank vectors.

~PageRankNibble() override = default¶

virtual std::set<node> expandOneCommunity(const std::set<node> &seeds) override¶

Parameters:

seeds – Seed nodes for which a community is to be found.

Returns:

Set of nodes that makes up the best community found around the seeds nodes.

virtual std::set<node> expandOneCommunity(node seed)¶

Detect a community for the given seed node.

The default implementation calls expandOneCommunity(conststd::set<node>&) with a set of one node.

Parameters:

seed – The seed to find the community for.

Returns:

The found community as set of node.