Hierarchical benchmark graphs for testing community detection algorithms

Abstract

Hierarchical organization is an important, prevalent characteristic of complex systems; in order to understand their organization, the study of the underlying (generally complex) networks that describe the interactions between their constituents plays a central role. Numerous previous works have shown that many real-world networks in social, biologic and technical systems present hierarchical organization, often in the form of a hierarchy of community structures. Many artificial benchmark graphs have been proposed in order to test different community detection methods, but no benchmark has been developed to throughly test the detection of hierarchical community structures. In this study, we fill this vacancy by extending the Lancichinetti-Fortunato-Radicchi (LFR) ensemble of benchmark graphs, adopting the rule of constructing hierarchical networks proposed by Ravasz and Barabási. We employ this benchmark to test three of the most popular community detection algorithms, and quantify their accuracy using the traditional Mutual Information and the recently introduced Hierarchical Mutual Information. The results indicate that the Ravasz-Barabási-Lancichinetti-Fortunato-Radicchi (RB-LFR) benchmark generates a complex hierarchical structure constituting a challenging benchmark for the considered community detection methods.

9 pages, 9 figures

References in corpus (18)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• 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
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Evaluating Local Community Methods in Networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Multifractal Network Generator