Return to 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$.

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.

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 two divisions. 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$.

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

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}$. Of course, this could be done to save two divisions. 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 in line 272 in Louvain.cpp:

new_qual = qual->quality();

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

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 two divisions. 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$.