As described in Ovelgoenne et al: An Ensemble Learning Strategy for Graph Clustering Raghavan et al. More...
#include <PLP.h>
Public Member Functions  
PLP (const Graph &G, count theta=none, count maxIterations=none)  
Constructor to the label propagation community detection algorithm. More...  
PLP (const Graph &G, const Partition baseClustering, count theta=none)  
Constructor to the label propagation community detection algorithm. More...  
virtual void  run () 
Run the label propagation clustering algorithm. More...  
virtual std::string  toString () const 
virtual void  setUpdateThreshold (count th) 
The algorithm runs until a number of nodes less than the threshold is updated. More...  
virtual count  numberOfIterations () 
Get number of iterations in last run. More...  
virtual std::vector< count >  getTiming () 
Get list of running times for each iteration. More...  
Public Member Functions inherited from NetworKit::CommunityDetectionAlgorithm  
CommunityDetectionAlgorithm (const Graph &G)  
A community detection algorithm operates on a graph, so the constructor expects a graph. More...  
CommunityDetectionAlgorithm (const Graph &G, const Partition baseClustering)  
A community detection algorithm operates on a graph, so the constructor expects a graph. More...  
virtual  ~CommunityDetectionAlgorithm ()=default 
Default destructor. More...  
virtual Partition  getPartition () 
Returns the result of the run method or throws an error, if the algorithm hasn't run yet. More...  
Public Member Functions inherited from NetworKit::Algorithm  
Algorithm ()  
Constructor to the algorithm base class. More...  
virtual  ~Algorithm ()=default 
Virtual default destructor. More...  
bool  hasFinished () const 
Indicates whether an algorithm has completed computation or not. More...  
void  assureFinished () const 
Assure that the algorithm has been run, throws a std::runtime_error otherwise. More...  
virtual bool  isParallel () const 
Protected Attributes  
count  updateThreshold = 0 
count  maxIterations 
count  nIterations = 0 
number of iterations in last run More...  
std::vector< count >  timing 
running times for each iteration More...  
Protected Attributes inherited from NetworKit::CommunityDetectionAlgorithm  
const Graph &  G 
Partition  result 
Protected Attributes inherited from NetworKit::Algorithm  
bool  hasRun 
A boolean variable indicating whether an algorithm has finished its computation or not. More...  
As described in Ovelgoenne et al: An Ensemble Learning Strategy for Graph Clustering Raghavan et al.
proposed a label propagation algorithm for graph clustering. This algorithm initializes every vertex of a graph with a unique label. Then, in iterative sweeps over the set of vertices the vertex labels are updated. A vertex gets the label that the maximum number of its neighbors have. The procedure is stopped when every vertex has the label that at least half of its neighbors have.
Constructor to the label propagation community detection algorithm.
[in]  G  input graph 
[in]  theta  updateThreshold: number of nodes that have to be changed in each iteration so that a new iteration starts. 
Constructor to the label propagation community detection algorithm.
[in]  G  input graph 
[in]  baseClustering  optional; the algorithm will start from the given clustering. 
[in]  theta  updateThreshold: number of nodes that have to be changed in each iteration so that a new iteration starts. 

virtual 
Get list of running times for each iteration.

virtual 
Get number of iterations in last run.

virtual 
Run the label propagation clustering algorithm.
== Dealing with isolated nodes ==
The pseudocode published does not deal with isolated nodes (and therefore does not terminate if they are present). Isolated nodes stay singletons. They can be ignored in the while loop, but the loop condition must compare to the number of nonisolated nodes instead of n.
== Termination criterion ==
The published termination criterion is: All nodes have got the label of the majority of their neighbors. In general this does not work. It was changed to: No label was changed in last iteration.
Implements NetworKit::CommunityDetectionAlgorithm.

virtual 
The algorithm runs until a number of nodes less than the threshold is updated.
th  The threshold. 

virtual 
Reimplemented from NetworKit::CommunityDetectionAlgorithm.

protected 

protected 
number of iterations in last run

protected 
running times for each iteration

protected 