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

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< countgetTiming ()
 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< counttiming
 running times for each iteration More...
 
- Protected Attributes inherited from NetworKit::CommunityDetectionAlgorithm
const GraphG
 
Partition result
 
- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Detailed Description

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 & Destructor Documentation

NetworKit::PLP::PLP ( const Graph G,
count  theta = none,
count  maxIterations = none 
)

Constructor to the label propagation community detection algorithm.

Parameters
[in]Ginput graph
[in]thetaupdateThreshold: number of nodes that have to be changed in each iteration so that a new iteration starts.
NetworKit::PLP::PLP ( const Graph G,
const Partition  baseClustering,
count  theta = none 
)

Constructor to the label propagation community detection algorithm.

Parameters
[in]Ginput graph
[in]baseClusteringoptional; the algorithm will start from the given clustering.
[in]thetaupdateThreshold: number of nodes that have to be changed in each iteration so that a new iteration starts.

Member Function Documentation

std::vector< count > NetworKit::PLP::getTiming ( )
virtual

Get list of running times for each iteration.

Returns
The list of running times in milliseconds
count NetworKit::PLP::numberOfIterations ( )
virtual

Get number of iterations in last run.

Returns
The number of iterations.
void NetworKit::PLP::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 non-isolated 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.

void NetworKit::PLP::setUpdateThreshold ( count  th)
virtual

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

Parameters
thThe threshold.
std::string NetworKit::PLP::toString ( ) const
virtual
Returns
String representation of algorithm and parameters.

Reimplemented from NetworKit::CommunityDetectionAlgorithm.

Member Data Documentation

count NetworKit::PLP::maxIterations
protected
count NetworKit::PLP::nIterations = 0
protected

number of iterations in last run

std::vector<count> NetworKit::PLP::timing
protected

running times for each iteration

count NetworKit::PLP::updateThreshold = 0
protected

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