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