## 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:

```lang-cpp
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:

```lang-cpp
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`:

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

and can't simply do something like $Q_{new}= Q_{old} + \Delta Q$.