Module org.jgrapht.core
Package org.jgrapht.alg.clustering
Class LabelPropagationClustering.Implementation<V,E>
java.lang.Object
org.jgrapht.alg.clustering.LabelPropagationClustering.Implementation<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- Enclosing class:
LabelPropagationClustering<V,
E>
The actual implementation
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionImplementation
(Graph<V, E> graph, Random rng, int maxIterations) Initialize the computation -
Method Summary
Modifier and TypeMethodDescriptioncompute()
Main loop of the algorithmCompute the final communities from the labels.Convert from a map representation to a list of sets.Compute the frequency of the labels of all neighbors of a vertex and the maximum frequency of the vertices, which have a label not equal to the input vertex label.private boolean
Stopping criterion.private boolean
updateLabel
(V v) Update the label of a vertex.
-
Field Details
-
graph
-
rng
-
maxIterations
private int maxIterations -
labels
-
-
Constructor Details
-
Implementation
Initialize the computation- Parameters:
graph
- the graphrng
- the random number generatormaxIterations
- maximum iterations
-
-
Method Details
-
compute
Main loop of the algorithm- Returns:
- the clusters
-
shouldStop
private boolean shouldStop()Stopping criterion. Perform the iterative process until every node in the network has a label equal to a label that the maximum number of its neighbors belong to.- Returns:
- true whether we should stop, false otherwise
-
getNeighborLabelCountsAndMaximum
Compute the frequency of the labels of all neighbors of a vertex and the maximum frequency of the vertices, which have a label not equal to the input vertex label.- Parameters:
v
- the input vertex- Returns:
- the frequency of the labels of all neighbors of a vertex and the maximum label frequency of the vertices with a label not equal to the input vertex label
-
updateLabel
Update the label of a vertex.- Parameters:
v
- the vertex- Returns:
- true if a label change occurred
-
computeCommunities
Compute the final communities from the labels. We need to do some extra work due to the way the algorithm works, as described in the following paragraph from the original paper. "When the algorithm terminates it is possible that two or more disconnected groups of nodes have the same label (the groups are connected in the network via other nodes of different labels). This happens when two or more neighbors of a node receive its label and pass the labels in different directions, which ultimately leads to different communities adopting the same label. In such cases, after the algorithm terminates one can run a simple breadth-first search on the sub-networks of each individual groups to separate the disconnected communities."- Returns:
- the clustering
-
convert
Convert from a map representation to a list of sets.- Parameters:
graph
- the graphlabels
- the map representation- Returns:
- the list of sets
-