Louvain Algorithm for Community Detection

Node: open the accordion below for a detailed explanation of the algorithm's implementation

Modularity Update

The change in modularity by moving one node to the community of one of its neighbors is computed as follows. We first remove node \(i\) from its community \(D\) and then insert this node into community \(C\).

We first introduce some notation:

\(D\rightarrow C\) is the operation of moving node \(i\) from its community \(D\) to community \(C\)
\(k_i(i \rightarrow D)\) is the total weight of all links pointing from node \(i\) to community \(D\)
\(k_i(i \rightarrow C)\) is the total weight of all links pointing from node \(i\) to community \(C\)
\(\Sigma_{C,in}\) sum of weights all links internal to community \(C\) including loops
\(\Sigma_{D,in}\) sum of weights all links internal to community \(D\) including loops
\(\Sigma_{C,tot}\) sum of weights all links of nodes in community \(C\) including loops
\(\Sigma_{D,tot}\) sum of weights all links of nodes in community \(D\) including loops
\(l_i\) is the weight of the loop of node \(i\)

The update of modularity is given by

\[ \Delta Q = Q_{after} - Q_{before} \]

where

\[ Q_{before} = \frac{\Sigma_{C,in}}{2m} - \left(\frac{\Sigma_{C,tot}}{2m}\right)^2 + \frac{\Sigma_{D,in}}{2m} - \left(\frac{\Sigma_{D,tot}}{2m}\right)^2 \]

and

\[ \begin{align} Q_{after} =&\; \frac{\Sigma_{C,in} + 2 k_i(i \rightarrow C) + l_i}{2m} - \left(\frac{\Sigma_{C,tot} + k_i}{2m}\right)^2 \\ &\; + \frac{\Sigma_{D,in} - 2 k_i(i \rightarrow D) - l_i}{2m} - \left(\frac{\Sigma_{D,tot} - k_i}{2m}\right)^2 \end{align} \]

After some algebraic manipulations, we obtain

\[ \Delta Q = \frac{k_i(i \rightarrow C) - k_i(i \rightarrow D)}{m} + \frac{k_i}{2m} \left(\frac{\Sigma_{C,tot} - \Sigma_{D,tot} + k_i}{2m}\right) \]

The Louvain algorithm is an agglomerative method that is widely used due to its performance (aka it is fast). It consists of two phases:

Phase 1: Improve the partition by moving nodes between communities
Phase 2: Improve the partition by a hierarchical agglomeration of the communities found with the method used in Phase 1

Repeat until no further increase in modularity can be obtained.

Phase 1

Initialization

Input: weighted and undirected network with \(n\) nodes.
For each node, a community is created and assigned to it.

For each node:

Measure the gain in modularity to be obtained by moving node \(i\) to the community of its neighbors.
Move \(i\) to the community with the largest gain.
If the gain is negative, don't move node \(i\).

Repeat this process until no gain in modularity can be measured.

Remarks

Each node will be processed many times.

The algorithm's output depends on the order in which the nodes are processed.

Computation time depends on the order of the nodes.

Modularity

The change in modularity is given by

\[ \Delta Q = \left[\frac{\Sigma_{in} + 2 k_{i,in}}{am} - \left(\frac{\Sigma_{tot} +k_i}{2m}\right)^2 \right] - \left[\frac{\Sigma_{in}}{2m} - \left(\frac{\Sigma_{tot}}{2m}\right)^2 - \left(\frac{k_i}{2m}\right)^2\right] \]

where

\( \Sigma_{in} = \text{sum of the weights of the links inside the community of node } i \)
\( \Sigma_{tot} = \text{total sum of the weights of all links of the community, including edges pointing outside the community} \)
\( \Sigma_{tot} + k_i = \text{total sum including the links of node } i \)
\( k_{i,in} = \text{sum of the weights of the links of node } i \text{ pointing inside the community} \)
\( k_i = \text{sum of the weights of the links incident to node } i \)

Phase 2

Construct a new network where the nodes are the communities found in Phase 1.
Links between actual nodes of the communities are combined into a new link; the weight is the sum of the weights of the links.
Links between nodes within a community are combined into a loop of the new node (with weight = 2).
Apply the method of Phase 1 to the new network.

Continue iteratively until \(\Delta Q \leq 0\). In each iteration, a new network is being created from the communities found in the previous iteration.