# From Louvain to Leiden: guaranteeing well-connected communities

arXiv: https://arxiv.org/abs/1810.08473 · HTML: https://mlsanity.com/paper/1810.08473/

## Key facts

- Cited by 385 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2018.

## Built on by (most cited first, 30 of 385)

- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Zep: A Temporal Knowledge Graph Architecture for Agent Memory](https://mlsanity.com/paper/2501.13956/) (2025)
- [Self-supervised Learning on Graphs: Contrastive, Generative,or Predictive](https://mlsanity.com/paper/2105.07342/) (2021)
- [Agentic Reasoning: A Streamlined Framework for Enhancing LLM Reasoning with Agentic Tools](https://mlsanity.com/paper/2502.04644/) (2025)
- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Retrieval-Augmented Generation with Hierarchical Knowledge](https://mlsanity.com/paper/2503.10150/) (2025)
- [In-depth Analysis of Graph-based RAG in a Unified Framework](https://mlsanity.com/paper/2503.04338/) (2025)
- [Glitch Tokens in Large Language Models: Categorization Taxonomy and Effective Detection](https://mlsanity.com/paper/2404.09894/) (2024)
- [DRAWER: Digital Reconstruction and Articulation With Environment Realism](https://mlsanity.com/paper/2504.15278/) (2025)
- [ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented Generation](https://mlsanity.com/paper/2502.09891/) (2025)
- [NodeRAG: Structuring Graph-based RAG with Heterogeneous Nodes](https://mlsanity.com/paper/2504.11544/) (2025)
- [CAM: A Constructivist View of Agentic Memory for LLM-Based Reading Comprehension](https://mlsanity.com/paper/2510.05520/) (2025)
- [PyTorch Geometric Signed Directed: A Software Package on Graph Neural Networks for Signed and Directed Graphs](https://mlsanity.com/paper/2202.10793/) (2022)
- [Revisiting Modularity Maximization for Graph Clustering: A Contrastive Learning Perspective](https://mlsanity.com/paper/2406.14288/) (2024)
- [Optimizing the Interface Between Knowledge Graphs and LLMs for Complex Reasoning](https://mlsanity.com/paper/2505.24478/) (2025)
- [Adaptive Conformal Prediction by Reweighting Nonconformity Score](https://mlsanity.com/paper/2303.12695/) (2023)
- [MMGraphRAG: Bridging Vision and Language with Interpretable Multimodal Knowledge Graphs](https://mlsanity.com/paper/2507.20804/) (2025)
- [BookRAG: A Hierarchical Structure-aware Index-based Approach for Retrieval-Augmented Generation on Complex Documents](https://mlsanity.com/paper/2512.03413/) (2025)
- [DIGRAC: Digraph Clustering Based on Flow Imbalance](https://mlsanity.com/paper/2106.05194/) (2021)
- [MuSe-GNN: Learning Unified Gene Representation From Multimodal Biological Graph Data](https://mlsanity.com/paper/2310.02275/) (2023)
- [Evolution of SAE Features Across Layers in LLMs](https://mlsanity.com/paper/2410.08869/) (2024)
- [A Comprehensive Review of Community Detection in Graphs](https://mlsanity.com/paper/2309.11798/) (2023)
- [Generative Adversarial Reviews: When LLMs Become the Critic](https://mlsanity.com/paper/2412.10415/) (2024)
- [Lead-lag detection and network clustering for multivariate time series with an application to the US equity market](https://mlsanity.com/paper/2201.08283/) (2022)
- [American Stories: A Large-Scale Structured Text Dataset of Historical U.S. Newspapers](https://mlsanity.com/paper/2308.12477/) (2023)
- [Season combinatorial intervention predictions with Salt & Peper](https://mlsanity.com/paper/2404.16907/) (2024)
- [FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioning](https://mlsanity.com/paper/2412.10669/) (2024)
- [Coordinating Narratives and the Capitol Riots on Parler](https://mlsanity.com/paper/2109.00945/) (2021)
- [Topology-Agnostic Detection of Temporal Money Laundering Flows in Billion-Scale Transactions](https://mlsanity.com/paper/2309.13662/) (2023)

## Abstract (arXiv)

Community detection is often used to understand the structure of large and complex networks. One of the most popular algorithms for uncovering community structure is the so-called Louvain algorithm. We show that this algorithm has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively. In our experimental analysis, we observe that up to 25% of the communities are badly connected and up to 16% are disconnected. To address this problem, we introduce the Leiden algorithm. We prove that the Leiden algorithm yields communities that are guaranteed to be connected. In addition, we prove that, when the Leiden algorithm is applied iteratively, it converges to a partition in which all subsets of all communities are locally optimally assigned. Furthermore, by relying on a fast local move approach, the Leiden algorithm runs faster than the Louvain algorithm. We demonstrate the performance of the Leiden algorithm for several benchmark and real-world networks. We find that the Leiden algorithm is faster than the Louvain algorithm and uncovers better partitions, in addition to providing explicit guarantees.