Delta modularity calculation (generalized)

🚨 This page is a work in progress. TODO: explain why this is needed.

Here we generalize the delta modularity calculation presented in the previous section for the case where we move a vertex $u$ from any community (not just a singleton community) to any other community $c$ . We proceed by removing $u$ from the old community and putting it into its own singleton community. The latter is done, so that the derived Louvain modularity difference formula can be reused, which is only applicable to the case where one moves a vertex from a singleton community to any other community. With this more generalized equation, we fill the gap caused by the absence of this formula in the original Louvain paper. While we do not employ this generalized formula in the actual implementation, it still might be useful for other applications.

First, we calculate the modularity difference when removing a vertex $u$ from its old community $c_{u}$ (not required to be a singleton community) and inserting it into its own singleton community $\overset{c}{˚}_{u}$ . As before, we prohibit self-loops in the original graph, hence $Σ_{\overset{c}{˚}_{u}}$ . We won’t be as elaborate this time due to the rationale being very similar:

$Δ Q (u, c_{u}, \overset{c}{˚}_{u}) = Q^{'} (c_{u}) - Q (c_{u}) + Q (\overset{c}{˚}_{u}) = [\frac{Σ _{c_{u}}^{'}}{2 m} - (\frac{Σ _{\overset{c}{^}_{u}}^{'}}{2 m})^{2}] - [\frac{Σ _{c_{u}}}{2 m} - (\frac{Σ _{\overset{c}{^}_{u}}}{2 m})^{2}] + [\frac{Σ _{\overset{c}{˚}_{u}}}{2 m} - (\frac{k _{u}}{2 m})^{2}] = [\frac{Σ _{c_{u}} - 2 k _{u}^{\to c_{u}}}{2 m} - (\frac{Σ _{\overset{c}{^}_{u}} - k _{u}}{2 m})^{2}] - [\frac{Σ _{c_{u}}}{2 m} - (\frac{Σ _{\overset{c}{^}_{u}}}{2 m})^{2}] - (\frac{k _{u}}{2 m})^{2} = - \frac{k _{u}^{\to c_{u}}}{m} - (\frac{Σ _{\overset{c}{^}_{u}}}{2 m})^{2} + 2 \frac{Σ _{\overset{c}{^}_{u}}}{2 m} \frac{k _{u}}{2 m} - (\frac{k _{u}}{2 m})^{2} + (\frac{Σ _{\overset{c}{^}_{u}}}{2 m})^{2} - (\frac{k _{u}}{2 m})^{2} = - \frac{k _{u}^{\to c_{u}}}{m} + \frac{2 k _{u} Σ _{\overset{c}{^}_{u}}}{( 2 m ^{2} )} - \frac{2 k _{u}^{2}}{( 2 m ) ^{2}} = \frac{1}{m} (- k_{u}^{\to c_{u}} + \frac{k _{u} ( Σ _{\overset{c}{^}_{u}} - k _{u} )}{2 m})$

We bring together this equation with the one from the previous section and obtain the following generalized formula for the modularity difference when moving a vertex $u$ from its previous community $c_{u}$ to any other community $c$ . This is done by first moving $u$ from $c_{u}$ into its own singleton community $\overset{c}{˚}_{u}$ , then moving it from there into the target community $c$ :

$Δ Q (u, c_{u}, c) = Δ Q (u, c_{u}, \overset{c}{˚}_{u}) + Δ Q (u, \overset{c}{˚}_{u}, c) = \frac{1}{m} (- k_{u}^{\to c_{u}} + \frac{k _{u} ( Σ _{\overset{c}{^}_{u}} - k _{u} )}{2 m}) + \frac{1}{m} (k_{u}^{\to c} - \frac{Σ _{\overset{c}{^}} k _{u}}{2 m}) = \frac{1}{m} (k_{u}^{\to c} - k_{u}^{\to c_{u}} + \frac{k _{u} ( Σ _{\overset{c}{^}_{u}} - k _{u} ) - Σ _{\overset{c}{^}} k _{u}}{2 m}) = \frac{1}{m} (k_{u}^{\to c} - k_{u}^{\to c_{u}} + \frac{k _{u} ( Σ _{\overset{c}{^}_{u}} - Σ _{\overset{c}{^}} - k _{u} )}{2 m})$

Finally, for the generalized formula, we have

$Δ Q (u, c_{u}, c) \propto (k_{u}^{\to c} - k_{u}^{\to c_{u}}) + \frac{k _{u} ( Σ _{\overset{c}{^}_{u}} - Σ _{\overset{c}{^}} - k _{u} )}{2 m}$

The delta modularity calculation for removing from a singleton community can be derived from this formula by assuming that $c_{u}$ is a singleton community. As we do not allow self-loops, $k_{u}^{\to c_{u}} = 0$ . Moreover, the sum of the weights of edges incident to vertices in $c_{u}$ is equal to the vertex degree: $\sum_{\overset{c}{^}_{u}} = k_{u}$ , which gives us:

$Δ Q (u, \overset{c}{˚}_{u}, c) \propto (k_{u}^{\to c} - 0) + \frac{k _{u} ( k _{u} - Σ _{\overset{c}{^}} - k _{u} )}{2 m} = k_{u}^{\to c} - \frac{Σ _{\overset{c}{^}} k _{u}}{m}$

which is indeed the formula derived here.

Fast Louvain

Delta modularity calculation (generalized)