unfolding of community in large network

J
ournal of Statistical Mechanics: Theory and Experiment
An IOP and SISSA journal
Fast unfolding of communities in large networks
J. Stat. Mech. (2008) P10008
Vincent D Blondel1, Jean-Loup Guillaume1,2, Renaud Lambiotte1,3 and Etienne Lefebvre1
Department of Mathematical Engineering, Universit´ Catholique de Louvain, e 4 avenue Georges Lemaitre, B-1348 Louvain-la-Neuve, Belgium 2 LIP6, Universit´ Pierre et Marie Curie, 4 place Jussieu, F-75005 Paris, France e 3 Institute for Mathematical Sciences, Imperial College London, 53 Prince’s Gate, South Kensington Campus, London SW7 2PG, UK E-mail: vincent.blondel@uclouvain.be, jean-loup.guillaume@lip6.fr, r.lambiotte@imperial.ac.uk and pixetus@hotmail.com Received 18 April 2008 Accepted 3 September 2008 Published 9 October 2008 Online at stacks.iop.org/JSTAT/2008/P10008 doi:10.1088/1742-5468/2008/10/P10008
1
Abstract. We propose a simple method to extract the community structure of
large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection methods in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2 million customers and by analysing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also ...