Class EdgeBetweennessClusterer<V,​E>

  • All Implemented Interfaces:
    com.google.common.base.Function<Graph<V,​E>,​java.util.Set<java.util.Set<V>>>, java.util.function.Function<Graph<V,​E>,​java.util.Set<java.util.Set<V>>>

    public class EdgeBetweennessClusterer<V,​E>
    extends java.lang.Object
    implements com.google.common.base.Function<Graph<V,​E>,​java.util.Set<java.util.Set<V>>>
    An algorithm for computing clusters (community structure) in graphs based on edge betweenness. The betweenness of an edge is defined as the extent to which that edge lies along shortest paths between all pairs of nodes. This algorithm works by iteratively following the 2 step process:
    • Compute edge betweenness for all edges in current graph
    • Remove edge with highest betweenness

    Running time is: O(kmn) where k is the number of edges to remove, m is the total number of edges, and n is the total number of vertices. For very sparse graphs the running time is closer to O(kn^2) and for graphs with strong community structure, the complexity is even lower.

    This algorithm is a slight modification of the algorithm discussed below in that the number of edges to be removed is parameterized.

    Author:
    Scott White, Tom Nelson (converted to jung2)
    See Also:
    "Community structure in social and biological networks by Michelle Girvan and Mark Newman"
    • Constructor Summary

      Constructors 
      Constructor Description
      EdgeBetweennessClusterer​(int numEdgesToRemove)
      Constructs a new clusterer for the specified graph.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.Set<java.util.Set<V>> apply​(Graph<V,​E> graph)
      Finds the set of clusters which have the strongest "community structure".
      java.util.List<E> getEdgesRemoved()
      Retrieves the list of all edges that were removed (assuming extract(...) was previously called).
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface com.google.common.base.Function

        equals
      • Methods inherited from interface java.util.function.Function

        andThen, compose
    • Constructor Detail

      • EdgeBetweennessClusterer

        public EdgeBetweennessClusterer​(int numEdgesToRemove)
        Constructs a new clusterer for the specified graph.
        Parameters:
        numEdgesToRemove - the number of edges to be progressively removed from the graph
    • Method Detail

      • apply

        public java.util.Set<java.util.Set<V>> apply​(Graph<V,​E> graph)
        Finds the set of clusters which have the strongest "community structure". The more edges removed the smaller and more cohesive the clusters.
        Specified by:
        apply in interface com.google.common.base.Function<V,​E>
        Specified by:
        apply in interface java.util.function.Function<V,​E>
        Parameters:
        graph - the graph
      • getEdgesRemoved

        public java.util.List<E> getEdgesRemoved()
        Retrieves the list of all edges that were removed (assuming extract(...) was previously called). The edges returned are stored in order in which they were removed.
        Returns:
        the edges in the original graph