Modular Networks for Validating Community Detection Algorithms

Abstract

How can we accurately compare different community detection algorithms? These algorithms cluster nodes in a given network, and their performance is often validated on benchmark networks with explicit ground-truth communities. Given the lack of cluster labels in real-world networks, a model that generates realistic networks is required for accurate evaluation of these algorithm. In this paper, we present a simple, intuitive, and flexible benchmark generator to generate intrinsically modular networks for community validation. We show how the generated networks closely comply with the characteristics observed for real networks; whereas their characteristics could be directly controlled to match wide range of real world networks. We further show how common community detection algorithms rank differently when being evaluated on these benchmarks compared to current available alternatives.

References in corpus (21)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Community detection algorithms: a comparative analysis
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Kronecker Graphs: An Approach to Modeling Networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• A Scalable Generative Graph Model with Community Structure
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Multifractal Network Generator
• Comparison and validation of community structures in complex networks
• Learning multifractal structure in large networks