The Louvain method for community detection in large networks

The Louvain method is a simple, efficient and easy-to-implement method for identifying communities in large networks. The method has been used with success for networks of many different type (see references below) and for sizes up to 100 million nodes and billions of links. The analysis of a typical network of 2 million nodes takes 2 minutes on a standard PC. The method unveils hierarchies of communities and allows to zoom within communities to discover sub-communities, sub-sub-communities, etc. It is today one of the most widely used method for detecting communities in large networks.

A greedy optimization method

The method is a greedy optimization method that attempts to optimize the "modularity" of a partition of the network (modularity is defined here). The optimization is performed in two steps. First, the method looks for "small" communities by optimizing modularity locally. Second, it aggregates nodes belonging to the same community and builds a new network whose nodes are the communities. These steps are repeated iteratively until a maximum of modularity is attained and a hierarchy of communities is produced. Although the exact computational complexity of the method is not known, the method seems to run in time O(n log n) with most of the computational effort spent on the optimization at the first level. Exact modularity optimization is known to be NP-hard.

Reference and origin

The original idea for the method is due to Etienne Lefebvre who first developped it during his Master thesis at UCL (Louvain-la-Neuve) in March 2007. The method was improved and tested with Vincent Blondel, Jean-Loup Guillaume and Renaud Lambiotte and is now known as the "Louvain method" because, even though the co-authors now hold positions in Paris, London and Louvain-la-Neuve, the method was devised when they all were at the Université catholique de Louvain. The method was first published in:

Fast unfolding of communities in large networks,
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre,
Journal of Statistical Mechanics: Theory and Experiment 2008 (10), P10008 (12pp)
doi: 10.1088/1742-5468/2008/10/P10008. ArXiv: http://arxiv.org/abs/0803.0476

Extensions

The method was initially introduced for unweighted and undirected graphs and for the modularity function. It can easily be adapted to weighted and directed graph. The same greedy technique can also be used to optimize objectives that are different from modularity.

Softwares and freely available code

A C++ implementation of the method was written by E. Lefebvre (and later adapted by J.-L. Guillaume) and is freely available for download from http://sites.google.com/site/findcommunities/. For specific comments concerning the C++ code please consult the corresponding readme file or contact Prof. Jean-Loup Guillaume.

A Matlab implementation of the method was written by Antoine Scherrer (ENS Lyon) and is available here for download. For more information on this implementation please consult the readme file; we can't provide any assistance for this implementation.

The method is also implemented in several network analysis softwares, including
NetworkX (see http://perso.crans.org/aynaud/communities/ for comments on the implementation)
Gephi (see http://wiki.gephi.org/index.php/Modularity for comments on the implementation)

References


Fast unfolding of communities in large networks
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
Journal of Statistical Mechanics: Theory and Experiment (10), P10008, 2008.

Thomas Aynaud, Vincent D. Blondel, Jean-Loup Guillaume et Renaud Lambiotte
Optimisation locale multi-niveaux de la modularité (in French)
Chapitre 14 in: Partitionnement de graphe Optimisation et applications, Charles-Edmond Bichot et Patrick Siarry (Eds), Hermes, Paris, 2010.

Andrea Lancichinetti and Santo Fortunato
Community detection algorithms: a comparative analysis
Phys. Rev. E 80, 056117, 2009.

Some studies that use the Louvain method

Twitter social network (2.4M nodes 38M links, Twitter)
Divide and Conquer: Partitioning Online Social Networks
Josep M. Pujol, Vijay Erramilli, Pablo Rodriguez
arXiv 0905.4918, 2010

LinkedIn social network (21M nodes, LinkedIn)
Mapping search relevance to social networks
Jonathan Haynes, Igor Perisic
Proceedings of the 3rd Workshop on Social Network Mining and Analysis, 2010

Audio sharing networks (Freesound)
Community structure in audio clip sharing
Gerard Roma, Perfecto Herrera
International Conference on Intelligent Networking and Collaborative Systems, INCoS 2010

Mobile phone networks (4M nodes, 100M links)
Tracking the Evolution of Communities in Dynamic Social Networks
Greene, D.;   Doyle, D.;   Cunningham, P.; 
International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2010

Flickr 1.8M/22M, LiveJournal 5.3M/77M, YouTube 1.1M/4.5M
Real World Routing Using Virtual World Information
Pan Hui, Sastry N. 
International Conference on Computational Science and Engineering, 2009

Citation network (6M nodes, ISI database)
Subject clustering analysis based on ISI category classification
Lin Zhang, Xinhai Liu, Frizo Janssens, Liming Liang and Wolfgang Glänzel
Journal of Informetrics, Volume 4, Issue 2, April 2010

Retail transaction data network
Market basket analysis with networks
Troy Raeder, Nitesh V. Chawla
Social Network Analysis and Mining, 2010

Human brain functional networks
Hierarchical Modularity in Human Brain Functional Networks
David Meunier, Renaud Lambiotte, Alex Fornito, Karen D. Ersche and Edward T. Bullmore
Neuroinformatics, 3: 37, 2009

Author: Vincent Blondel (vincent.blondel@uclouvain.be)
Version: March 2011