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.
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.
