The modularity difference in Louvain algorithm for community detection in graphs

Question

---

I am interested in the formula of modularity difference between two partitions considered in the Louvain algorithm for community detection in graphs. I give a formal expression of this question below.

---

Consider an undirected graph $G$ with vertex set $V$. If $G$ is weighted, $\omega(u,v)$ denotes the weight of the edge between $u$ and $v$ if it exists, otherwise it is $0$. If $G$ is unweighted, then it is seen as a weighted graph with each edge weight equal to $1$.

Let us denote by $m$ the half of $2m = \sum_{u\in V}\sum_{v\in V} \omega(u,v)$; it is the number of edges in $G$ if it is unweighted.

A partition $P$ of $V$ is a set of $k$ sets $P = \{C_1, C_2, \dots, C_k\}$ with $\cup_i C_i = V$ and $C_i \cap C_j = \emptyset$ if $i\neq j$.

The modularity of partition $P$ is: $$ Q(P) = \sum_{C\in P} Q(C) = \sum_{C\in P} \frac{e_C}{2m} - \left(\frac{a_C}{2m}\right)^2 $$ where $ e_C = \sum_{u\in C}\sum_{v\in C} \omega(u,v) $ and $a_C = \sum_{u\in C}\sum_{v\in V} \omega(u,v)$.

Modularity is widely used in the context of community detection in graphs, where one seeks partitions with high modularity. Then, $C_1$, $C_2$, $\dots$, $C_k$ are called communities.

The Louvain algorithm is one of the main community detection methods. It relies on the fact that one may easily compute the modularity difference between two partitions if one of them is obtained from the other by moving only one vertex from a community to another one.

Partial expressions of this modularity difference are available in the literature, including the original Louvain paper (with a typo) and in the wikipedia page on Louvain method, but I cannot find a full expression and its derivation in any published paper. All I could find is a Quora discussion on the topic, that I find quite obscure, sorry.

Finding this expression is not very challenging, but not completely trivial either, it seems, since there are many incomplete and/or flawed versions online. Given its great importance in network science, I guess I missed something.

Question: where may I find a full, clear and correct derivation of the modularity difference between two such partitions?

There are many implementations of Louvain method, and their source code certainly contains the correct formula; but it is quite technical to get it from code, and I am interested in the detailed derivation too.

Answer 1

There is a derivation of the modularity difference in this book chapter: Multilevel Local Optimization of Modularity by Thomas Aynaud, Vincent D. Blondel, Jean-Loup Guillaume, and Renaud Lambiotte. It is also available in French.

I provide my own version below, with the notations introduced in the question.

Let us consider a node $u$ in a community $i$ of $P$, and let us consider the partition $P'$ obtained by moving $u$ from community $i$ to another community $j$ of $P$: for all $k\neq i$ and $k\ne j$ in $P$, $k$ is in $P'$; in addition, $P'$ contains $i'=i\setminus\{i\}$ and $j'=j\cup\{u\}$, and nothing else.

We then have $e_{i'} = e_i - 2 d(u,i)$ and $e_{j'} = e_j + 2 d(u,j)$. Also, $a_{i'} = a_i - d(u)$ and $a_{j'} = a_j + d(u)$.

Therefore: $$ Q(i') = \frac{e_i-2\cdot d(u,i)}{2m}-\left(\frac{a_i-d(u)}{2m}\right)^2 $$ $$ = \frac{e_i}{2m}-\frac{d(u,i)}{m}- \left(\frac{a_i}{2m}\right)^2 - \left(\frac{d(u)}{2m}\right)^2 + \frac{a_i\cdot d(u)}{2\cdot m^2} $$ and, similarly: $$ Q(j') = \frac{e_j+2\cdot d(u,j)}{2m}-\left(\frac{a_j+d(u)}{2m}\right)^2 $$ $$ = \frac{e_j}{2m} + \frac{d(u,j)}{m} - \left(\frac{a_j}{2m}\right)^2 - \left(\frac{d(u)}{2m}\right)^2 - \frac{a_j\cdot d_u}{2\cdot m^2} $$

We finally obtain: $$ Q(P') - Q(P) = Q(i')-Q(i) + Q(j')-Q(j) $$ $$ = \left( -\frac{d(u,i)}{m} - \left(\frac{d(u)}{2m}\right)^2 + \frac{a_i\cdot d(u)}{2\cdot m^2} \right) + \left( \frac{d(u,j)}{m} - \left(\frac{d(u)}{2m}\right)^2 - \frac{a_j\cdot d_u}{2\cdot m^2} \right) $$ $$ = \frac{d(u,j)-d(u,i) + d(u)\cdot\frac{a_i-a_j-d(u)}{2m}}{m} $$