Intro
-----


I'm referring to the original paper [Fast unfolding of communities in large
networks](https://perso.uclouvain.be/vincent.blondel/publications/08BG.pdf) by Blondel et al. in this question and adopt their notation. Explanation for the used symbols is on page 4 below equation (2).


I'm wondering why Blondel et al. are dropping the coefficient $\frac{1}{m}$. First, let's simplify their equation (2) to see what I mean:


$$ \Delta Q= \Biggl[ \frac{\Sigma\_{in}+2k\_{i,in}}{2m} - \Bigl( \frac{\Sigma\_{tot}+k\_i}{2m} \Bigr)^2 \Biggr] - \Biggl[ \frac{\Sigma\_{in}}{2m} - \Bigl( \frac{\Sigma\_{tot}}{2m} \Bigr)^2 - \Bigl( \frac{k\_i}{2m} \Bigr)^2 \Biggr] $$


$$ \Delta Q = \frac{\Sigma\_{in}}{2m} + \frac{2k\_{i,in}}{2m} - \Bigl( \frac{\Sigma\_{tot}}{2m} + \frac{k\_i}{2m}\Bigr)^2 - \frac{\Sigma\_{in}}{2m} + \Bigl( \frac{\Sigma\_{tot}}{2m} \Bigr)^2 + \Bigl( \frac{k\_i}{2m} \Bigr)^2 $$


$$ \Delta Q = \frac{2k\_{i,in}}{2m} - \frac{\Sigma\_{tot}\cdot 2k\_i}{(2m)^2} $$


However, this is not the version they used in their code. On their [official code page](https://sites.google.com/site/findcommunities/), they've linked to [sourceforge](https://sourceforge.net/projects/louvain/) to download the C++ code. In the file `Modularity.h`, you'll find the following code:



```
inline long double
Modularity::gain(int node, int comm, long double dnc, long double degc) {
  assert(node>=0 && node<size);
  
  long double totc = tot[comm];
  long double m2   = g.total_weight;
  
  return (dnc - totc*degc/m2);
}

```

`dnc` is passed over in line 257 in `louvain.cpp` and calculated in the method `void Louvain::neigh_comm(int node)`. If you follow the calculations, you will see that this is actually our $k\_{i,in}$ in the formula. I'm now wondering where this line in the method `Modularity::gain(...)` comes from:



```
return (dnc - totc*degc/m2);

```

My guess
--------


Let's further "simplify" our formula to a point where it resembles the code used:


$$\Delta Q = \frac{k\_{i,in}}{m} - \frac{\Sigma\_{tot}\cdot 2k\_i \cdot \frac{1}{2m}}{(2m)^2 \cdot \frac{1}{2m}}$$


$$ \Delta Q = \frac{k\_{i,in}}{m} - \frac{\Sigma\_{tot}\cdot \frac{k\_i}{m}}{2m}$$


This is very similar to the mentioned codeline if we let `dnc` denote $\frac{k\_{i,in}}{m}$ and `degc` $\frac{k\_i}{m}$.


However, in the method where they calculate `dnc` and `degc` (`void Louvain::neigh_comm(int comm)`), Blondel et al. just use the numerator, dropping the coefficient $\frac{1}{m}$ here:


$$ \Delta Q = \frac{1}{m} \cdot \Bigl( k\_{i,in} - \frac{\Sigma\_{tot}\cdot k\_i}{2m} \Bigr) $$


Of course, this could be done to save a division. However, they do not get the correct absolute value for $\Delta Q$ then. Maybe that's why they also have to recalculate the quality again multiple times in every pass in line 272 in `Louvain.cpp`:



```
new_qual = qual->quality();

```

and can't simply do something like $Q\_{new}= Q\_{old} + \Delta Q$, which would save a lot of multiplications and divisions.



Louvain method: Why do they drop coefficient 1/m in the official implementation?
The function is used when they decide whether the node should stay in the community or not. Therefore, they only need to compare quality value differences and have no need for absolute numbers. The division factor is constant during the computation and therefore can be omitted since it does not affect the result of the comparison:
$$
k \cdot \Delta Q\_1 \lt k \cdot \Delta Q\_2 \iff \Delta Q\_1 \lt \Delta Q\_2, k \in \Bbb R^+
$$


That way, they safe a division in the inner loops which is called for every edge in the graph. Divisions in general are computationally quite expensive even on modern processors. I do not have actual measurements, but if you put both version in [llvm-mca](https://releases.llvm.org/13.0.0/docs/CommandGuide/llvm-mca.html), the block throughput is twice as fast without the extra division.
As you mentioned, they recalculate the overall quality value for the graph in each pass. However, this loop is called for each node whose count is often much less than the number of edges.


Another reason might be accuracy. In the original formula, they divide by $4m^2$, which might become too large to be stored as floating point value and the denominator becomes infinite. If you divide a finite number by an infinite value, the final result becomes zero. In their quality gain formula, they used $2m$ as denominator and the risk of overflow is reduced significantly.


