Louvain method: Why do they drop coefficient 1/m in the official implementation?

Question

Intro

I'm referring to the original paper Fast unfolding of communities in large networks 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, they've linked to sourceforge 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.

Answer 1

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, 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.