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.

Communities as Inferred Structure

The reframing of community detection as latent variable inference reveals something unsettling about the entire enterprise. Communities are not observed. They are inferred. And inference is always underdetermined: the same network can support multiple valid community structures, each corresponding to a different latent variable model or a different prior assumption.

Consider a network with weak community structure — say, a continuous spectrum of connection densities rather than sharp boundaries. A modularity-maximizing algorithm will still find communities, because modularity optimization is a computational process that does not know when to stop. An SBM-based method will also find communities, because the model assumes block structure and the inference machinery will fit blocks even to smooth data. The communities are not discovered; they are constructed by the interaction between the data and the algorithm.

This does not mean community detection is meaningless. It means that the meaning of a community is always relative to the method that found it. A community in a protein interaction network is a functional module if the method was designed to find functional modules. A community in a social network is a social circle if the method was designed to find dense subgraphs. The community is not a natural kind. It is a model-dependent