From Louvain to Leiden: guaranteeing well-connected communities

Vincent Traag; Ludo Waltman; Nees Jan van Eck

Source-linked AI summary

From Louvain to Leiden: guaranteeing well-connected communities

Vincent Traag, Ludo Waltman, Nees Jan van Eck

arXiv:1810.08473v3Oct 19, 2018cs.SIphysics.soc-ph

TL;DR

The Louvain algorithm can produce arbitrarily badly connected or disconnected communities. This paper introduces Leiden, which guarantees connected communities and, in experiments, is faster and produces higher-quality partitions than Louvain.

Problem
Louvain may yield arbitrarily badly connected communities, including internally disconnected ones, undermining community structure quality.
Method
The Leiden algorithm refines Louvain with local moving, partition refinement, and network aggregation to improve partition quality and connectivity guarantees.
Results
Leiden guarantees connected communities, converges iteratively to locally optimal assignments, and generally outperforms Louvain in speed and partition quality.
Takeaways & Limitations
The paper concludes that Leiden is strongly preferable to Louvain for practical community detection.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Community detection seeks dense groups in complex networks, with modularity and the fast, widely used Louvain algorithm among prominent approaches. The paper identifies severe connectivity defects in Louvain and introduces Leiden to provide faster, better partitions with explicit guarantees.

Background: Community detection identifies relatively dense groups in complex networks whose modular structure is usually unknown beforehand.Detecting such communities is presented as an important problem.
Related work: Louvain is a popular modularity-optimisation algorithm found to be among the fastest and best-performing methods in comparative analyses.Modularity optimisation is NP-hard, motivating heuristic algorithms such as Louvain.
Problem: Louvain may produce arbitrarily badly connected or internally disconnected communities for both modularity and CPM.The paper presents this as a major problem beyond modularity’s known resolution limit.
Contribution: The Leiden algorithm addresses this shortcoming by being faster, finding better partitions, and providing explicit guarantees and bounds.The paper names the algorithm Leiden and explains its main ideas intuitively in the main text.

II. LOUVAIN ALGORITHM

The Louvain algorithm optimises a quality function through local node moves and network aggregation. It usually starts from singleton communities, though it can also be iterated from previously identified partitions.

Algorithm phases: Louvain optimises modularity or CPM in two phases: local node moving followed by network aggregation.Nodes move to communities yielding the largest quality-function increase, after which each community becomes part of an aggregate network.
Initialization: Usually, Louvain starts from a singleton partition in which every node forms its own community.
Algorithm behavior: A local node move can leave a community internally disconnected even when its remaining nodes are locally optimally assigned.In the illustrated case, moving node 0 disconnects the red community while nodes 1–6 remain in it.
Initialization: Louvain can start from a different partition and run through multiple consecutive iterations using each identified partition as the next starting point.

A. Badly connected communities

The Louvain algorithm can produce communities that are arbitrarily badly connected, including internally disconnected communities. Iterating Louvain can worsen this problem because moving bridge nodes may disconnect their former communities.

Louvain may identify internally disconnected communities whose parts connect only through paths outside the community.The problem occurs in practice, not merely as a theoretical possibility.
A node moved between communities can serve as a bridge, disconnecting its former community while the remaining nodes stay assigned there.Those nodes may remain sufficiently strongly connected to the old community despite its disconnection.
Louvain may find communities that are connected only in a very weak sense, yielding arbitrarily badly connected communities.
In its standard form, Louvain guarantees only that no communities can be merged, whereas iteration additionally guarantees that no nodes can be moved.These guarantees concern separation and node assignments, not community connectivity.
Iterating Louvain aggravates badly connected communities because later iterations can again move bridge nodes.

III. LEIDEN ALGORITHM

The Leiden algorithm is introduced as a Louvain-based method that guarantees well-connected communities. It combines a refinement phase, randomized node mergers, and a fast local move procedure to improve the algorithm’s community construction and efficiency.

Algorithm overview: The Leiden algorithm guarantees that communities are well connected while building on the smart local move algorithm and other Louvain improvements.It also incorporates faster local moving and moving nodes to random neighbours.
Refinement phase: The refinement phase splits communities from the local-moving partition P into subcommunities before constructing the aggregate network.The aggregate network uses the refined partition Prefined, while its initial partition is based on P.
Refinement phase: Refined communities are formed by locally merging nodes only within communities of P and only when the node and target community are sufficiently well connected.The refined partition initially places every node in its own community.
Randomized merging: The Leiden algorithm uses randomized refinement mergers, selecting any quality-improving community with probabilities influenced by the quality increase and parameter θ > 0.Random selection allows broader exploration of the partition space.
Local moving: Unlike Louvain, Leiden uses a fast local move procedure rather than repeatedly revisiting nodes that cannot be moved to improve the quality function.Louvain continues visiting all nodes until no quality-increasing movements remain.

A. Guarantees

The Leiden algorithm guarantees increasingly strong structural properties as it is iterated: communities are γ-separated and γ-connected after each iteration, while stable iterations additionally ensure local node optimality and subpartition γ-density. Continued iteration converges to partitions whose communities are uniformly γ-dense and subset optimal.

After each iteration: After each iteration, all Leiden communities are γ-separated and γ-connected.γ refers to the resolution parameter in the optimized quality function, which may be modularity or CPM.
After each iteration: Unlike Louvain, Leiden guarantees γ-connectivity, a stronger property than ordinary connectivity.Louvain guarantees γ-separation but does not guarantee ordinary connectivity or γ-connectivity.
After a stable iteration: After a stable iteration, all nodes are locally optimally assigned and all communities are subpartition γ-dense.Louvain also guarantees node optimality after a stable iteration, but not subpartition γ-density.
After continued iteration: Continued Leiden iteration converges to a partition in which all communities are uniformly γ-dense and subset optimal.Uniform γ-density prevents subsets from being separated from their communities, while subset optimality means all community subsets are locally optimally assigned.
After continued iteration: Unlike Louvain, Leiden may continue improving after a stable iteration before reaching its converged partition.For Louvain, all subsequent iterations remain stable after a stable iteration.

IV. EXPERIMENTAL ANALYSIS

This section experimentally compares the practical performance of the Leiden and Louvain algorithms. The experiments use six empirical networks and evaluate Leiden with controlled randomness in its refinement phase.

Experimental setup: The experiments compare the practical performance of the Leiden and Louvain algorithms.The comparison follows the preceding claim that Leiden may be faster because it uses a fast local move approach.
Experimental setup: All experiments ran on a computer with 64 Intel Xeon E5-4667v3 2GHz CPUs and 1TB internal memory.
Experimental setup: The experiments used θ = 0.01 for Leiden’s refinement-phase randomness, while values from roughly [0.0005, 0.1] also produced reasonable results.This range allows some, but not too much, randomness.

A. Badly connected communities

Louvain frequently produces badly connected communities, with disconnected communities becoming more common across later iterations. Leiden guarantees connected communities, although its first iteration can still yield badly connected communities.

Empirical results: 23%, 16% and 14%: Louvain’s first iteration produced badly connected communities on average in Amazon, DBLP and Web UK, respectively.Disconnected communities were usually around 1%, except Web of Science, where more than 5% were disconnected.
Empirical results: Later Louvain iterations increased the percentage of disconnected communities, even as modularity increased.The second iteration showed a large increase, after which the percentage remained fairly stable.
Empirical results: After four Louvain iterations, Web UK had 8% disconnected communities and Amazon had 5% disconnected communities.Amazon still had 25% badly connected communities, while Web UK had twice as many badly connected as disconnected communities.
Interpretation: Louvain’s disconnected-community rates can mask the broader problem that it finds arbitrarily badly connected communities.The issue is pervasive in practice, despite disconnected communities often being relatively uncommon in the first iteration.
Leiden comparison: Leiden guarantees that all communities are connected, but its first iteration can perform worse than Louvain on the percentage of badly connected communities.Leiden was specifically designed to address badly connected communities, while still potentially yielding some badly connected communities.

B. Benchmark networks

On benchmark networks, Leiden is faster than Louvain and increasingly outperforms it as partitions become more difficult. Leiden also continues improving partition quality across iterations, while Louvain quickly plateaus.

Speed: In the most difficult benchmark case, µ = 0.9, Louvain requires almost 2.5 days, whereas Leiden needs fewer than 10 minutes.This comparison concerns the first iteration on networks with n = 10^7 nodes.
Partition quality: As µ increases, Leiden starts to outperform Louvain in partition quality, although the differences remain small when both approaches find near-optimal partitions.At lower µ values, both algorithms determine the correct partition in two iterations and the quality difference is negligible.
Speed: Leiden becomes orders of magnitude faster than Louvain at higher mixing values, reaching 10–100 times faster runtimes for the largest networks.For lower mixing values, Leiden is about twice as fast; its advantage grows as the mixing parameter increases.
Iterative performance: Across iterations, Leiden keeps finding better partitions, especially at higher µ, while Louvain quickly reaches a state where it cannot improve further.Several Leiden iterations can be performed before Louvain finishes its first iteration.

C. Empirical networks … Appendix A: Pseudo-code and mathematical notation

The empirical-network analysis finds Leiden faster and produces better partitions than Louvain, while the paper formalizes Leiden’s connectivity guarantees and supporting notation, contributions, and disclosures.

C. Empirical networks: Leiden is significantly faster than Louvain on empirical networks, running roughly 2–20 times faster in the first iteration.For Amazon and IMDB, the first iteration is only about 1.6 times faster; the difference is especially large for larger networks.
C. Empirical networks: For all empirical networks, Leiden identifies substantially better partitions than Louvain, which quickly converges while Leiden continues improving each iteration.The quality improvement is larger for empirical than benchmark networks, and Leiden keeps improving beyond the first 10 iterations.
V. DISCUSSION: The paper identifies Louvain’s major shortcoming as producing communities that can be arbitrarily badly connected.Community detection algorithms must be both fast and capable of providing high-quality results.
V. DISCUSSION: Leiden addresses this defect by guaranteeing connected communities and, under iteration, convergence to partitions whose subsets are locally optimally assigned.The paper presents these as explicit guarantees of the new algorithm.
AUTHOR CONTRIBUTIONS STATEMENT: All authors conceived the algorithm and contributed to the source code; VAT performed the experiments, VAT and LW wrote the manuscript, and NJvE reviewed it.The author initials and responsibilities are reported in the contribution statement.
ADDITIONAL INFORMATION: The authors disclose acting as bibliometric consultants to CWTS B.V., which uses community detection algorithms in commercial products and services.This statement appears under competing interests.
Appendix A: Pseudo-code and mathematical notation: Appendix A supplies pseudo-code for Louvain and Leiden and defines notation for partitions, quality changes, recursive sets, flattening, and community connectivity.It introduces graphs G = (V, E), partitions into disjoint communities, and flattening for translating aggregate-graph partitions to base graphs.
Appendix A: Pseudo-code and mathematical notation: The appendix bases proofs on CPM, explains its advantages over modularity, extends results to modularity, and defines iterative sequences of Louvain or Leiden partitions.It also formalizes connected and disconnected communities through induced subgraphs and initializes iteration with a singleton partition.

Appendix B: Disconnected communities in the Louvain algorithm · Appendix C: Reachability of optimal partitions · 1. Non-decreasing move sequences

The appendices show that Louvain can produce disconnected communities that cannot later be repaired, while Leiden’s theoretical basis is that every optimal partition is reachable through a non-decreasing move sequence. Specifically, any optimal partition can be reached from singletons in n − |P∗| steps, whereas greedy sequences cannot necessarily reach all optimal partitions.

Appendix B: Disconnected communities in the Louvain algorithm: Louvain can terminate with a disconnected community even though all involved nodes are locally optimally assigned.The example concludes that later Louvain stages cannot repair the disconnected community.
Appendix B: Disconnected communities in the Louvain algorithm: The disconnected-community construction extends from weighted to unweighted graphs and has analogous versions for both CPM and modularity.The weighted example can be viewed as an aggregate graph of an unweighted base graph; modularity calculations are more complex because they depend on m.
Appendix C: Reachability of optimal partitions: The appendix studies whether greedy and non-decreasing move sequences can reach all optimal partitions.It shows that some optimal partitions lack a greedy sequence from which they can be reached, while non-decreasing sequences can reach optimal partitions.
Appendix C: Reachability of optimal partitions: A move sequence changes one node’s community at each step, with non-decreasing sequences satisfying H(Pt+1) ≥ H(Pt) and greedy sequences choosing the maximizing move.Greedy sequences are necessarily non-decreasing, but non-decreasing sequences need not be greedy.
1. Non-decreasing move sequences: For any graph and optimal partition P∗, a non-decreasing move sequence exists from the singleton partition to P∗.This result supplies the reachability basis for the Leiden algorithm’s asymptotic guarantees.
1. Non-decreasing move sequences: n − |P∗| steps suffice to reach any optimal partition P∗ from the singleton partition.Theorem 1 specifies τ = n − |P∗| for the sequence length.
1. Non-decreasing move sequences: The proof constructs each target community by repeatedly merging nodes while preserving non-decreasing quality, then applies the construction to every community.A community C∗ is reached in |C∗| − 1 steps, and the total number of steps is obtained by summing across target communities.

2. Greedy move sequences · Appendix D: Guarantees of the Leiden algorithm

Greedy move sequences can be unable to reach an optimal partition, because strongly connected nodes may be kept together despite belonging to different optimal communities. The Leiden algorithm’s guarantees are formalized through increasingly strong properties, with γ-separation and γ-connectivity guaranteed in every iteration and stronger properties guaranteed in stable iterations or asymptotically.

2. Greedy move sequences: A counterexample shows that no greedy move sequence can reach the optimal partition of some graphs.The greedy sequence always reaches one partition, whereas a different partition is optimal.
2. Greedy move sequences: Strong connections can force two nodes into the same greedy community even when the optimal partition assigns them to different communities.In the counterexample, the nodes’ joint benefit exceeds the alternatives available through greedy moves.
2. Greedy move sequences: With γ = 1, greedy moves always produce three communities, while the optimal partition has two communities.The greedy partition is forced because joining nodes 0 and 1 yields a benefit of 3 − γ = 2, exceeding the competing benefit of 3/2.
Appendix D: Guarantees of the Leiden algorithm: The Leiden guarantees rely partly on algorithmic randomness, requiring θ > 0, and are defined for flat partitions P of graphs G = (V, E).The appendix introduces properties from relatively weak to stronger guarantees before stating their algorithmic consequences.
Appendix D: Guarantees of the Leiden algorithm: The appendix defines γ-separation, γ-connectivity, subpartition γ-density, node optimality, uniform γ-density, and subset optimality as increasingly related partition properties.Subset optimality is the strongest property and subsumes the others; uniform γ-density implies subpartition γ-density, which implies γ-connectivity.
Appendix D: Guarantees of the Leiden algorithm: Subset optimality requires every subset of each community to have no beneficial move to another community or the empty set.Restricting the subset or destination in this definition yields uniform γ-density, node optimality, or γ-separation.
Appendix D: Guarantees of the Leiden algorithm: γ-separation and γ-connectivity are guaranteed in each Leiden iteration.The appendix states that subpartition γ-density and node optimality are guaranteed in every stable iteration, while the remaining properties hold asymptotically.

1. Guarantees in each iteration · 2. Guarantees in stable iterations

The Leiden algorithm guarantees γ-separation and γ-connectivity after every iteration, even when its input partition is disconnected. Under strictly positive-improvement moves, stable Leiden partitions are subpartition γ-dense and node optimal, while stable Louvain iterations remain stable thereafter.

1. Guarantees in each iteration: MoveNodesFast ensures that disconnected nodes remain queued for evaluation, supporting the iteration-level connectivity guarantee.Lemma 2 states that every node is either still queued or connected to another node in its current community.
1. Guarantees in each iteration: Theorem 4 guarantees that each Leiden iteration produces a γ-separated partition.For a flat input partition Pt, the output Pt+1 = Leiden(G, Pt) is γ-separated.
1. Guarantees in each iteration: Theorem 5 guarantees that each Leiden iteration produces a γ-connected partition.The proof establishes γ-connectivity through the aggregate-graph construction and its decomposition.
1. Guarantees in each iteration: A single Leiden iteration yields a γ-connected partition even when the input partition is disconnected.The connectivity guarantee does not require Pt itself to be connected.
2. Guarantees in stable iterations: Under strictly positive improvements, a stable Leiden iteration satisfies Pt+1 = Pt and produces a subpartition γ-dense partition.Equal-quality node movements are rejected so that unchanged quality implies an unchanged partition.
2. Guarantees in stable iterations: A stable Leiden partition is node optimal, even though subpartition γ-density alone does not imply node optimality.If any node had a positive-gain move to another community or an empty community, MoveNodesFast would change the partition.
2. Guarantees in stable iterations: When Louvain reaches a stable iteration, all subsequent iterations remain stable because its partition is γ-separated and node optimal.Thus, if Pt+1 = Pt, then Pτ = Pt for all τ ≥ t.

3. Asymptotic guarantees

The Leiden algorithm eventually reaches an asymptotically stable partition because it makes only strict improvements and the graph has finitely many partitions. For flat partitions, asymptotic stability is equivalent to subset optimality and implies uniform γ-density.

Asymptotic guarantees: The Leiden algorithm eventually stabilizes at a partition that remains unchanged in all subsequent iterations.Strict improvements prevent revisiting partitions, while the finite number of possible partitions ensures eventual stabilization.
Asymptotic guarantees: As long as some community subset is not optimally assigned, MergeNodesSubset can identify it and MoveNodesFast can move it to improve the partition.The process stops when all community subsets are optimally assigned.
Asymptotic guarantees: A flat partition is asymptotically stable if and only if it is subset optimal.This is the central equivalence established by Theorem 11.
Asymptotic guarantees: An asymptotically stable flat partition is uniformly γ-dense.This follows because subset optimality implies uniform γ-density.

Appendix E: Bounds on optimality

Appendix E proves that the quality of a uniformly γ-dense partition upper-bounds the quality of an optimal partition, with extensions to weighted graphs and modularity. The result applies directly only to unweighted graphs and does not establish an a priori lower bound on uniformly γ-dense partitions.

Unweighted-graph bound: A uniformly γ-dense partition provides an upper bound on the quality of an optimal partition.The theorem is stated for unweighted graphs.
Proof framework: The proof compares partitions through their intersection, whose subsets capture the common refinement of both partitions.A lemma expresses the difference in partition quality using this intersection.
Extensions: For weighted graphs, the appendix gives an analogous upper bound involving the maximum edge weight.The maximum edge weight is denoted by ¯w = maxi,j wi,j.
Extensions: For modularity, the unweighted-graph bound requires rescaling the resolution parameter by 2m and remains additive rather than multiplicative.Depending on the partition, the additive bound may improve on an SDP-based bound.
Open problem: The theorem does not provide an a priori bound on the minimal quality of a uniformly γ-dense partition.Finding such an a priori bound remains an open problem.