Community detection is the problem of finding a set partition or an overlapping collection of vertex subsets in a graph so that vertices grouped together share a specified pattern of connectivity. In the most common assortative interpretation, a graph community has comparatively many internal graph edges and comparatively few graph edges joining it to other communities. Other definitions group vertices by structural roles or by latent classes in a stochastic block model, so there is no single definition of a graph community that is appropriate in every setting (Fortunato 2010).
A common approach chooses a set partition that maximizes graph modularity. Modularity compares the observed number of graph edges within each proposed community with the number expected from a null model that preserves the vertex degrees. Modularity is therefore both a measure of community structure and an objective function for community detection, although other definitions and objectives are also used.
The Louvain algorithm is a heuristic for increasing graph modularity by alternating local moves of vertices between communities with aggregation, in which each graph community is replaced by a single graph vertex (Blondel et al. 2008). It can produce communities whose induced subgraphs are disconnected. The Leiden algorithm introduces a refinement phase before aggregation. For the usual graph modularity objective on an undirected graph, it guarantees that each returned graph community induces a connected graph, but does not guarantee a set partition with maximum graph modularity (Traag et al. 2019).
Unlike a classical graph partitioning problem with prescribed part sizes or a fixed cut objective, community detection often includes choosing the number and sizes of the parts. Approaches include cluster analysis based on graph-derived similarities, spectral graph partitioning, and estimation of hidden block labels in a stochastic block model. When a random model supplies true hidden labels, detection commonly asks only for an estimated partition correlated with those labels, while finding every label correctly is a stronger requirement.
For a hypergraph, a hyperedge may meet several communities in different numbers of vertices. Community detection must then determine which hyperedge sizes and splitting patterns to favor, producing trade-offs that do not occur for ordinary pairwise graph edges (Li et al. 2026).
The Wolfram Language function FindGraphCommunities[g] finds communities in a graph, and CommunityGraphPlot[g] visualizes its community structure.
