Module org.jgrapht.core

Package org.jgrapht.alg.clustering

Class LabelPropagationClustering<V,E>

java.lang.Object

org.jgrapht.alg.clustering.LabelPropagationClustering<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

ClusteringAlgorithm<V>

public class LabelPropagationClustering<V,E>
extends Object
implements ClusteringAlgorithm<V>

A label propagation clustering algorithm.

The algorithm is a near linear time algorithm capable of discovering communities in large graphs. It is described in detail in the following paper:

• Raghavan, U. N., Albert, R., and Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3), 036106.

As the paper title suggests the running time is close to linear. The algorithm runs in iterations, each of which runs in $O(n + m)$ where $n$ is the number of vertices and $m$ is the number of edges. The authors found experimentally that in most cases, 95% of the nodes or more are classified correctly by the end of iteration 5. See the paper for more details.

The algorithm is randomized, meaning that two runs on the same graph may return different results. If the user requires deterministic behavior, the random number generator can be provided by the constructor.

Author:

Dimitrios Michail

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ClusteringAlgorithm

ClusteringAlgorithm.Clustering<V>, ClusteringAlgorithm.ClusteringImpl<V>

Constructor Summary

Constructors

Constructor	Description
LabelPropagationClustering(Graph<V,E> graph)	Create a new clustering algorithm.
LabelPropagationClustering(Graph<V,E> graph, int maxIterations)	Create a new clustering algorithm.
LabelPropagationClustering(Graph<V,E> graph, int maxIterations, Random rng)	Create a new clustering algorithm.
LabelPropagationClustering(Graph<V,E> graph, Random rng)	Create a new clustering algorithm.

Method Summary

Modifier and Type	Method	Description
ClusteringAlgorithm.Clustering<V>	getClustering()	Computes a clustering.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LabelPropagationClustering

public LabelPropagationClustering(Graph<V,E> graph)

Create a new clustering algorithm.

Parameters:

graph - the graph (needs to be undirected)

LabelPropagationClustering

public LabelPropagationClustering(Graph<V,E> graph,
                                  Random rng)

Create a new clustering algorithm.

Parameters:

graph - the graph (needs to be undirected)

rng - random number generator

LabelPropagationClustering

public LabelPropagationClustering(Graph<V,E> graph,
                                  int maxIterations)

Create a new clustering algorithm.

Parameters:

graph - the graph (needs to be undirected)

maxIterations - maximum number of iterations (zero means no limit)

LabelPropagationClustering

public LabelPropagationClustering(Graph<V,E> graph,
                                  int maxIterations,
                                  Random rng)

Create a new clustering algorithm.

Parameters:

graph - the graph (needs to be undirected)

maxIterations - maximum number of iterations (zero means no limit)

rng - random number generator

Method Detail

getClustering

public ClusteringAlgorithm.Clustering<V> getClustering()

Description copied from interface: ClusteringAlgorithm

Computes a clustering.

Specified by:

getClustering in interface ClusteringAlgorithm<V>

Returns:

a clustering