Louvain method

The Louvain method for community detection is a greedy optimization method intended to extract non-overlapping communities from large networks created by Blondel et al. from the University of Louvain (the source of this method's name).

Modularity optimization

The inspiration for this method of community detection is the optimization of modularity as the algorithm progresses. Modularity is a scale value between −0.5 (non-modular clustering) and 1 (fully modular clustering) that measures the relative density of edges inside communities with respect to edges outside communities. Optimizing this value theoretically results in the best possible grouping of the nodes of a given network. But because going through all possible iterations of the nodes into groups is impractical, heuristic algorithms are used.

In the Louvain Method of community detection, first small communities are found by optimizing modularity locally on all nodes, then each small community is grouped into one node and the first step is repeated. The method is similar to the earlier method by Clauset, Newman and Moore that connects communities whose amalgamation produces the largest increase in modularity. The Louvain algorithm was shown to correctly identify the community structure when it exists, in particular in the stochastic block model.

Algorithm

The value to be optimized is modularity, defined as a value in the range $[-1/2,1]$ that measures the density of links inside communities compared to links between communities. For a weighted graph, modularity is defined as:

$Q={\frac {1}{2m}}\sum _{i=1}^{N}\sum _{j=1}^{N}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}}{\bigg ]}\delta (c_{i},c_{j}),$

where:

• $A_{ij}$ represents the edge weight between nodes $i$ and $j$; see Adjacency matrix;
• $k_{i}$ and $k_{j}$ are the sum of the weights of the edges attached to nodes $i$ and $j$, respectively;
• $m$ is the sum of all of the edge weights in the graph;
• $N$ is the total number of nodes in the graph;
• $c_{i}$ and $c_{j}$ are the communities to which the nodes $i$ and $j$ belong; and
• $\delta$ is Kronecker delta function:

${\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{if }}c_{i}{\text{ and }}c_{j}{\text{ are the same cluster}}\\0&{\text{otherwise}}\end{cases}}\end{aligned}}$

Based on the above equation, the modularity of a community $c$ can be calculated as:

${\begin{aligned}Q_{c}&={\dfrac {1}{2m}}\sum _{i}\sum _{j}A_{ij}\mathbf {1} \left\{c_{i}=c_{j}=c\right\}-\left(\sum _{i}{\dfrac {k_{i}}{2m}}\mathbf {1} \left\{c_{i}=c\right\}\right)^{2}\\&={\frac {\Sigma _{in}}{2m}}-\left({\frac {\Sigma _{tot}}{2m}}\right)^{2}\end{aligned}}$

where

• $\Sigma _{in}$ is the sum of edge weights between nodes within the community $c$ (each edge is considered twice); and
• $\Sigma _{tot}$ is the sum of all edge weights for nodes within the community (including edges which link to other communities).

As nodes in different communities do not contribute to the modularity $Q$, it can be written as:

$Q=\sum _{c}Q_{c}$

In order to maximize modularity efficiently, the Louvain Method has two phases that are repeated iteratively.

Phase 1:

1. First, each node in the network is assigned to its own community.

Step 1: Each node in the graph is randomly assigned to a singleton community

2. Next, for each node $i$, the change in modularity is calculated for removing $i$ from its own community and moving it into the community of each neighbor $j$ of $i$. This value is computed in two steps:

(a) Compute the change in modularity $\Delta Q$ for removing node $i$ from its original community.

(b) Compute the change in modularity $\Delta Q$ for inserting an isolated node $i$ (i.e. node $i$ has no connections and is in a community of only itself) into the community of neighbouring node, denoted $c_{j}$.

In the following, we will show the derivation for (b). The equations for (a) are similar and can be computed by similar methods.

First, we compute the modularity of the isolated cluster of node $i$, which we will call $c_{i}$. Here we are assuming that there are no loops, and so $A_{\mu \mu }=0$ for all values of $\mu$:

${\begin{aligned}Q_{i}^{\text{prev}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{i}=1}\sum _{\nu =1}^{N_{i}=1}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{i}=1}{\dfrac {k_{\mu }}{2m}}\right)^{2}\\&=-\left({\dfrac {k_{i}}{2m}}\right)^{2}\end{aligned}}$

Next, we compute the modularity of the cluster $c_{j}$ before we have added the new node $i$. We already computed this equation:

${\begin{aligned}Q_{j}^{\text{prev}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}}{\dfrac {k_{\mu }}{2m}}\right)^{2}\end{aligned}}$

Finally, we compute the modularity of the cluster $c_{j}$ after we have added a new node $i$:

${\begin{aligned}Q_{j}^{\text{updated}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{2m}}\right)^{2}\end{aligned}}$

We can rewrite the first term as follows:

${\begin{aligned}{\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}A_{\mu \nu }&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2\sum _{\mu =1}^{N_{j}+1}A_{\mu ,N_{j}+1}\right]\\&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]\end{aligned}}$

where $k_{i}^{(j)}$ represents the sum of the weights of all the edges which go between node $i$ and the nodes in community $c_{j}$. In other words, $k_{i}^{(j)}$ is the degree of node $i$ within community $c_{j}$.

We can rewrite the second term as:

${\begin{aligned}\left(\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{2m}}\right)^{2}&=\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}{\dfrac {k_{\mu }k_{\nu }}{(2m)^{2}}}\\&=\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}{\dfrac {k_{\mu }k_{\nu }}{(2m)^{2}}}+2k_{N_{j}+1}\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{(2m)^{2}}}+{\dfrac {(k_{N_{j}+1})^{2}}{(2m)^{2}}}\\&={\dfrac {1}{(2m)^{2}}}\left[\left(\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}\right)\left(\sum _{\nu =1}^{N_{j}}k_{\nu }+k_{N_{j}+1}\right)\right]\\&=\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\end{aligned}}$

Putting this together we have:

${\begin{aligned}Q_{j}^{\text{updated}}&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]-\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\end{aligned}}$

Putting together the equations for $Q_{i}^{\text{prev}}$,$Q_{j}^{\text{prev}}$, and $Q_{j}^{\text{updated}}$, we can compute the change in modularity $\Delta Q$ for adding an isolated node $i$ to the cluster $c_{j}$. This is sometimes referred to as the gain:

$${\begin{aligned}\Delta Q&=Q_{j}^{\text{updated}}-Q_{j}^{\text{prev}}-Q_{i}^{\text{prev}}\\&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]-\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\\&-\left[{\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}}{\dfrac {k_{\mu }}{2m}}\right)^{2}-\left({\dfrac {k_{i}}{2m}}\right)^{2}\right]\end{aligned}}$$

3. Once the change in modularity $\Delta Q$ has been computed for all communities $\{c_{j}\}$ that node $i$ is connected to, node $i$ is placed into the community that resulted in the greatest modularity increase. If no increase is possible, node $i$ remains in its original community.

4. This process is applied repeatedly and sequentially to all nodes until no modularity increase can occur. Once this local maximum of modularity is hit, the first phase has ended.

Steps 3 and 4: Nodes are assigned to communities based on their modularities

Phase 2:

The second phase of the algorithm involves reducing communities to a single node and repeating the steps in Phase 1:

1. Each community $c_{j}$ is reduced to a single node. Links between nodes in $c_{j}$ are reduced to a single weighted self-loop for this community. Likewise edges connecting nodes from $c_{j}$ to other communities are reduced to a single weighted edge.

Phase 2, step 1: Communities are reduced to a single node with weighted edges

2. Once the new graph is created, the second phase has ended and the first phase can be re-applied to the new network.

Final Result: Phase 1 is repeated and nodes are added to communities. Here is shown the result repeating phase 1 before collapsing the communities again

Previous uses

• Twitter social Network (2.4 Million nodes, 38 million links) by Josep Pujol, Vijay Erramilli, and Pablo Rodriguez: The authors explore the problem of partitioning Online Social Networks onto different machines.
• Mobile phone Network (4 Million nodes, 100 Million links) by Derek Greene, Donal Doyle, and Padraig Cunningham: Community-tracking strategies for identifying dynamic communities of different dynamic social networks.
• Detecting species in network-based dynamical model.

Disadvantages

A graph illustrating how communities can become disconnected when using the Louvain algorithm.

Louvain produces only non-overlapping communities, which means that each node can belong to at most one community. This is highly unrealistic in many real-world applications. For example, in social networks, most people belong to multiple communities: their family, their friends, their co-workers, old school buddies, etc. In biological networks, most genes or proteins belong to more than one pathway or complex. Furthermore, Louvain has been shown to sometimes produce arbitrarily badly connected communities, and has been effectively superseded (at least in the non-overlapping case) by the Leiden algorithm.

These badly connected communities arise when a node that had been acting as a "bridge" between two groups of nodes in its community is moved to a new community, leaving the old one disconnected. The remaining nodes in the old community may also be relocated, but if their connection to the community is strong enough despite the removal of the "bridge" node, they will instead remain in place. While this is the worst-case scenario, there are other, more subtle problems with the Louvain algorithm that can also lead to arbitrarily badly connected communities, such as the formation of communities using nodes that are only weakly connected.

Another common issue with the Louvain algorithm is the resolution limit of modularity - that is, multiple small communities being grouped together into a larger community. This causes the smaller communities to be hidden. Both this and the arbitrarily badly connected community problem are further exasperated by each iteration of the algorithm. Ultimately, the only thing the Louvain algorithm guarantees is that the resulting communities cannot be merged further; in other words, they're well-separated. To avoid the problems that arise from arbitrarily badly connected communities and the resolution limit of modularity, it is recommended to use the Leiden algorithm instead, as its refinement phase and other various adjustments have corrected these issues.

Time complexity and comparison to other methods of non-overlapping community detection

Generally, the Louvain method is assumed to have a time complexity of $O(n\log {}n)$. Richard Blondel, co-author of the paper that originally published the Louvain method, seems to support this notion, but other sources claim the time complexity is "essentially linear in the number of links in the graph," meaning the time complexity would instead be $O(m)$, where $m$ is the number of edges in the graph. Unfortunately, no source has published a rigorous analysis of the time complexity so nothing can be said with certainty except that, based on empirical evidence like the table below, Louvain is faster than previous algorithms.

When comparing modularity optimization methods, the two measures of importance are the speed and the resulting modularity value. A higher speed is better as it shows a method is more efficient than others and a higher modularity value is desirable as it points to having better-defined communities. The compared methods are, the algorithm of Clauset, Newman, and Moore, Pons and Latapy, and Wakita and Tsurumi.

Modularity Optimization Comparison

	Karate	Arxiv	Internet	Web nd.edu	Phone	Web uk-2005	Web WebBase 2001
Nodes/links	34/77	9k/24k	70k/351k	325k/1M	2.6M/6.3M	39M/783M	118M/1B
Clauset, Newman, and Moore	.38/0s	.772/3.6s	.692/799s	.927/5034s	-/-	-/-	-/-
Pons and Latapy	.42/0s	.757/3.3s	.729/575s	.895/6666s	-/-	-/-	-/-
Wakita and Tsurumi	.42/0s	.761/0.7s	.667/62s	.898/248s	.56/464s	-/-	-/-
Louvain Method	.42/0s	.813/0s	.781/1s	.935/3s	.769/134s	.979/738s	.984/152mn

-/- in the table refers to a method that took over 24hrs to run. This table (from) shows that the Louvain method outperforms many similar modularity optimization methods in both the modularity and the time categories.

See also

• Leiden algorithm
• Modularity (networks)
• Community structure
• Network science
• K-means clustering

References

• "The Louvain method for community detection in large networks" Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html