Community Detection — Graph Clustering in Networks
Community Detection (Louvain, Girvan-Newman, Leiden, Infomap) · Also known as: graph clustering, network partitioning, Topluluk Tespiti (Louvain, Girvan-Newman, Leiden)
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?
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
+16 more
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.
Strengths & limitations
- 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.
- 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.
Frequently asked
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.
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. DOI: 10.1088/1742-5468/2008/10/P10008 ↗
- Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233. link ↗
How to cite this page
ScholarGate. (2026, June 1). Community Detection (Louvain, Girvan-Newman, Leiden, Infomap). ScholarGate. https://scholargate.app/en/network-analysis/community-detection
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Centrality AnalysisNetwork analysis↔ compare
- Exponential Random Graph ModelNetwork analysis↔ compare
- Hierarchical ClusteringMachine learning↔ compare
- Network Diffusion ModelsNetwork analysis↔ compare
- Stochastic Block ModelNetwork analysis↔ compare