All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
NetworKit::PageRankNibble Class Reference

Variant of PageRank-Nibble algorithm due to Andersen, Chung and Lang. More...

#include <PageRankNibble.h>

Public Member Functions

 PageRankNibble (const Graph &g, double alpha, double epsilon)
virtual std::map< node,
std::set< node > > 
run (const std::set< node > &seeds) override
 Detect communities for given seed nodes. More...
virtual std::set< nodeexpandSeed (node seed)
- Public Member Functions inherited from NetworKit::SelectiveCommunityDetector
 SelectiveCommunityDetector (const Graph &G)

Protected Member Functions

std::set< nodebestSweepSet (std::vector< std::pair< node, double >> &pr)

Protected Attributes

double alpha
double epsilon
- Protected Attributes inherited from NetworKit::SelectiveCommunityDetector
const GraphG
 the input graph More...

Detailed Description

Variant of PageRank-Nibble algorithm due to Andersen, Chung and Lang.

Paper: Local Graph Partitioning using PageRank Vectors. URL: Simplifications according to D. Gleich's code at URL

Constructor & Destructor Documentation

NetworKit::PageRankNibble::PageRankNibble ( const Graph g,
double  alpha,
double  epsilon 
Graphg for which PageRank-Nibble is to be performed. Is treated as unweighted in current implementation.
alphaLoop probability of random walk; smaller values tend to produce larger communities.
epsTolerance threshold for approximation of PageRank vectors.

Member Function Documentation

std::set< node > NetworKit::PageRankNibble::bestSweepSet ( std::vector< std::pair< node, double >> &  pr)
std::set< node > NetworKit::PageRankNibble::expandSeed ( node  seed)
seedSeed node for which a community is to be found.
Set of nodes that makes up the best community found around node seed. If target conductance or target size are not fulfilled, an empty set is returned.
std::map< node, std::set< node > > NetworKit::PageRankNibble::run ( const std::set< node > &  seeds)

Detect communities for given seed nodes.

a mapping from seed node to community (as a set of nodes)

Implements NetworKit::SelectiveCommunityDetector.

Member Data Documentation

double NetworKit::PageRankNibble::alpha
double NetworKit::PageRankNibble::epsilon

The documentation for this class was generated from the following files: