mlsanityData to 7 Oct 2026

From Louvain to Leiden: guaranteeing well-connected communities

arXiv 1810.08473 ↗First posted 19 Oct 2018cs.SI physics.soc-phcited by 379

Not on the map. Why?

Cited by 31 in Retrieval-augmented generation, but placed by its own abstract, which didn’t fit.

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.

Key facts. Cited by 379 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 31; 2022: 28; 2023: 38; 2024: 55; 2025: 95; 2026: 132.

379 papers.

Sort:

By area:

  1. 2024From Local to Global: A Graph RAG Approach to Query-Focused Summarizationcited by 1,411
  2. 2025Zep: A Temporal Knowledge Graph Architecture for Agent Memorycited by 372
  3. 2021Self-supervised Learning on Graphs: Contrastive, Generative,or Predictivecited by 136
  4. 2025Agentic Reasoning: A Streamlined Framework for Enhancing LLM Reasoning with Agentic Toolscited by 106
  5. 2023Evaluating Cognitive Maps and Planning in Large Language Models with CogEvalcited by 77
  6. 2021Generative hypergraph clustering: from blockmodels to modularitycited by 48
  7. 2025Retrieval-Augmented Generation with Hierarchical Knowledgecited by 46
  8. 2025In-depth Analysis of Graph-based RAG in a Unified Frameworkcited by 45
  9. 2025DRAWER: Digital Reconstruction and Articulation With Environment Realismcited by 29
  10. 2024Glitch Tokens in Large Language Models: Categorization Taxonomy and Effective Detectioncited by 27
  11. 2025ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented Generationcited by 27
  12. 2025NodeRAG: Structuring Graph-based RAG with Heterogeneous Nodescited by 25
38 more
  1. 2025CAM: A Constructivist View of Agentic Memory for LLM-Based Reading Comprehensioncited by 23
  2. 2022PyTorch Geometric Signed Directed: A Software Package on Graph Neural Networks for Signed and Directed Graphscited by 18
  3. 2024Revisiting Modularity Maximization for Graph Clustering: A Contrastive Learning Perspectivecited by 18
  4. 2025Optimizing the Interface Between Knowledge Graphs and LLMs for Complex Reasoningcited by 17
  5. 2023Adaptive Conformal Prediction by Reweighting Nonconformity Scorecited by 16
  6. 2025MMGraphRAG: Bridging Vision and Language with Interpretable Multimodal Knowledge Graphscited by 16
  7. 2025BookRAG: A Hierarchical Structure-aware Index-based Approach for Retrieval-Augmented Generation on Complex Documentscited by 16
  8. 2021DIGRAC: Digraph Clustering Based on Flow Imbalancecited by 15
  9. 2023MuSe-GNN: Learning Unified Gene Representation From Multimodal Biological Graph Datacited by 14
  10. 2024Evolution of SAE Features Across Layers in LLMscited by 14
  11. 2023A Comprehensive Review of Community Detection in Graphscited by 12
  12. 2024Generative Adversarial Reviews: When LLMs Become the Criticcited by 12
  13. 2022Lead-lag detection and network clustering for multivariate time series with an application to the US equity marketcited by 11
  14. 2023American Stories: A Large-Scale Structured Text Dataset of Historical U.S. Newspaperscited by 11
  15. 2024Season combinatorial intervention predictions with Salt & Pepercited by 11
  16. 2024FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioningcited by 11
  17. 2021Coordinating Narratives and the Capitol Riots on Parlercited by 10
  18. 2023Topology-Agnostic Detection of Temporal Money Laundering Flows in Billion-Scale Transactionscited by 10
  19. 2023Live Graph Lab: Towards Open, Dynamic and Real Transaction Graphs with NFTcited by 10
  20. 2021Scalable Community Detection via Parallel Correlation Clusteringcited by 9
  21. 2022Learning Hypergraphs From Signals With Dual Smoothness Priorcited by 9
  22. 2023Multi-agent Attacks for Black-box Social Recommendationscited by 9
  23. 2023Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detectioncited by 8
  24. 2023Transformer-Based Hierarchical Clustering for Brain Network Analysiscited by 8
  25. 2024The Local Interaction Basis: Identifying Computationally-Relevant and Sparsely Interacting Features in Neural Networkscited by 8
  26. 2024Geneverse: A collection of Open-source Multimodal Large Language Models for Genomic and Proteomic Researchcited by 8
  27. 2025SToFM: a Multi-scale Foundation Model for Spatial Transcriptomicscited by 8
  28. 2023CSGCL: Community-Strength-Enhanced Graph Contrastive Learningcited by 7
  29. 2023Normalized mutual information is a biased measure for classification and community detectioncited by 7
  30. 2025Hierarchical Lexical Graph for Enhanced Multi-Hop Retrievalcited by 7
  31. 2025SurveyG: A Multi-Agent LLM Framework with Hierarchical Citation Graph for Automated Survey Generationcited by 7
  32. 2026SuperLocalMemory: Privacy-Preserving Multi-Agent Memory with Bayesian Trust Defense Against Memory Poisoningcited by 7
  33. 2023Temporal Dynamics of Coordinated Online Behavior: Stability, Archetypes, and Influencecited by 6
  34. 2023PubGraph: A Large-Scale Scientific Knowledge Graphcited by 6
  35. 2023Synergistic Graph Fusion via Encoder Embeddingcited by 6
  36. 2025MegaRAG: Multimodal Knowledge Graph-Based Retrieval Augmented Generationcited by 6
  37. 2026A2RAG: Adaptive Agentic Graph Retrieval for Cost-Aware and Reliable Reasoningcited by 6
  38. 2021mlf-core: a framework for deterministic machine learningcited by 5

50 most cited of 379 All 379 (JSON)