Towards realistic artificial benchmark for community detection algorithms evaluation

Abstract

Assessing the partitioning performance of community detection algorithms is one of the most important issues in complex network analysis. Artificially generated networks are often used as benchmarks for this purpose. However, previous studies showed their level of realism have a significant effect on the algorithms performance. In this study, we adopt a thorough experimental approach to tackle this problem and investigate this effect. To assess the level of realism, we use consensual network topological properties. Based on the LFR method, the most realistic generative method to date, we propose two alternative random models to replace the Configuration Model originally used in this algorithm, in order to increase its realism. Experimental results show both modifications allow generating collections of community-structured artificial networks whose topological properties are closer to those encountered in real-world networks. Moreover, the results obtained with eleven popular community identification algorithms on these benchmarks show their performance decrease on more realistic networks.

References in corpus (15)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• Complex cooperative networks from evolutionary preferential attachment
• Evaluating Local Community Methods in Networks
• An Empirical Study of the Relation Between Community Structure and Transitivity
• Effect of size heterogeneity on community identification in complex networks

Cited by in corpus (6)

• On community structure in complex networks: challenges and opportunities
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Centrality in Modular Networks
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Ensemble Clustering for Graphs: Comparisons and Applications
• EC-SBM Synthetic Network Generator