Groupe d’études et de recherche en analyse des décisions

G-2016-33

A new centrality-based approach for fast community detection in graphs

et

In this paper, we propose a new scheme for building algorithms to detect communities in networks. This new approach is based upon a vertex centrality measure and the hypothesis that central vertices, i.e. vertices with high centrality, link distinct communities. It turns out that the betweenness centrality and the centrality based upon the clustering coefficient provide good results, but it is also the case for the eigenvector centrality. These methods are experimented on 11 classical networks and results are compared to those produced by Blondel's algorithm (2008), polynomial-time heuristic optimizing the modularity centrality, and those by an algorithm finding the optimal partition for the modularity centrality. Based on this new approach, the resulting algorithm runs, beyond the centrality computation, in \(O(\max (n\log(n),m))\). These preliminary results are encouraging and will lead to further research for finding appropriate centrality measures and study their performance.

, 12 pages