Closed benchmarks for network community structure characterization

Abstract

Characterizing the community structure of complex networks is a key challenge in many scientific fields. Very diverse algorithms and methods have been proposed to this end, many working reasonably well in specific situations. However, no consensus has emerged on which of these methods is the best to use in practice. In part, this is due to the fact that testing their performance requires the generation of a comprehensive, standard set of synthetic benchmarks, a goal not yet fully achieved. Here, we present a type of benchmark that we call "closed", in which an initial network of known community structure is progressively converted into a second network whose communities are also known. This approach differs from all previously published ones, in which networks evolve toward randomness. The use of this type of benchmark allows us to monitor the transformation of the community structure of a network. Moreover, we can predict the optimal behavior of the variation of information, a measure of the quality of the partitions obtained, at any moment of the process. This enables us in many cases to determine the best partition among those suggested by different algorithms. Also, since any network can be used as a starting point, extensive studies and comparisons can be performed using a heterogeneous set of structures, including random ones. These properties make our benchmarks a general standard for comparing community detection algorithms.

18 pages, 5 figures. Available at http://pre.aps.org/abstract/PRE/v85/i2/e026109

References in corpus (14)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Finding statistically significant communities in networks
• Mixture models and exploratory analysis in networks
• Robustness of community structure in networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• Deciphering Network Community Structure by Surprise
• Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering

Cited by in corpus (5)

• Surprise maximization reveals the community structure of complex networks
• Exploring the limits of community detection strategies in complex networks
• SurpriseMe: an integrated tool for network community structure characterization using Surprise maximization
• An algorithm for network community structure determination by surprise
• Bad Communities with High Modularity