Community Detection is the unsupervised task of partitioning a graph into densely connected subgroups (communities) where nodes within a community are highly interconnected while connections between communities are sparse — the graph-theoretic analog of clustering, revealing the mesoscale organizational structure that lies between individual node properties and global network statistics.

What Is Community Detection?

• Definition: A community (also called module, cluster, or group) is a set of nodes $C subset V$ with significantly more internal edges (within $C$) than external edges (between $C$ and $V setminus C$). Formally, a good community has high internal edge density $frac{|E_{internal}|}{|C|(|C|-1)/2}$ and low external edge density relative to null model expectations. Community detection partitions the entire graph into such groups.
• Resolution Challenge: Communities exist at multiple scales — a social network has friend groups (5–20 people) nested within interest communities (100–1000 people) nested within regional communities (10,000+ people). Different methods and different parameter settings reveal different hierarchical levels, and there is no single "correct" partition.
• Ground Truth Ambiguity: Unlike supervised classification, community detection has no universal ground truth. Communities can be defined topologically (dense subgraphs), functionally (nodes with shared function), or by metadata (nodes with shared attributes). Different definitions produce different partitions, and the "best" partition depends on the application.

Why Community Detection Matters

• Social Network Analysis: Discovering interest groups, echo chambers, and influence communities in social media platforms (Facebook, Twitter/X, Reddit) reveals the social structure that drives information spread, opinion formation, and collective behavior. Community structure explains why information goes viral within some groups but not others.
• Biological Module Discovery: Protein-protein interaction networks organize into functional modules — groups of proteins that collaborate on specific biological processes (DNA repair, signal transduction, metabolism). Community detection in PPI networks discovers these functional modules without requiring any functional annotation, providing unsupervised functional classification of uncharacterized proteins.
• GNN Design: Community structure directly impacts GNN performance — GNNs propagate information within communities efficiently (short paths) but struggle to transmit information between communities (long paths through sparse bridges). Understanding community structure guides architectural decisions: how many layers are needed, whether to use global pooling, and when to employ over-squashing-aware propagation.
• Network Summarization: Large networks with millions of nodes can be summarized by their community structure — collapsing each community into a single super-node produces a compact "community graph" that preserves the mesoscale organization while dramatically reducing complexity for visualization and analysis.

Community Detection Methods

Community Detection is finding the cliques — uncovering the densely connected groups that organize complex networks into meaningful functional units, revealing the mesoscale structure that determines information flow, functional specialization, and emergent collective behavior.