Fast unfolding of community hierarchies in large networks

Vincent D. Blondel, Université catholique de Louvain
Jean-Loup Guillaume, LIP6
Renaud Lambiotte, Université catholique de Louvain
Etienne Lefebre, Université catholique de Louvain

Abstract

Social, technological and information systems can often be described in terms of complex networks that have a topology of interconnected nodes that combines organization and randomness. The typical size of large networks such as social network services, mobile phone networks or the web now counts in millions when not billions of nodes and these scales demand new methods to retrieve comprehensive information from their structure. A promising approach consists in decomposing the networks into sub-units or communities, which are sets of highly connected nodes. The identification of these communities is of crucial importance as they may help to uncover a-priori unknown functional modules such as topics in information networks or cyber-communities in social networks. Moreover, the resulting meta-network, whose nodes are the communities, may then be used to visualize the original network structure. Here we propose a simple community detection method that reveals the hierarchical community structure of networks and that outperforms all other known community detection methods. We use our method to identify language communities and analyze community interactions in a Belgian mobile phone network of 2.6 million customers and we apply it to a web network of 118 million nodes and more than one billion links.