I'm using the Clauset-Newman-Moore algorithm for finding communities in graphs in a project and I need to dissect the paper of this algorithm.
From what I understand, you begin the algorithm putting every vertex into a community of one, calculating the modularity for the graph using this separation into communities and then changing the graph and incrementing the modularity using the algorithm steps in a way that the new modularity of the graph is the modularity of the new separation.
But, from reading the paper and doing some calculations, it seems that the algorithm doesn't increment enough to give us the modularity of the new separation.
In the beginning of the algorithm, using equation $(7)$ of the paper, we will have
$$Q=-\sum_v\frac{k_v^2}{(2m)^2}$$
After the first increment (joining the communities of two vertices that are connected), if we calculate $Q$ by the equation $(7)$ we will have, if the vertices are $v_1$ and $v_2$ and the community they are in is called $i$,
$$Q= -\left(\sum_{v\neq v1,v2} \frac{k_v^2}{(2m)^2}\right) + \left(e_{ii}-a_i^2\right)$$ $$= -\left(\sum_{v\neq v1,v2} \frac{k_v^2}{(2m)^2}\right) + \left(\left(\frac{1}{2m}(1+1)\right) - \left(\frac{1}{2m}(k_{v_1}+k_{v_2})\right)^2\right)$$ $$ = -\left(\sum_{v} \frac{k_v^2}{(2m)^2}\right)+ \left(\frac{1}{2m}+\frac{1}{2m} - 2\frac{k_{v_1}k_{v_2}}{(2m)^2}\right)$$
And if we calculate the new modularity using the first increment of the algorithm, we will only have
$$Q = -\left(\sum_{v} \frac{k_v^2}{(2m)^2}\right)+ \left(\frac{1}{2m} - \frac{k_{v_1}k_{v_2}}{(2m)^2}\right)$$
Which is definitely different from the previous one. So how is this difference compensated? What am I missing? Am I calculating this wrong?
I appreciate every answer. Thank you for your time!