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 gold standard for large-scale community detection. However, Traag et al. discovered that Louvain's greedy node movement could split a community into disconnected components, leaving up to 25% of communities internally disconnected in real-world networks! The Leiden Algorithm solved this by adding an explicit refinement phase and fast queue-based node tracking.

The Flaw in Louvain

Why did Louvain produce disconnected communities?

In Louvain, when a bridge node leaves a community, two distant sub-clusters in that community become topologically disconnected.
However, if the modularity formula still finds that keeping them in the same community label yields a higher overall score than creating new individual communities, Louvain keeps them assigned to the same community ID!
When Louvain aggregates these nodes in Phase 2, it contracts a disconnected "community" into a single super-node, permanently hiding the topological disconnect.

Working Principle: Three Phases

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

Phase 1: Local Moving of Nodes: Nodes are moved between communities to optimize modularity or Constant Potts Model (CPM). Unlike Louvain, Leiden uses a fast queue of affected nodes so only nodes whose neighborhood changed are re-evaluated.
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 Insight

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

In the refinement phase, a node $u$ inside community $\mathcal{C}$ can merge into a sub-community $\mathcal{S} \subset \mathcal{C}$ probabilistically based on the modularity delta $\Delta Q$:

$$\Pr(u \to \mathcal{S}) \propto \exp\left( \frac{\Delta Q}{\gamma} \right)$$

where $\gamma$ is a tuning parameter. This randomized, constrained movement splits poorly-connected regions before the graph is aggregated, preventing disconnected sub-graphs from merging.

Worked Example

Consider two dense cliques $A$ and $B$ connected by a single bottleneck path $x \to y \to z$:

In Louvain, $y$ might move to clique $A$, and $z$ might move to clique $B$. If $x$ later leaves, $A$ and $B$ might remain labeled as one community even if no path connects them!
In Leiden, after Phase 1 identifies the candidate community $\{A, x, y, z, B\}$, Phase 2's refinement discovers that $A$ and $B$ have no direct edges. It refines the group into two sub-communities $\{A, x, y\}$ and $\{z, B\}$.
In Phase 3, Leiden creates two separate super-nodes for $\{A, x, y\}$ and $\{z, B\}$, preserving proper topological connectivity.

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	Fast Queue of changed node neighborhoods
Empirical Speed	Fast ($O(E)$ per level)	2x - 5x Faster than Louvain

Implementation

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

Case Study

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

In computational biology, single-cell analysis tools (such as Seurat and Scanpy) represent cell similarity graphs with millions of single cells. The Leiden algorithm is the universal standard for clustering single cells into cell types because internally disconnected clusters would misclassify cell lineages!

BioinformaticsscRNA-seq

Exercises

Construct a 7-node graph where the Louvain method creates a disconnected community, and show how Leiden's refinement phase fixes it.
Explain how queue-based node selection in Phase 1 speeds up Leiden compared to Louvain's full scans.
Compare the Constant Potts Model (CPM) quality function with standard Modularity $Q$ in Leiden.
Challenge: Implement Phase 2 (Sub-community refinement) with probabilistic node assignment.

Limitations

Randomization & Resolution Limit

While Leiden guarantees 100% connected communities, its sub-community refinement phase is non-deterministic (randomized). Additionally, if configured to optimize standard modularity $Q$, it still inherits modularity's resolution limit (failing to find tiny communities in massive graphs), which is why CPM (Constant Potts Model) is often preferred for multi-scale analysis.

Cookie Consent

Leiden Algorithm

Contents

A Bit of History

The Flaw in Louvain

Working Principle: Three Phases

Key Insight

Sub-community Refinement

Worked Example

Complexity & Benchmarks

Implementation

Real-World Applications

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

Exercises

Limitations

Randomization & Resolution Limit

Cookie Consent

Leiden Algorithm

Contents

A Bit of History

The Flaw in Louvain

Working Principle: Three Phases

Key Insight

Sub-community Refinement

Worked Example

Complexity & Benchmarks

Implementation

Real-World Applications

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

Exercises

Limitations

Randomization & Resolution Limit

Related Deep Dives

Graph Theory Series

Louvain Method

Part 25: Network Science