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>
private static class LabelPropagationClustering.Implementation<V,E> extends java.lang.Object
The actual implementation
-
-
Constructor Summary
Constructors Constructor Description Implementation(Graph<V,E> graph, java.util.Random rng, int maxIterations)
Initialize the computation
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.List<java.util.Set<V>>
compute()
Main loop of the algorithmprivate java.util.List<java.util.Set<V>>
computeCommunities()
Compute the final communities from the labels.private java.util.List<java.util.Set<V>>
convert(Graph<V,E> graph, java.util.Map<V,java.lang.String> labels)
Convert from a map representation to a list of sets.private Pair<java.util.Map<java.lang.String,java.lang.Integer>,java.lang.Integer>
getNeighborLabelCountsAndMaximum(V v)
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
shouldStop()
Stopping criterion.private boolean
updateLabel(V v)
Update the label of a vertex.
-
-
-
Method Detail
-
compute
public java.util.List<java.util.Set<V>> 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
private Pair<java.util.Map<java.lang.String,java.lang.Integer>,java.lang.Integer> getNeighborLabelCountsAndMaximum(V v)
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
private boolean updateLabel(V v)
Update the label of a vertex.- Parameters:
v
- the vertex- Returns:
- true if a label change occurred
-
computeCommunities
private java.util.List<java.util.Set<V>> 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
-
-