Louvain Algorithm, in depth: modularity from first principles, the move gain, a hand trace, an implementation, the resolution limit and the Leiden fix

Modularity: the score being maximised

Louvain maximises a score called modularity, so start there. Take an undirected graph with total edge weight m. Node i has weighted degree k_i, the sum of the weights of its edges. Modularity compares the edge weight that falls inside communities with the weight you would expect there if edges were rewired at random while every node kept its degree:

Q = sum over communities c of [ Sigma_in(c) / (2m)  -  gamma * (Sigma_tot(c) / (2m))^2 ]

Sigma_in(c)  = sum of k-weights of edges inside c, each edge counted from both ends (2 x weight)
Sigma_tot(c) = sum of degrees k_i of the nodes in c
gamma        = resolution parameter, 1 in the classic definition

The first term is the fraction of edge endpoints that land inside the community. The second is the fraction you would expect under the random-rewiring null model, because a random endpoint lands in c with probability Sigma_tot(c)/2m. A good community has far more inner weight than its degree alone explains.

Three facts about Q matter in practice. Putting every node in one community gives Q = 0, because the observed and expected fractions are both 1. Putting every node alone gives a negative Q. With gamma = 1, Q always lies between -1/2 and 1. It never reaches -1, whatever some summaries claim. A high Q is not proof of structure, because random graphs can score well too.

For the example used throughout this article, three triangles linked in a chain by two bridge edges (m = 11), the natural partition into the three triangles scores 0.4835. The single community scores 0 and nine singletons score -0.1157.

The gain of moving one node

Maximising modularity exactly is NP-hard, so Louvain climbs greedily. Its only move takes one node out of its community and puts it into a neighbour's community. The algorithm is fast because the change in Q from that move needs only local quantities. Remove node i first, so it sits alone. Let k_i,in(c) be the weight of edges from i to nodes in community c, and let Sigma_tot(c) exclude i. Expanding Q before and after the insertion, all terms not involving i cancel:

delta_Q(i -> c) = k_i,in(c) / m  -  gamma * Sigma_tot(c) * k_i / (2 m^2)

Multiply by m to get a gain with the same ordering:
gain(i -> c)    = k_i,in(c)      -  gamma * Sigma_tot(c) * k_i / (2m)

The equation reads naturally. Joining a community earns the edges you share with it, and pays a penalty that grows with the community's total degree and your own. Big hubs and big communities are expensive to combine. For each node, compare the gain for every neighbouring community with staying alone (gain 0), and move to the best. That costs the node's degree, so one sweep costs O(m).

Two phases and the level loop

Phase 1, local moves. Every node starts in its own community. Visit the nodes in some order, usually a random permutation, and apply the best positive move. Repeat full sweeps until one completes with no moves, or until the total gain falls below a small threshold. Because every accepted move strictly increases Q, and there are finitely many partitions, the phase terminates.

Phase 2, aggregation. Build a new graph with one node per community. The weight between two new nodes is the total weight of edges between the two communities. Edges inside a community become a self-loop on its new node. The convention matters: the self-loop's weight is the inner edge weight, and it counts twice toward the new node's degree, so degrees and m are preserved exactly. Get this wrong and Q computed at level 2 no longer equals Q at level 1, and the algorithm optimises the wrong function.

Run phase 1 again on the smaller graph, where moving a super-node moves a whole community at once. Stop when a level makes no moves. Each level is coarser, so the output is a hierarchy.

No tight worst-case bound is widely cited. In practice there are few levels, and the cost grows roughly linearly with edges on sparse graphs.

A hand trace on three triangles

Trace phase 1 on this graph with nodes visited in order 0 to 8. Here 2m = 22. Nodes 0, 1, 4, 7, 8 have degree 2, and nodes 2, 3, 5, 6 have degree 3. The table shows the scaled gain k_i,in - Sigma_tot * k_i / 22 for each candidate.

Node 3 shows the greedy rule at work. Joining triangle A has a positive gain of 0.045, but joining node 4 is worth 0.727, so the best move wins. A second sweep moves nothing, and Q = 0.4835. Aggregation produces three super-nodes with self-loops of weight 3 and edges A-B and B-C of weight 1, with degrees 7, 8 and 7. At level 2, moving A into B would earn 1 but pay 8 * 7 / 22 = 2.55, so nothing moves and the run stops. Five seeds of the implementation below all gave these three communities.

An implementation

This implementation stores the graph as a dict of neighbour weights, with a self-loop kept once in adj[u][u] and counted twice in degree. It favours clarity over speed. Production code uses CSR arrays instead of dicts.

import random
from collections import defaultdict

def one_level(adj, gamma, rng):
    k = {u: sum(nb.values()) + nb.get(u, 0) for u, nb in adj.items()}
    m2 = sum(k.values())                     # 2m
    comm = {u: u for u in adj}
    tot = dict(k)                            # Sigma_tot per community
    moved, improved, order = True, False, list(adj)
    while moved:
        moved = False
        rng.shuffle(order)
        for u in order:
            cu = comm[u]
            links = defaultdict(float)       # weight from u to each neighbouring community
            for v, w in adj[u].items():
                if v != u:
                    links[comm[v]] += w
            tot[cu] -= k[u]                  # take u out of its community
            best = cu
            best_gain = links.get(cu, 0.0) - gamma * tot[cu] * k[u] / m2
            for c, w_uc in links.items():
                gain = w_uc - gamma * tot[c] * k[u] / m2
                if gain > best_gain + 1e-12:
                    best, best_gain = c, gain
            tot[best] += k[u]
            if best != cu:
                comm[u] = best
                moved = improved = True
    return comm, improved

def aggregate(adj, comm):
    new = defaultdict(lambda: defaultdict(float))
    for u, nb in adj.items():
        for v, w in nb.items():
            cu, cv = comm[u], comm[v]
            if u == v:
                new[cu][cu] += w             # carry an existing self-loop
            elif cu == cv:
                new[cu][cu] += w / 2         # each inner edge is seen from both ends
            else:
                new[cu][cv] += w
    return {u: dict(nb) for u, nb in new.items()}

def louvain(adj, gamma=1.0, seed=0):
    rng = random.Random(seed)
    member = {u: u for u in adj}             # original node -> current super-node
    while True:
        comm, improved = one_level(adj, gamma, rng)
        if not improved:
            return member
        member = {u: comm[s] for u, s in member.items()}
        adj = aggregate(adj, comm)

Test it by recomputing Q from the original graph and the final membership, and by checking that aggregation preserves total degree. Both catch the self-loop bug.

Using a library

In practice you call a library. NetworkX provides networkx.community.louvain_communities(G, weight='weight', resolution=1, seed=...), which returns a list of node sets, plus networkx.community.modularity to score them. igraph exposes the same algorithm as community_multilevel and is much faster on large graphs because its core is C. For larger graphs, GPU implementations exist (cuGraph ships Louvain and Leiden). Defaults for tie-breaking, thresholds and levels differ, so read each library's docs.

The resolution limit and gamma

Fortunato and Barthelemy showed in 2007 that modularity has a resolution limit. The penalty term depends on the size of the whole graph. In a large graph, two small, dense communities joined by even one edge can score higher merged than apart. Louvain then returns the merged group, and no amount of better optimisation fixes it, because the objective itself prefers the merge.

The gamma parameter is the practical lever. Values above 1 give more, smaller communities, and values below 1 give fewer, larger ones. Q at different gammas is not comparable, so do not pick gamma by maximising Q. Sweep it from 0.25 to 4, and pick the value where the partition is stable across seeds and community sizes suit the downstream use, such as review queues of tens of accounts.

A related problem is degeneracy. Many partitions can have nearly the same Q yet differ in structure, and node order decides which one a run returns.

Failure modes

• Badly connected communities. Traag, Waltman and van Eck (2019) showed that Louvain can return communities that are poorly connected internally, or even disconnected. A node that bridged two parts of a community can move out in a later sweep, leaving the rest split, and aggregation then freezes the split community. The Leiden algorithm adds a refinement phase that guarantees connected communities. If you stay with Louvain, run a connected-components check inside each community (union-find over its inner edges) and split any that fail.
• Seed sensitivity. Different visiting orders give different partitions. Run with several seeds and measure agreement with normalised mutual information or the adjusted Rand index. Report a consensus or the most stable run, not whichever came first.
• Directed and signed graphs. Classic Louvain assumes undirected, non-negative weights. Negative weights break the null model.
• Isolates and Q comparisons. Isolated nodes become singleton communities that inflate the count. Q depends on size and density, so compare it only with degree-preserving randomisations of the same graph.

Operational guidance

Prepare the graph. Merge parallel edges by summing weights, drop self-loops that are artefacts of logging, and decide what weight means. Counts of interactions are usually heavy-tailed, so a log transform stops one huge edge from dominating.

Evaluate without labels. Plot community sizes on a log scale and compute conductance of the largest communities alongside the checks above.

Keep partitions stable over time. When the graph changes daily, warm-start from yesterday's membership where your library allows it (the leidenalg package accepts an initial membership, for example). Then match new communities to old ones by maximum overlap, so community IDs persist for downstream consumers. Without matching, every rerun relabels everything and dashboards churn.

Scale. Parallel and GPU implementations apply moves in batches, so expect slightly different results from the sequential algorithm.

Trade-offs against other methods

For new work, prefer Leiden with a resolution sweep. Leiden reuses Louvain's move and aggregation phases, so everything above still applies.

What to do next

1. Run the implementation above on the nine-node example and confirm Q = 0.4835 and three communities.
2. Load your graph, symmetrise it if needed, merge parallel edges and choose a weight transform.
3. Run Louvain with five seeds and compute pairwise NMI. If agreement is low, treat the partition as unstable.
4. Sweep gamma from 0.25 to 4 and choose the value where community sizes fit the downstream use and agreement is high.
5. Check every community for internal connectivity with union-find, and split or switch to Leiden if any fail.
6. Compare Q with Q on degree-preserving randomisations before claiming the structure is real.
7. For recurring runs, warm-start from the previous partition and match community IDs by overlap.

Related reading: label propagation for a faster, objective-free alternative; union-find for the connectivity check; Katz centrality for ranking nodes inside a community; and articulation points for finding the bridges that hold a community together.