Module org.jgrapht.core
Package org.jgrapht.alg.clustering

Class NaiveGreedyModularityAlgorithm<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    ClusteringAlgorithm<V>
    public class NaiveGreedyModularityAlgorithm<V,​E>
extends Object
implements ClusteringAlgorithm<V>
    A naive implementation of greedy modularity maximization for community detection.

    The algorithm partitions the vertices of an undirected graph into communities by greedily maximizing the modularity of possible communities. Greedy modularity maximization begins with each node in its own community and repeatedly joins the pair of communities that lead to the largest modularity until no further increase in modularity is possible (a maximum).

    This implementation is simple but computationally expensive, with a worst-case complexity of O(n^4). It is intended as an easy-to-understand reference implementation rather than a performance-optimized solution.

    Author:
    Antonia Tsiftsi