Class PLP¶

Inheritance Relationships¶

Class Documentation¶

class PLP : public NetworKit::CommunityDetectionAlgorithm¶

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.

Public Functions

PLP(const Graph &G, count theta = none, count maxIterations = none)¶

Constructor to the label propagation community detection algorithm.

Parameters:

• G – [in] input graph

• theta – [in] updateThreshold: number of nodes that have to be changed in each iteration so that a new iteration starts.

PLP(const Graph &G, const Partition &baseClustering, count theta = none)¶

Constructor to the label propagation community detection algorithm.

Parameters:

• G – [in] input graph

• baseClustering – [in] optional; the algorithm will start from the given clustering.

• theta – [in] updateThreshold: number of nodes that have to be changed in each iteration so that a new iteration starts.

virtual void run() override¶

Run the label propagation clustering algorithm.

void setUpdateThreshold(count th)¶

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

Parameters:

th – The threshold.

count numberOfIterations()¶

Get number of iterations in last run.

Returns:

The number of iterations.

const std::vector<count> &getTiming() const¶

Get list of running times for each iteration.

Returns:

The list of running times in milliseconds