Where does the second formula of modularity comes from in the Louvain paper (the community sigma total formula)?

891 Views Asked by At

In the paper "Fast unfolding of communities in large networks", the authors show the first definition of modularity: $$ Q = \frac1{2m} \sum_{i,j} \left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j). $$ However, a few pages later, they show the $\Delta Q$ definition (the change of modularity when moving a vertex $i$ to a community $c$): $$ \Delta Q = \left[\frac{\Sigma_{in} + k_{i,in}}{2m} - \left(\frac{\Sigma_{tot} + k_i}{2m}\right)^2\right] - \left[\frac{\Sigma_{in}}{2m} - \left(\frac{\Sigma_{tot}}{2m}\right)^2 - \left(\frac{k_i}{2m}\right)^2\right] $$

How did the authors reached to this definition of $\Delta Q$? It cannot be developed from the original modularity definition shown above.

Thank you in advance.

1

There are 1 best solutions below

0
On

The formula of the change in the modularity is derived from this formula of modularity: $$\sum_{c_i\in C}[{\frac{\sum_{in}^{c_i}}{2m}-\frac{(\sum_{tot}^{c_i})^2}{4m^2}}]$$

In order to show that $$\frac{1}{2m}\sum_{i,j}[A_{i,j}-\frac{k_ik_j}{2m}]\delta(c_i,c_j) = \sum_{c_i\in C}[{\frac{\sum_{in}^{c_i}}{2m}-\frac{(\sum_{tot}^{c_i})^2}{4m^2}}]$$ you should note that

$\sum_{i,j}{k_ik_j}\delta(c_i,c_j)=\sum_{c_i \in C}(\sum_{j \in c_i}{k_j})^2$.

A detailed explanation of the change in modularity formula is explained here: https://www.quora.com/How-is-the-formula-for-Louvain-modularity-change-derived.