View article

Extended Abstract. Networks are everywhere. In many applications, they are used to represent interactions between the different elements of interest. But at the same time as theoretical knowledge and practical tools of graph theory were developed, network sizes grew tremendously. Social networks, which were studied for a few dozens of individuals, are now composed of millions of people sharing online friendships; mobile phone networks have a penetration rate that grew from around 20% in the late nineties to almost 100% nowadays in developed countries; biological networks such as protein-to-protein interactions, may have billions of nodes; etc. Many network properties (degree distribution, average distance or flow propagation for example) have been studied extensively. A key feature of real networks lies in the non-homogeneous local distribution of edges. Each node tends to be more densely connected with a specific subset of the vertices of the graph than with the rest of the network. These structural organizations of nodes are called communities. Extracting communities from large networks have been a challenging problem for years, and a popular class of methods consists of optimizing the so-called modularity. This quality function introduced by Newman and Girvan [1] defines good communities as group of nodes with an internal edge density larger than the associated density expected from the degree distribution of the graph. Optimizing the modularity has been shown to be a NP-complete problem [2] and while many heuristics have been developed for specific contexts, a lot of them are not suitable for a more general framework due …