Class LabelPropagationClustering.Implementation<V,E>

java.lang.Object
org.jgrapht.alg.clustering.LabelPropagationClustering.Implementation<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
Enclosing class:
LabelPropagationClustering<V,E>

private static class LabelPropagationClustering.Implementation<V,E> extends Object
The actual implementation
  • Field Details

    • graph

      private Graph<V,E> graph
    • rng

      private Random rng
    • maxIterations

      private int maxIterations
    • labels

      private Map<V,String> labels
  • Constructor Details

    • Implementation

      public Implementation(Graph<V,E> graph, Random rng, int maxIterations)
      Initialize the computation
      Parameters:
      graph - the graph
      rng - the random number generator
      maxIterations - maximum iterations
  • Method Details

    • compute

      public List<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<Map<String,Integer>,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 List<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
    • convert

      private List<Set<V>> convert(Graph<V,E> graph, Map<V,String> labels)
      Convert from a map representation to a list of sets.
      Parameters:
      graph - the graph
      labels - the map representation
      Returns:
      the list of sets