Louvain Method

A Bit of History

Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre — researchers affiliated with the Université catholique de Louvain in Belgium, which gives the method its name — published "Fast Unfolding of Communities in Large Networks" in 2008, introducing a community-detection algorithm that scales to networks with tens of millions of vertices, in dramatic contrast to the Girvan-Newman algorithm's far more limited practical scale from the earlier deep dive.

Modularity

Both this algorithm and Girvan-Newman ultimately optimize the same quality measure, modularity \(Q\), which compares the actual density of edges within proposed communities against what would be expected in a random graph with the same degree sequence (recalling the Havel-Hakimi degree-sequence deep dive):

$$Q = \frac{1}{2m}\sum_{i,j}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)$$

where \(A_{ij}\) is the adjacency matrix, \(k_i\) is vertex \(i\)'s degree, \(m\) is the total edge count, and \(\delta(c_i,c_j)\) is 1 if vertices \(i\) and \(j\) are in the same community and 0 otherwise. Higher modularity means "more edges within communities than random chance would predict" — exactly the intuitive notion of well-separated community structure.

Working Principle: Two Phases

The Louvain method alternates between two phases until modularity stops improving:

1. Phase 1 (local moving): starting with every vertex in its own singleton community, repeatedly consider each vertex in turn and evaluate the modularity gain from moving it into each of its neighbors' communities, applying whichever single move yields the largest positive gain (or leaving it in place if no move helps). Repeat this scan over all vertices until no further single-vertex move improves modularity.
2. Phase 2 (aggregation): collapse every community discovered in Phase 1 into a single "super-vertex," with edges between communities becoming weighted edges between super-vertices (and internal community edges becoming self-loops). Return to Phase 1 on this smaller, coarser graph.

These two phases repeat, producing a natural hierarchy of community structure at increasingly coarse scales, until a full pass produces no further modularity improvement.

Worked Example

On a network with two obvious dense clusters loosely connected by a few edges, Phase 1 quickly merges vertices within each cluster into their own community (since moving a vertex to join its densely-connected neighbors' community yields a large positive modularity gain), typically converging to exactly the two intuitive clusters after just one or two scans. Phase 2 then collapses each cluster into a single super-vertex; since only two super-vertices remain, connected by comparatively few aggregated inter-community edges, running Phase 1 again on this tiny 2-vertex graph produces no further improvement, and the algorithm terminates having found the same two communities Girvan-Newman would also find — but reaching that answer via bottom-up assembly rather than top-down cutting.

Complexity Analysis

Each Phase 1 scan touches each edge a small number of times, and empirically the number of phase-1/phase-2 rounds needed is small (often a small constant) even for very large graphs:

$$\text{Time: } O(E) \text{ per level (empirically, near-linear overall)}$$

This near-linear practical performance — a dramatic contrast with Girvan-Newman's \(O(VE^2)\) — is precisely why the Louvain method (and its refined successor, the Leiden algorithm, developed later to fix certain edge cases where Louvain can produce disconnected "communities") became the default community-detection tool for networks with millions of vertices.

Implementation

def louvain_phase1(n, adj, weights, m):
    """
    Simplified single-level Louvain local-moving phase (Phase 1 only, no aggregation).
    n: vertices. adj[v]: list of neighbors. weights[(u,v)]: edge weight. m: total edge weight.
    Returns a community assignment list.
    """
    community = list(range(n))  # start with every vertex in its own community
    degree = [sum(weights.get(tuple(sorted((v, u))), 1) for u in adj[v]) for v in range(n)]
    community_degree = degree[:]

    improved = True
    while improved:
        improved = False
        for v in range(n):
            best_gain, best_community = 0, community[v]
            current_community = community[v]

            # Tentatively remove v from its current community
            community_degree[current_community] -= degree[v]

            neighbor_communities = {}
            for u in adj[v]:
                w = weights.get(tuple(sorted((v, u))), 1)
                neighbor_communities[community[u]] = neighbor_communities.get(community[u], 0) + w

            for c, edge_weight_to_c in neighbor_communities.items():
                gain = edge_weight_to_c - (community_degree[c] * degree[v]) / (2 * m)
                if gain > best_gain:
                    best_gain, best_community = gain, c

            community_degree[best_community] += degree[v]
            if best_community != current_community:
                improved = True
            community[v] = best_community

    return community

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}
m = sum(weights.values())
print(louvain_phase1(6, adj, weights, m))

// Simplified single-level Louvain local-moving phase (Phase 1 only).
#include <vector>
#include <map>
#include <iostream>
using namespace std;

vector<int> louvainPhase1(int n, vector<vector<int>>& adj, map<pair<int,int>,double>& weights, double m) {
    vector<int> community(n);
    for (int i = 0; i < n; i++) community[i] = i;

    vector<double> degree(n, 0);
    for (int v = 0; v < n; v++)
        for (int u : adj[v]) degree[v] += weights[minmax(v, u)];

    vector<double> communityDegree = degree;

    bool improved = true;
    while (improved) {
        improved = false;
        for (int v = 0; v < n; v++) {
            int currentCommunity = community[v];
            communityDegree[currentCommunity] -= degree[v];

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

            double bestGain = 0;
            int bestCommunity = currentCommunity;
            for (auto& [c, edgeWeightToC] : neighborCommunities) {
                double gain = edgeWeightToC - (communityDegree[c] * degree[v]) / (2 * m);
                if (gain > bestGain) { bestGain = gain; bestCommunity = c; }
            }

            communityDegree[bestCommunity] += degree[v];
            if (bestCommunity != currentCommunity) improved = true;
            community[v] = bestCommunity;
        }
    }
    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}
    };
    double m = 7;
    auto result = louvainPhase1(n, adj, weights, m);
    for (int c : result) cout << c << " ";
    return 0;
}

import java.util.*;

class Louvain {
    static int[] phase1(int n, List<List<Integer>> adj, Map<List<Integer>, Double> weights, double m) {
        int[] community = new int[n];
        for (int i = 0; i < n; i++) community[i] = i;

        double[] degree = new double[n];
        for (int v = 0; v < n; v++)
            for (int u : adj.get(v)) degree[v] += weights.get(Arrays.asList(Math.min(v,u), Math.max(v,u)));

        double[] communityDegree = degree.clone();

        boolean improved = true;
        while (improved) {
            improved = false;
            for (int v = 0; v < n; v++) {
                int currentCommunity = community[v];
                communityDegree[currentCommunity] -= degree[v];

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

                double bestGain = 0;
                int bestCommunity = currentCommunity;
                for (var entry : neighborCommunities.entrySet()) {
                    int c = entry.getKey();
                    double gain = entry.getValue() - (communityDegree[c] * degree[v]) / (2 * m);
                    if (gain > bestGain) { bestGain = gain; bestCommunity = c; }
                }

                communityDegree[bestCommunity] += degree[v];
                if (bestCommunity != currentCommunity) improved = true;
                community[v] = bestCommunity;
            }
        }
        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(e[0], e[1]), 1.0);
        System.out.println(Arrays.toString(phase1(n, adj, weights, 7)));
    }
}

Real-World Applications

Exercises

1. Trace through Phase 1 by hand on a small 6-vertex graph with two obvious triangular clusters, confirming vertices converge into the two intuitive communities.
2. Explain in your own words what Phase 2's aggregation step accomplishes, and why repeating Phase 1 on the aggregated graph can reveal a coarser level of community structure.
3. Compare the modularity formula's \(\frac{k_i k_j}{2m}\) term to what it represents (the expected number of edges between \(i\) and \(j\) under random reconnection) and explain why subtracting it rewards "more edges than random chance" community structure.
4. Challenge: Research the Leiden algorithm (a later refinement of Louvain) and summarize the specific issue with disconnected communities that it was designed to fix.

Limitations