Fast unfolding of community hierarchies in large networks

Abstract

Introduction 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 communities of strongly connected nodes, with the nodes belonging to different communities only sparsely connected. Finding exact optimal partitions in networks is known to be computationally intractable, mainly due to the explosion of the number of possible partitions as the number of nodes increases. It is therefore of high interest to propose algorithms to find reasonably “good” solutions of the problem in a reasonably “fast” way. One of the fastest algorithms consists in optimizing the modularity of the partition in a greedy way (Clauset et al, 2004), a method that, even improved, does not allow to analyze more than a few millions nodes (Wakita et al, 2007).