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.

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

Detect a community for the given seed node.

The default implementation calls expandOneCommunity(const std::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.

std::set<node> expandOneCommunity(const std::set<node> &seeds) = 0

Detect a single community for the given seed nodes.

This is useful if you know multiple nodes that should be part of the community. This method may throw an exception if the particular algorithm does not support multiple seeds.

Parameters:

seeds – The seeds for the community.

Returns:

The found community as set of nodes.