What is the Louvain Method?

The Louvain Method is an efficient algorithm for hierarchical clustering of nodes in a graph into communities i.e. sets of nodes which are strongly connected internally and weakly connected to other communities. The Louvain method was first introduced in this paper:

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. In Journal of Statistical Mechanics: Theory and Experiment (Vol. 2008, Issue 10, p. P10008). IOP Publishing. DOI: 10.1088/1742-5468/2008/10/p10008

How does the Louvain Method work?

The Louvain Method has two phases which are executed repeatedly: Modularity Optimization and Community Aggregation. In Modularity Optimization nodes are assigned to communities and in Community Aggregation these communities are merged into single nodes.

Modularity Optimization

During Modularity Optimization the Louvain Method tries to find a partition (i.e. the assignment of nodes to communities), which optimizes the modularity of the graph. "The modularity of a partition is a scalar value between -1 and 1 that measures the density of links inside communities as compared to links between communities." (Blondel et. al, 2008). The formula for modularity is:

: weight of edge between  and 
: sum of weights of all edges originating from 
: community to which  has been assigned
: Kronecker delta function,  if ,  otherwise
: sum of all weights of all edges

For initialization each node is first assigned to a community containing only it self. Then for each node and each of its neighbouring communities the change in modularity  for the node being removed from its current community and added to the neighbouring community is calculated. The node is then reassigned to the community with the highest change in modularity or not moved if no change is greater than zero. This is then repeated for every node until no node move can further improve modularity - potentially moving some nodes many times.

Community Aggregation

After the Modularity Optimization is finished, the communities are merged into single nodes. The merging is done by adding the weights of edges between any pair of nodes inside the community and creating a new node for the community with an edge to itself having the sum as weight. Analogously, the weights of edges between any pair of nodes of two different communities are summed up and an edge with this sum as weight is added between the new nodes corresponding to the respective communities.

With the resulting new graph, the whole process can be repeated starting with Modularity Optimization, successively building up a hierarchy of communities.

Visualization

In the visualization you can explore the Louvain Method step-by-step with examples. There is a default example loaded but you can also generate a random graph or edit and create your on graph in a JSON format.

The visualization is based on Cytoscape.js a JavaScript graph visualization library introduced in the paper:

Franz, M., Lopes, C. T., Huck, G., Dong, Y., Sumer, O., & Bader, G. D. (2015). Cytoscape.js: a graph theory library for visualisation and analysis. In Bioinformatics (p. btv557). Oxford University Press (OUP). DOI: 10.1093/bioinformatics/btv557