Comparative evaluation of community detection algorithms: a topological approach

Creative Commons License

Orman G. K. , Labatut V., Cherifi H.

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2012 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Publication Date: 2012
  • Doi Number: 10.1088/1742-5468/2012/08/p08001
  • Keywords: network dynamics, random graphs, networks, network reconstruction, clustering techniques, COMPLEX NETWORKS, IDENTIFICATION


Community detection is one of the most active fields in complex network analysis, due to its potential value in practical applications. Many works inspired by different paradigms are devoted to the development of algorithmic solutions allowing the network structure in such cohesive subgroups to be revealed. Comparative studies reported in the literature usually rely on a performance measure considering the community structure as a partition (Rand index, normalized mutual information, etc). However, this type of comparison neglects the topological properties of the communities. In this paper, we present a comprehensive comparative study of a representative set of community detection methods, in which we adopt both types of evaluation. Community-oriented topological measures are used to qualify the communities and evaluate their deviation from the reference structure. In order to mimic real-world systems, we use artificially generated realistic networks. It turns out there is no equivalence between the two approaches: a high performance does not necessarily correspond to correct topological properties, and vice versa. They can therefore be considered as complementary, and we recommend applying both of them in order to perform a complete and accurate assessment.