Algorithm Deep Dive: Leiden Algorithm

A Bit of History

In 2019, V.A. Traag, L. Waltman, and N.J. van Eck from Leiden University published "From Louvain to Leiden: guaranteeing well-connected communities" in Scientific Reports. For over a decade, the Louvain Method (2008) was the uncontested gold standard for large-scale community detection across physics, sociology, and computational biology. However, Traag et al. discovered a startling flaw in Louvain's greedy aggregation mechanism: it frequently leaves communities internally disconnected—sometimes containing up to 25% disconnected sub-graphs in real-world benchmarks!

The Leiden Algorithm solved this systemic issue by introducing a fast local refinement phase and a queue-based node tracking mechanism that guarantees well-connected communities while executing substantially faster than Louvain.

Intuitive Analogy: The Island Merger Problem Imagine two distinct island nations connected by a single toll bridge. In the Louvain approach, as bridge workers leave, the algorithm notices that keeping both island populations under the same national administration still saves administrative costs on paper. So it merges them into a single state—even though citizens have no physical way to travel between the islands anymore! The Leiden approach acts as an urban planner that inspects internal transport links before forming a single administrative region, guaranteeing that every city within a state is actually reachable by road.

The Flaw in Louvain

Why did Louvain produce disconnected communities?

Bridge Node Migration: In Louvain, when a critical articulation or "bridge" node leaves a community to join another neighboring community, the remaining nodes in the original community become topologically disconnected into two or more components.
Global Formula Blindness: Even though no edge connects the separated sub-clusters, the modularity or Constant Potts Model (CPM) equation might still report a higher net score for keeping them under the same community label than splitting them into separate communities.
Permanent Aggregation Error: When Louvain contracts communities into super-nodes during its aggregation step (Phase 2), it turns the entire disconnected community into a single super-node. From that point onward, those disconnected regions are permanently glued together in all future hierarchy iterations.

Figure 1: Comparison between Louvain's permanent disconnected community contraction and Leiden's sub-community refinement phase.

Working Principle: Three Phases

Leiden addresses Louvain's structural weakness by splitting the process into three distinct phases:

Phase 1: Local Moving of Nodes: Nodes are moved between communities to optimize modularity or the Constant Potts Model (CPM). Unlike Louvain, Leiden uses a fast queue of affected nodes so only nodes whose neighborhood changed are re-evaluated, drastically improving speed.
Phase 2: Refinement of Communities (The Core Innovation): Communities found in Phase 1 are refined into well-connected sub-communities. Nodes are moved randomly into sub-communities within their main community, guaranteed not to disconnect them.
Phase 3: Aggregation Based on Refined Partition: Instead of aggregating based on the raw Phase 1 partition (which might be weakly connected), Leiden aggregates based on the refined sub-community partition.

Key Architectural Principle

By aggregating the graph based on the refined sub-communities rather than the raw primary communities, Leiden guarantees that every single super-node created in the aggregated graph represents a strictly connected component of the original graph!

In Phase 2, Leiden starts with a singleton partition of sub-communities inside each primary community $\mathcal{C}$. A node $u \in \mathcal{C}$ is considered for merging into a candidate sub-community $\mathcal{S} \subset \mathcal{C}$ probabilistically. The selection probability is proportional to the exponential change in modularity or CPM:

\Pr(u \to \mathcal{S}) = \frac{\exp\left( \frac{1}{\gamma} \Delta H(u \to \mathcal{S}) \right)}{\sum_{\mathcal{S}' \subset \mathcal{C}} \exp\left( \frac{1}{\gamma} \Delta H(u \to \mathcal{S}') \right)}

where $\gamma > 0$ is a randomness parameter and $\Delta H$ is the change in the quality function. Crucially, node $u$ is only allowed to merge into sub-community $\mathcal{S}$ if $\mathcal{S}$ is well-connected to the rest of $\mathcal{C}$, preventing the creation of disconnected sub-structures.

Worked Example

Let us trace the execution of the Leiden algorithm on a necked network consisting of two dense 4-node cliques $K_4^A$ and $K_4^B$ connected by a bottleneck bridge path $x \to y \to z$.

Figure 2: The step-by-step pipeline of Leiden: Local movement, random constrained refinement, and sub-community contraction.

Mathematical Formulation

The Leiden algorithm supports both traditional Modularity $Q$ and the Constant Potts Model (CPM) quality functions. Under CPM, the quality $H$ of a partition $\mathcal{P}$ is defined as:

H(\mathcal{P}) = \sum_{\mathcal{C} \in \mathcal{P}} \left( e_{\mathcal{C}} - \gamma \binom{|\mathcal{C}|}{2} \right)

where $e_{\mathcal{C}}$ is the number of internal edges in community $\mathcal{C}$, $|\mathcal{C}|$ is the number of nodes in $\mathcal{C}$, and $\gamma$ is the resolution parameter. Unlike modularity, CPM is scale-invariant and does not suffer from the classic resolution limit.

Complexity & Benchmarks

Leiden is both higher quality and faster than Louvain because of its queue-based update mechanism:

Metric	Louvain Method	Leiden Algorithm
Guaranteed Connected Communities?	No (up to 25% disconnected)	Yes (100% connected)
Node Re-evaluation Strategy	Full pass over all $V$ nodes per iteration	Fast Queue tracking affected neighborhoods
Empirical Runtime	Fast ($O(\|E\|)$ per level)	2x - 5x Faster than Louvain
Quality Metric Support	Primarily Modularity $Q$	Modularity $Q$ & Constant Potts Model (CPM)

Implementation

Below are production-ready implementations of Phase 1 fast queue-based tracking in Python, C++, and Java:

from collections import deque

class LeidenPhase1Queue:
    """
    Demonstrating Leiden's fast queue-based node movement strategy
    which avoids scanning unaffected nodes in Phase 1.
    """
    def __init__(self, n, adj, weights, m):
        self.n = n
        self.adj = adj
        self.weights = weights
        self.m = m
        self.community = list(range(n))
        self.degrees = [sum(weights.get(tuple(sorted((v, u))), 1) for u in adj[v]) for v in range(n)]
        self.comm_degrees = self.degrees[:]

    def run_phase1_fast_queue(self):
        # Queue initialized with all nodes
        q = deque(range(self.n))
        in_queue = [True] * self.n

        while q:
            u = q.popleft()
            in_queue[u] = False
            
            current_comm = self.community[u]
            self.comm_degrees[current_comm] -= self.degrees[u]

            # Find best community
            best_gain = 0
            best_comm = current_comm
            
            neighbor_comms = {}
            for v in self.adj[u]:
                w = self.weights.get(tuple(sorted((u, v))), 1)
                c = self.community[v]
                neighbor_comms[c] = neighbor_comms.get(c, 0) + w

            for c, w_to_c in neighbor_comms.items():
                gain = w_to_c - (self.comm_degrees[c] * self.degrees[u]) / (2 * self.m)
                if gain > best_gain:
                    best_gain = gain
                    best_comm = c

            self.comm_degrees[best_comm] += self.degrees[u]

            if best_comm != current_comm:
                self.community[u] = best_comm
                # Add neighbors not in queue back into queue!
                for v in self.adj[u]:
                    if not in_queue[v] and self.community[v] != best_comm:
                        q.append(v)
                        in_queue[v] = True

        return self.community

# Example Graph
adj = [[1,2],[0,2],[0,1,3],[2,4,5],[3,5],[3,4]]
weights = {(0,1):1,(0,2):1,(1,2):1,(2,3):1,(3,4):1,(3,5):1,(4,5):1}
leiden = LeidenPhase1Queue(6, adj, weights, m=7)
print("Leiden Fast Queue Communities:", leiden.run_phase1_fast_queue())

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

class LeidenPhase1 {
    int n;
    vector<vector<int>> adj;
    map<pair<int,int>, double> weights;
    double m;

public:
    LeidenPhase1(int n, vector<vector<int>>& adj, map<pair<int,int>, double>& weights, double m)
        : n(n), adj(adj), weights(weights), m(m) {}

    vector<int> runFastQueue() {
        vector<int> community(n);
        vector<double> degree(n, 0);
        for (int i = 0; i < n; ++i) {
            community[i] = i;
            for (int v : adj[i]) degree[i] += weights[minmax(i, v)];
        }
        vector<double> commDegree = degree;

        queue<int> q;
        vector<bool> inQueue(n, true);
        for (int i = 0; i < n; ++i) q.push(i);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            inQueue[u] = false;

            int currentComm = community[u];
            commDegree[currentComm] -= degree[u];

            map<int, double> neighborComms;
            for (int v : adj[u]) {
                double w = weights[minmax(u, v)];
                neighborComms[community[v]] += w;
            }

            double bestGain = 0;
            int bestComm = currentComm;

            for (auto& p : neighborComms) {
                int c = p.first;
                double wToC = p.second;
                double gain = wToC - (commDegree[c] * degree[u]) / (2 * m);
                if (gain > bestGain) {
                    bestGain = gain;
                    bestComm = c;
                }
            }

            commDegree[bestComm] += degree[u];

            if (bestComm != currentComm) {
                community[u] = bestComm;
                for (int v : adj[u]) {
                    if (!inQueue[v] && community[v] != bestComm) {
                        q.push(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        return community;
    }
};

int main() {
    int n = 6;
    vector<vector<int>> adj = {{1,2},{0,2},{0,1,3},{2,4,5},{3,5},{3,4}};
    map<pair<int,int>, double> weights = {
        {{0,1},1},{{0,2},1},{{1,2},1},{{2,3},1},{{3,4},1},{{3,5},1},{{4,5},1}
    };
    LeidenPhase1 leiden(n, adj, weights, 7);
    vector<int> comms = leiden.runFastQueue();
    cout << "Leiden Fast Queue Communities: ";
    for (int c : comms) cout << c << " ";
    cout << endl;
    return 0;
}

import java.util.*;

public class LeidenPhase1 {
    private int n;
    private List<List<Integer>> adj;
    private Map<List<Integer>, Double> weights;
    private double m;

    public LeidenPhase1(int n, List<List<Integer>> adj, Map<List<Integer>, Double> weights, double m) {
        this.n = n; this.adj = adj; this.weights = weights; this.m = m;
    }

    public int[] runFastQueue() {
        int[] community = new int[n];
        double[] degree = new double[n];
        for (int i = 0; i < n; i++) {
            community[i] = i;
            for (int v : adj.get(i)) {
                degree[i] += weights.get(Arrays.asList(Math.min(i, v), Math.max(i, v)));
            }
        }
        double[] commDegree = degree.clone();

        Deque<Integer> q = new ArrayDeque<>();
        boolean[] inQueue = new boolean[n];
        for (int i = 0; i < n; i++) {
            q.add(i);
            inQueue[i] = true;
        }

        while (!q.isEmpty()) {
            int u = q.poll();
            inQueue[u] = false;

            int currentComm = community[u];
            commDegree[currentComm] -= degree[u];

            Map<Integer, Double> neighborComms = new HashMap<>();
            for (int v : adj.get(u)) {
                double w = weights.get(Arrays.asList(Math.min(u, v), Math.max(u, v)));
                neighborComms.put(community[v], neighborComms.getOrDefault(community[v], 0.0) + w);
            }

            double bestGain = 0;
            int bestComm = currentComm;

            for (var entry : neighborComms.entrySet()) {
                int c = entry.getKey();
                double wToC = entry.getValue();
                double gain = wToC - (commDegree[c] * degree[u]) / (2 * m);
                if (gain > bestGain) {
                    bestGain = gain;
                    bestComm = c;
                }
            }

            commDegree[bestComm] += degree[u];

            if (bestComm != currentComm) {
                community[u] = bestComm;
                for (int v : adj.get(u)) {
                    if (!inQueue[v] && community[v] != bestComm) {
                        q.add(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        return community;
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> adj = Arrays.asList(
            Arrays.asList(1,2), Arrays.asList(0,2), Arrays.asList(0,1,3),
            Arrays.asList(2,4,5), Arrays.asList(3,5), Arrays.asList(3,4)
        );
        Map<List<Integer>, Double> weights = new HashMap<>();
        int[][] edges = {{0,1},{0,2},{1,2},{2,3},{3,4},{3,5},{4,5}};
        for (int[] e : edges) weights.put(Arrays.asList(Math.min(e[0], e[1]), Math.max(e[0], e[1])), 1.0);

        LeidenPhase1 leiden = new LeidenPhase1(n, adj, weights, 7.0);
        System.out.println("Leiden Fast Queue Communities: " + Arrays.toString(leiden.runFastQueue()));
    }
}

Real-World Applications

1. Single-Cell RNA Sequencing (scRNA-seq) Cell Clustering

In computational genomics, tools like Seurat (R) and Scanpy (Python) construct nearest-neighbor graphs representing millions of single cells. The Leiden algorithm is the universal industry standard for identifying distinct cell types because disconnected communities would falsely combine distinct cell lineages!

2. Financial Fraud Detection & Anti-Money Laundering (AML)

Transaction graphs link bank accounts, devices, and IP addresses. Identifying ring-fraud syndicates requires accurate connectivity guarantees. Leiden ensures that every detected fraud cluster is an actual connected ring of actors rather than spurious distant entities.

Exercises

Practice Problems

Construct a 7-node graph where the Louvain method creates a disconnected community, and manually trace how Leiden's refinement phase splits it.
Explain mathematically why queue-based node selection in Phase 1 speeds up Leiden compared to Louvain's full sequential passes.
Compare the Constant Potts Model (CPM) quality function with standard Modularity $Q$ in Leiden regarding the resolution limit.

Hint: Think about how CPM treats community size independently of the total edge count $m$.

Limitations

Randomization & Parameter Sensitivity

While Leiden guarantees 100% connected communities, its sub-community refinement phase is randomized. Consequently, running Leiden twice on the same network with identical settings may yield slightly different partition boundaries unless a fixed random seed is set. Furthermore, when using CPM, selecting an appropriate resolution parameter $\gamma$ requires domain knowledge.

Cookie Consent

Leiden Algorithm

Contents

A Bit of History

The Flaw in Louvain

Working Principle: Three Phases

Key Architectural Principle

Sub-community Refinement

Worked Example

Mathematical Formulation

Complexity & Benchmarks

Implementation

Real-World Applications

1. Single-Cell RNA Sequencing (scRNA-seq) Cell Clustering

2. Financial Fraud Detection & Anti-Money Laundering (AML)

Exercises

Practice Problems

Limitations

Randomization & Parameter Sensitivity

Cookie Consent

Leiden Algorithm

Contents

A Bit of History

The Flaw in Louvain

Working Principle: Three Phases

Key Architectural Principle

Sub-community Refinement

Worked Example

Mathematical Formulation

Complexity & Benchmarks

Implementation

Real-World Applications

1. Single-Cell RNA Sequencing (scRNA-seq) Cell Clustering

2. Financial Fraud Detection & Anti-Money Laundering (AML)

Exercises

Practice Problems

Limitations

Randomization & Parameter Sensitivity

Related Deep Dives

Graph Theory Series Index

Louvain Method

Part 25: Network Science