Class GirvanNewmanClustering<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    ClusteringAlgorithm<V>

    public class GirvanNewmanClustering<V,​E>
    extends java.lang.Object
    implements ClusteringAlgorithm<V>
    The Girvan-Newman clustering algorithm.

    The algorithm is described in: Girvan, Michelle, and Mark EJ Newman. "Community structure in social and biological networks." Proceedings of the national academy of sciences 99.12 (2002): 7821-7826.

    Running time is $O(m^2 n)$ or $O(m^2n + m n^2 \log n)$ for weighted graphs.

    Author:
    Dimitrios Michail
    • Constructor Detail

      • GirvanNewmanClustering

        public GirvanNewmanClustering​(Graph<V,​E> graph,
                                      int k)
        Create a new clustering algorithm.
        Parameters:
        graph - the graph
        k - the desired number of clusters
      • GirvanNewmanClustering

        public GirvanNewmanClustering​(Graph<V,​E> graph,
                                      int k,
                                      EdgeBetweennessCentrality.OverflowStrategy overflowStrategy,
                                      java.lang.Iterable<V> startVertices)
        Create a new clustering algorithm.
        Parameters:
        graph - the graph
        k - the desired number of clusters
        overflowStrategy - strategy to use if overflow is detected
        startVertices - vertices from which to start shortest path computations when computing edge centralities. This parameter allows the user to compute edge centrality contributions only from a subset of the vertices of the graph. If null the whole graph vertex set is used.