Community Detection — Graph Clustering in Networks
- Introduced by
- Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
- Year
- 2002–2019 (algorithm family)
- Type
- Graph-partitioning / clustering algorithm family
What does it do?
Community detection is a family of graph-partitioning algorithms that discover densely connected sub-groups — communities — within a network.
First formalised through the modularity measure by Girvan and Newman (2002), the field advanced rapidly with the Louvain method (Blondel et al., 2008), the Leiden refinement (Traag et al., 2019), and the information-theoretic Infomap approach. All variants answer the same question: which nodes cluster together more tightly among themselves than with the rest of the network?
The intuition behind the method
Imagine a large social network where some people talk mostly to their immediate circle while only occasionally reaching outside it. Community detection finds those circles automatically, without you having to label them in advance. The algorithm rearranges nodes into groups so that internal connections are dense and cross-group connections are sparse — maximising a quality score called modularity (or, in Infomap, minimising the description length of a random walk through the network). The result is a partition: every node belongs to exactly one community, and you can visualise the network as a set of cohesive clusters.
History
The study of community structure in networks was placed on a quantitative footing by Girvan and Newman (2002), who introduced the concept of edge betweenness as a tool for hierarchical network division. Newman and Girvan (2004) then formalised the modularity measure Q, which became the standard quality criterion. Blondel et al. (2008) published the Louvain method — a two-phase greedy optimisation that made high-quality community detection practical on networks with millions of nodes. Traag, Waltman, and van Eck (2019) identified a structural flaw in Louvain — that it can produce internally disconnected communities — and developed the Leiden algorithm to correct it, guaranteeing well-connected partitions. In parallel, Rosvall and Bergstrom (2008) developed Infomap, which reframes community detection as a compression problem: find the partition that minimises the description length of a random walk on the network.
When to use it
Community detection is appropriate when you have a network (at minimum ~20 nodes) and want to discover latent group structure without pre-specifying the groups. It suits exploratory, descriptive, and classification goals on binary or continuous edge-weight data, including cross-sectional and longitudinal network data. It does not require node attributes or normal distributions. The method is particularly well suited when the number of communities is unknown. If the network is too small (fewer than 20 nodes), descriptive network statistics are preferred. Results are sensitive to edge-weight definitions and network density, so those choices deserve careful thought.
Limitations and considerations
- Modularity maximisation is susceptible to local optima; results may vary across runs and should be reported as the best of multiple runs.
- The resolution limit means very small communities in large networks may be merged together, masking fine-grained structure.
- Results are sensitive to how edge weights are defined; different weighting schemes can yield meaningfully different partitions.
- Girvan-Newman has O(m²n) complexity and is impractical on large networks; Louvain or Leiden should be preferred for scale.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Does not require the number of communities to be specified in advance — the partition size is determined by the data.
- Scales to large networks: Louvain and Leiden run in near-linear time, making them practical for networks with millions of nodes.
- Leiden guarantees well-connected, internally cohesive communities, correcting the disconnected-community flaw of Louvain.
- Applicable to both unweighted and weighted networks without distributional assumptions on the data.
Applications
- Identifying research clusters in citation and co-authorship networks to map scientific fields.
- Detecting functional modules in protein-protein interaction networks in biology.
- Finding user communities in social media and communication networks for behavioural analysis.
- Segmenting customer networks in business and marketing to reveal cohesive customer groups.
- Discovering structural blocks in infrastructure, transport, or supply-chain networks.
How it works
How it works
The input is a graph whose nodes represent entities (people, web pages, proteins, citations) and whose edges represent relationships between them. Edges may be directed or undirected, and may carry weights. The adjacency structure — which nodes are connected and how strongly — is the sole input the algorithms need. No node labels, classes, or external attributes are required, though they can be used to validate results later.
Each algorithm begins with an initial assignment of nodes to communities. In Louvain and Leiden every node starts as its own singleton community. Girvan-Newman starts with the full network and iteratively removes the edge with the highest betweenness centrality, progressively revealing the community structure. Infomap starts from a random-walk description of the network and encodes it using a two-level map to minimise the code length.
The core phase searches for a partition that maximises modularity Q (Louvain, Leiden) or minimises map-equation code length (Infomap). Louvain greedily moves single nodes between communities to improve Q, then aggregates communities into super-nodes and repeats — a two-phase process that scales well but can produce disconnected communities. Leiden refines Louvain by guaranteeing every community is internally connected, using a local moving and refinement step before aggregation. Girvan-Newman removes edges iteratively and records the dendrogram of splits; the partition that maximises Q at any cut of the dendrogram is selected. The number of communities emerges from the algorithm itself; it does not need to be specified in advance.
The quality of the final partition is summarised by the modularity score Q, which ranges from −0.5 to 1. Values above ~0.3–0.5 are generally considered indicative of meaningful community structure. Because modularity optimisation can get trapped in local optima, running the algorithm multiple times and taking the best result is standard practice. The partition is also inspected visually and cross-validated against any available node attributes or ground-truth labels to confirm it is substantively meaningful.
Common pitfalls
- Running the algorithm once and treating the single result as ground truth — always run multiple times and report the best modularity or use ensemble methods.
- Ignoring the resolution limit: in large sparse networks, small but real communities can be absorbed into larger ones without warning.
- Applying modularity-based algorithms to networks with fewer than 20 nodes — community structure cannot be reliably identified at that scale.
- Confusing a high modularity score with confirmed real-world community structure; modularity is a quality measure of the partition, not an inferential test of whether communities are statistically significant.
Frequently asked questions
Which algorithm should I choose — Louvain, Leiden, Girvan-Newman, or Infomap?
Louvain is a fast, widely used baseline for large networks. Leiden is the preferred choice when correctness matters, as it guarantees internally connected communities and typically achieves higher modularity. Girvan-Newman produces a dendrogram useful for hierarchical exploration but is too slow for large networks. Infomap is well suited to directed or flow-based networks where the path a random walker takes is meaningful.
Do I need to specify the number of communities in advance?
No. Louvain, Leiden, and Infomap determine the number of communities automatically from the network structure. Girvan-Newman produces a full dendrogram from which any number of communities can be read off; the partition maximising Q is usually selected.
How do I know whether the communities found are meaningful?
The modularity score Q provides a data-internal quality measure; values above roughly 0.3–0.5 suggest non-trivial community structure. Beyond that, the communities should be validated against domain knowledge, node attributes, or external labels. High Q alone does not prove sociological or biological significance.
What happens if results differ across runs?
Modularity optimisation is a heuristic and different runs can yield slightly different partitions, especially in Louvain. Run the algorithm multiple times (at least 10–100 runs on large networks) and report the partition with the highest Q. Leiden is more stable than Louvain because its refinement step is more thorough, but repeated runs remain good practice.
Related methods
Sources
Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.
Open DOI referenceCopied.Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.
Open publication referenceCopied.