Romain Campigotto, Jean-Loup Guillaume and Massoud Seifi
Proceedings of the 5th IEEE/ACM International Conference on Advances in Social Networks and Mining (ASONAM 2013). Niagara Falls, Canada.
Communities are a powerful tool to describe the structure of complex networks. Algorithms aiming at maximizing a quality function called modularity have been shown to effectively compute the community structure. However, some problems remain: in particular, it is possible to find high modularity partitions in graph without any community structure, in particular random graphs. In this paper, we study the notion of consensual communities and show that they do not exist in random graphs. For that, we exhibit a phase transition based on the strength of consensus: below a given threshold, all the nodes belongs to the same consensual community; above this threshold, each node is in its own consensual community.