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: http://www.math.ucsd.edu/~fan/wp/localpartition.pdf Simplifications according to D. Gleich's code at URL https://gist.github.com/dgleich/6201856.

Constructor & Destructor Documentation

NetworKit::PageRankNibble::PageRankNibble ( const Graph g,
double  alpha,
double  epsilon 
)
Parameters
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)
protected
std::set< node > NetworKit::PageRankNibble::expandSeed ( node  seed)
virtual
Parameters
seedSeed node for which a community is to be found.
Returns
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)
overridevirtual

Detect communities for given seed nodes.

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

Implements NetworKit::SelectiveCommunityDetector.

Member Data Documentation

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

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