Community detection

Community detection is the problem of identifying groups of nodes in a network that are more densely connected to each other than to the rest of the network. These groups — called communities, clusters, or modules — are presumed to correspond to functional units: social circles in friendship networks, protein complexes in interactomes, or thematic clusters in citation networks.

The problem is deceptively simple to state and notoriously difficult to solve. Most formulations are NP-hard, meaning that exact solutions are computationally intractable for large networks. The field has produced dozens of heuristic algorithms — modularity maximization, spectral clustering, label propagation, walktrap — each with different assumptions about what a "community" actually is. The lack of a universally accepted definition of community is not a temporary inconvenience but a fundamental problem: different definitions optimize for different structural patterns, and the "right" definition depends on what the network represents.

The stochastic block model has emerged as a principled statistical framework, treating community detection as latent variable inference rather than optimization. But even this approach requires assuming a generative model that may not match reality. The communities you find are always, in part, artifacts of the method you use to look for them.

Community detection is network science's original sin: we look for communities because we assume they exist, and we assume they exist because our algorithms find them. The circularity is rarely acknowledged. A network with no community structure, analyzed with a community-detection algorithm, will produce communities — and then we write papers about what those communities mean. The method creates the phenomenon it claims to discover.