Class 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 java.lang.Object
    The actual implementation
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private Graph<V,​E> graph  
      private java.util.Map<V,​java.lang.String> labels  
      private int maxIterations  
      private java.util.Random rng  
    • 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 algorithm
      private 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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • graph

        private Graph<V,​E> graph
      • rng

        private java.util.Random rng
      • maxIterations

        private int maxIterations
      • labels

        private java.util.Map<V,​java.lang.String> labels
    • Constructor Detail

      • Implementation

        public Implementation​(Graph<V,​E> graph,
                              java.util.Random rng,
                              int maxIterations)
        Initialize the computation
        Parameters:
        graph - the graph
        rng - the random number generator
        maxIterations - maximum iterations
    • 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
      • convert

        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.
        Parameters:
        graph - the graph
        labels - the map representation
        Returns:
        the list of sets