Louvain Community Detection

From Modularity to an Optimization Procedure

Modularity gives a score for a partition of a graph, but it does not by itself specify how to find a high-scoring partition. Louvain is a heuristic procedure for improving that score. It alternates between two operations: local vertex moves, which seek better community assignments, and graph aggregation, which compresses the current communities into weighted supernodes. The procedure is useful for cell-neighborhood graphs because it can work on large sparse graphs without enumerating every possible partition.

We use the standard modularity objective for an undirected weighted graph, with nonnegative edge weights and no self-loops in the original graph. Let $A_{ij}=A_{ji}$ be the weight between vertices $i$ and $j$, let $k_i=\sum_j A_{ij}$ be the strength of vertex $i$, and let $m=\frac{1}{2}\sum_i k_i$, the sum of all edge weights. For a community $C$, let $l_C$ be the total weight of edges with both ends in $C$, and let $K_C=\sum_{i\in C}k_i$. The modularity of a partition is

Q=\sum_C\left(\frac{l_C}{m}-\left(\frac{K_C}{2m}\right)^2\right).

This objective compares observed within-community edge weight with the amount expected under a degree-preserving null model. Louvain seeks a partition with a large $Q$; it does not guarantee the globally largest possible value.

The Local Vertex-Move Step

Louvain commonly begins with every vertex in its own community. It visits vertices in some order and considers moving a vertex into a community represented among its neighbors. For each candidate, it evaluates the modularity change; a move is accepted when that change is positive. After a pass through the vertices, further passes are made until a complete pass produces no improving move. The order of visits can affect the result.

Definition: Suppose vertex $i$ is currently in community $C$, and consider moving it to a different community $D$. Let $k_i$ be its strength, $a$ the total weight from $i$ to the other vertices in $C$, and $b$ the total weight from $i$ to vertices in $D$. Let $K_C$ and $K_D$ be the communities’ total strengths before the move. The modularity gain is $$ \Delta Q=\frac{b-a}{m}+\frac{k_i(K_C-K_D-k_i)}{2m^2}. $$ A positive $\Delta Q$ means the move increases modularity.

The calculation uses $a$ and $b$ as edge weights, not counts of neighboring vertices. In particular, $a$ excludes vertex $i$ itself. A vertex may have no edge to a candidate community; then $b=0$, though implementations typically focus the search on communities neighboring the vertex. If the vertex is removed from its original community, that community’s remaining strength is $K_C-k_i$. A candidate move can leave the original community empty, as happens when moving a singleton vertex.

The formula shows the balance in a move. The term $(b-a)/m$ rewards transferring edge weight from the old community to the new one. The other term accounts for the change in the degree-based expected-edge contribution. Thus the community with the most edge weight to a vertex is not automatically the best destination.

Worked Example: Deriving a Move Gain

Suppose a weighted graph has $m=7$. A vertex $i$ of strength $k_i=4$ is in community $C$, with $K_C=4$, and is considering a move to community $D$, with $K_D=3$. Its edge weight to the rest of $C$ is $a=0$, and its edge weight to $D$ is $b=3$. The move’s modularity gain is

\Delta Q=\frac{3-0}{7}+ \frac{4(4-3-4)}{2(7^2)} =\frac{3}{7}-\frac{12}{98} =\frac{30}{98} \approx 0.3061.

The positive gain means the move increases modularity by about $0.3061$. The degree correction reduces the direct edge-weight contribution, but does not reverse it. This calculation concerns a change in the partition score, not a probability that the move is correct.

Why the Move Formula Holds

Only communities $C$ and $D$ change their contributions to $Q$. Before the move, the internal edge weight in $C$ includes $a$; after the move it decreases by $a$. The internal edge weight in $D$ increases by $b$. The corresponding community strengths change from $K_C,K_D$ to $K_C-k_i,K_D+k_i$. Subtracting the old contributions from the new ones gives

\Delta Q=\frac{b-a}{m} -\frac{(K_C-k_i)^2+(K_D+k_i)^2-K_C^2-K_D^2}{4m^2}.

Expanding the squared terms gives

$$ (K_C-k_i)^2+(K_D+k_i)^2-K_C^2-K_D^2 =2k_i(K_D-K_C)+2k_i^2. $$

Substituting this expression into the previous equation yields

\Delta Q=\frac{b-a}{m} +\frac{k_i(K_C-K_D-k_i)}{2m^2},

which is the local move formula. All unchanged communities cancel from the difference. This also explains why the calculation needs only local edge weights and the strengths of the two affected communities.

Worked Louvain Pass on a Weighted Graph

Consider four vertices $A,B,C,D$, with edge weights $w_{AB}=3$, $w_{BC}=1$, and $w_{CD}=3$, and no other edges. The graph is undirected, has nonnegative weights, and has no self-loops, so it satisfies the assumptions above. The total edge weight is $m=3+1+3=7$. The vertex strengths are $k_A=3$, $k_B=4$, $k_C=4$, and $k_D=3$.

Worked Example: Moving Vertices Into Two Communities

Start with four singleton communities. Visit $B$ and consider moving it into $A$’s community. Here $k_B=4$, $K_C=4$ for $B$’s singleton source community, $K_D=3$ for $A$’s singleton destination community, $a=0$, and $b=3$. Therefore,

\Delta Q_{B\to A} =\frac{3}{7}+\frac{4(4-3-4)}{98} =\frac{42-12}{98} =\frac{30}{98} \approx 0.3061.

This is an improving move, so $A$ and $B$ form a community. Next, consider moving $C$ into $D$’s singleton community. The values are $k_C=4$, $K_C=4$ for $C$’s source, $K_D=3$ for $D$’s destination, $a=0$, and $b=3$. The gain is also $30/98$, so this move is accepted. The resulting communities are $\{A,B\}$ and $\{C,D\}$.

For a direct check, each community has internal edge weight 3 and total strength 7. Thus

Q=2\left(\frac{3}{7}-\left(\frac{7}{14}\right)^2\right) =2\left(\frac{3}{7}-\frac14\right) =\frac{5}{14} \approx 0.3571.

The initial singleton partition has $Q=-(3^2+4^2+4^2+3^2)/(4\cdot 7^2)=-50/196\approx-0.2551$. The two accepted moves have total gain $60/98\approx0.6122$, which brings the score to approximately $0.3571$, consistent with the direct calculation.

Worked Example: Rejecting a Move Across the Bridge

From the partition $\{A,B\},\{C,D\}$, consider moving $B$ from $\{A,B\}$ to $\{C,D\}$. For the source community, $K_C=7$; for the destination, $K_D=7$. Vertex $B$ has $k_B=4$, edge weight $a=3$ to $A$, and edge weight $b=1$ to $C$. The gain is

\Delta Q_{B\to \{C,D\}} =\frac{1-3}{7}+\frac{4(7-7-4)}{98} =-\frac{2}{7}-\frac{16}{98} =-\frac{44}{98} \approx -0.4490.

The move would lower modularity, so it is rejected. This illustrates why the bridge edge of weight 1 does not justify joining the two communities: moving $B$ would also give up its weight-3 edge to $A$ and change the degree-based terms. After testing the available moves and making any positive-gain moves, a pass with no further improvements marks a local optimum for the moves considered—not a proof that no better partition exists.

Aggregation: Compressing the Current Partition

Once local moving has reached a pass with no improving moves, Louvain constructs a smaller graph. Each current community becomes one supernode. The weight between two different supernodes is the sum of all original edge weights running between their communities. Internal edges of each community become a self-loop on its supernode. In the common weighted-graph convention, that loop has weight $l_C$ and contributes $2l_C$ to the supernode’s strength. This convention preserves the total edge weight $m$.

Worked Example: Aggregating the Two-Community Partition

For the partition $\{A,B\},\{C,D\}$, each community has internal edge weight 3, and the only edge between communities has weight 1. The aggregated graph therefore has two supernodes, each with a self-loop of weight 3, and one edge of weight 1 between them. Each supernode’s strength is $2(3)+1=7$, so the aggregated graph still has total edge weight $m=(7+7)/2=7$.

A partition of these supernodes corresponds to a partition of the original communities. If the two supernodes are joined into one community, all original edge weight is internal and its strength is 14. Its modularity is

Q=\frac{7}{7}-\left(\frac{14}{14}\right)^2=0.

This is less than $5/14$, so merging the supernodes is not an improving move. The aggregated representation retains the same modularity comparisons for partitions that keep each original community intact; it does not discard the within-community edge weight, but stores it in self-loops.

Louvain applies local moves again on the aggregated graph. If its supernodes combine into larger groups, the graph can be aggregated again. The process stops when a level produces no further improvement. The final groups of supernodes can be mapped back through the aggregation steps to assign communities to the original vertices—in this setting, the cells represented by the graph.

Assumptions, Diagnostics, and Limitations

The standard calculations here assume an undirected weighted graph with symmetric, nonnegative edge weights and a positive total weight $m$. Self-loops may arise during aggregation, even though the original graph was taken to have none. The loop convention must be handled consistently: a loop of weight $w$ contributes $2w$ to strength and $w$ to internal edge weight. A directed graph requires a directed modularity definition rather than silently applying the undirected formula.

Several checks help identify problems in an implementation or analysis:

For each proposed move, verify that $a$ and $b$ sum edge weights to the relevant communities and that $K_C,K_D$ are measured before the move.
After a move or aggregation, recompute $Q$ directly on a small graph and compare it with the predicted gain or preserved score.
Confirm that aggregation preserves total edge weight and supernode strengths, counting self-loops twice in strength.
Check that accepted moves have positive gain, up to numerical tolerance. A gain with the wrong sign often indicates a mistaken factor of two or an incorrect strength update.
Record the visit order and initialization when comparing runs. Different orders can lead to different local optima.

Louvain is computationally attractive because it uses local changes and repeatedly reduces graph size. Its limitation is that it is a greedy heuristic: an improving sequence of individual moves is not guaranteed to find the best partition, and a locally stable partition can still be suboptimal. It also optimizes modularity, so its output depends on the graph and the objective rather than directly identifying biological cell types. As alternatives, one could evaluate partitions by exhaustive search on a very small graph, or use a different graph-clustering objective or a method that optimizes a different criterion. Exhaustive search becomes impractical as the number of vertices grows; changing the objective can yield different communities rather than a universally better answer.

A common mistake is to say, “No single vertex move improves modularity, so the partition is optimal.” The correct conclusion is narrower: no move among those tested improved modularity at that stage. Other sequences of moves, or a different starting order, may reach another partition with a larger score. Similarly, an aggregation step is not itself evidence that the merged communities are biologically homogeneous; it is a computational compression that preserves the modularity comparisons for the represented groups.

Key takeaway: Louvain alternates between accepting positive-gain vertex moves and aggregating the resulting communities. The move formula makes each local decision explicit, while the heuristic nature of the search means its output is a high-scoring candidate, not a guaranteed global optimum.

Check Your Understanding

Answer each question, then compare with the solutions below.

A graph has $m=5$. A vertex has $k_i=2$, $K_C=4$, and $K_D=3$, with $a=1$ and $b=2$. Calculate the move gain and state whether Louvain accepts the move.
Why does aggregation need a self-loop for the internal edge weight of a community?
What does a full pass with no positive-gain moves establish, and what does it not establish?
A supernode has a self-loop of weight 2 and an external edge of weight 3. What is its strength under the convention used here?

Solutions. 1. The gain is $(2-1)/5+2(4-3-2)/(2\cdot25)=0.2-0.04=0.1600$, so the move is accepted. 2. The loop records the edge weight already internal to the aggregated community, allowing modularity for partitions of supernodes to reflect that internal weight. 3. It establishes a local optimum among the moves considered in that pass; it does not establish a global maximum over all partitions. 4. The strength is $2(2)+3=7$, because a self-loop contributes twice its weight to strength.

What You'll Learn