Class GirvanNewman<V,​E extends UndirectedEdge<V>,​G extends UnDiGraph<V,​E>>

  • Type Parameters:
    V - vertex type
    E - edge type
    G - graph type
    Direct Known Subclasses:
    GirvanNewmanUnDiGraph

    public class GirvanNewman<V,​E extends UndirectedEdge<V>,​G extends UnDiGraph<V,​E>>
    extends Object
    The Girvan–Newman algorithm detects communities in complex systems. It progressively removes edges from the original graph. Those edges are the least central, i.e., most "between" communities.
    See Also:
    Wikipedia: Girvan–Newman algorithm
    • Constructor Detail

      • GirvanNewman

        public GirvanNewman​(UnDiGraph<V,​E> g,
                            GirvanNewman.EdgeBetweenessCtor<V> ebCtor,
                            GraphUtils.GraphFactory<G> gCtor)
        Construct an instance of the Girvan-Newman algorithm.
        Parameters:
        g - an undirected graph
        ebCtor - a customized constructor of edge-betweeness
        gCtor - a factory to construct instances of the graph type
    • Method Detail

      • removeMaxEdge

        public double removeMaxEdge()
        Removes the edge with the highest edge-betweeness. Recalculate the betweenness of all edges affected by the removal.
        Returns:
        the highest edge-betweeness; Double.NaN if there is no edge to remove
      • clusters

        public List<G> clusters()
        Gets all the clusters, each of which is connected.
        Returns:
        all the clusters
      • numberOfClusters

        public int numberOfClusters()
        Gets the number of connected clusters.
        Returns:
        the number of connected clusters
      • value

        public double value​(UndirectedEdge<V> edge)
        Get the edge-betweeness of an edge.
        Parameters:
        edge - an edge
        Returns:
        the edge-betweeness
      • maxEdge

        public UndirectedEdge<V> maxEdge()
        Gets the edge with the maximal edge-betweeness.
        Returns:
        the edge with the maximal edge-betweeness
      • maxValue

        public double maxValue()
        Get the maximum of edge-betweeness.
        Returns:
        the maximum of edge-betweeness
      • maxClusterSize

        public int maxClusterSize()
        Get the size of the maximal cluster.
        Returns:
        the size of the maximal cluster