org.apache.flink.graph.library

Class LabelPropagation<K,VV extends Comparable<VV>,EV>

java.lang.Object

org.apache.flink.graph.library.LabelPropagation<K,VV,EV>

Type Parameters:

K - vertex identifier type

VV - vertex value type which is used for comparison

EV - edge value type

All Implemented Interfaces:

GraphAlgorithm<K,VV,EV,DataSet<Vertex<K,VV>>>

public class LabelPropagation<K,VV extends Comparable<VV>,EV>
extends Object
implements GraphAlgorithm<K,VV,EV,DataSet<Vertex<K,VV>>>

An implementation of the label propagation algorithm. The iterative algorithm detects communities by propagating labels. In each iteration, a vertex adopts the label that is most frequent among its neighbors' labels.

The initial vertex values are used as initial labels and are expected to be Comparable. In case of a tie (i.e. two or more labels appear with the same frequency), the algorithm picks the greater label. The algorithm converges when no vertex changes its value or the maximum number of iterations has been reached. Note that different initializations might lead to different results.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	LabelPropagation.SendNewLabelToNeighbors<K,VV extends Comparable<VV>> Sends the vertex label to all out-neighbors.
static class	LabelPropagation.UpdateVertexLabel<K,VV extends Comparable<VV>> Function that updates the value of a vertex by adopting the most frequent label among its in-neighbors.

Constructor Summary

Constructors

Constructor and Description
LabelPropagation(int maxIterations) Creates a new Label Propagation algorithm instance.

Method Summary

Modifier and Type	Method and Description
DataSet<Vertex<K,VV>>	run(Graph<K,VV,EV> input)

Methods inherited from class java.lang.Object

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

Constructor Detail

LabelPropagation

public LabelPropagation(int maxIterations)

Creates a new Label Propagation algorithm instance. The algorithm converges when vertices no longer update their value or when the maximum number of iterations is reached.

Parameters:

maxIterations - The maximum number of iterations to run.

See Also:

Near linear time algorithm to detect community structures in large-scale networks

Method Detail

run

public DataSet<Vertex<K,VV>> run(Graph<K,VV,EV> input)

Specified by:

run in interface GraphAlgorithm<K,VV extends Comparable<VV>,EV,DataSet<Vertex<K,VV extends Comparable<VV>>>>