Benchmark graphs for testing community detection algorithms.

By Andrea Lancichinetti, Santo Fortunato, Filippo Radicchi. Physical review. E, Statistical, nonlinear, and soft matter physics, 2008

2,930 citations recorded by the source corpus.

Community structure is one of the most important features of real networks and reveals the internal organization of the nodes. Many algorithms have been proposed but the crucial issue of testing, i.e., the question of how good an algorithm is, with respect to others, is still open. Standard tests include the analysis of simple artificial graphs with a built-in community structure, that the algorithm has to recover. However, the special graphs adopted in actual tests have a structure that does not reflect the real properties of nodes and communities found in real networks. Here we introduce a class of benchmark graphs, that account for the heterogeneity in the distributions of node degrees and of community sizes. We use this benchmark to test two popular methods of community detection, modularity optimization, and Potts model clustering. The results show that the benchmark poses a much more severe test to algorithms than standard benchmarks, revealing limits that may not be apparent at a first analysis.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/3e0f02e92c6b148c45fc672095ac654000eec5e5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Communities in Networks (2009, methodology): “have been developed to serve those needs [39]. These diﬀering needs have also resulted in the deployment of diﬀerent real and computer-generated benchmark networks to test community-ﬁnding algorithms [39,70]. A 2005 review article [26] compared the performance of several of the (then-)available meth”
Towards Linear Time Overlapping Community Detection in Social Networks (2012, methodology): “For synthetic random networks, we adopted the widely used LFR benchmark(2) [8], which allows heterogeneous distributions of node degrees and community sizes.”
A classification for community discovery methods in complex networks (2011, background): “Various authors have also proposed a benchmark graph, which would be useful to test community discovery algorithms [183].”
Non-overlapping community detection (2018, background): “Lancichinetti, Fortunato and Radicchi (2008) introduced a model based on a rewiring principle, which has obvious advantages over Bagrow’s scheme.”
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, background): “However, it has been recently shown[48] that the Erd€ os-R enyi model behaves at least as well as the configuration modularity on benchmarks [49] and leads to improved results in particular graphs.”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “[91, 94]), in addition to including a robust and formally motivated model-selection procedure.”
Community detection in networks: A user guide (2016, background): “A) (Lancichinetti et al., 2008), Zachary karate club, etc., and the scores are generally good.”
Complex Network Clustering by Multiobjective Discrete Particle Swarm Optimization Based on Decomposition (2014, background): “in [64], which is an extension of the classical GN benchmark proposed by Girvan and Newan in [47].”
Scalable Approach to Uncertainty Quantification and Robust Design of Interconnected Dynamical Systems (2011, positive): “1 Social Network The first example is the Fortunato benchmark graph [36] with 1000 nodes and 99084 edges.”
An efficient and principled method for detecting communities in networks (2011, methodology): “For the synthetic case we use a standard test, the LFR benchmark for unweighted undirected networks with planted community structure [32, 33].”
From Louvain to Leiden: guaranteeing well-connected communities (2018, methodology): “To study the scaling of the Louvain and the Leiden algorithm, we rely on a variant of a well-known approach for constructing benchmark networks 28 .”
Community detection in graphs (2009, methodology): “A realization of the LFR benchmark graphs [326], with 500 vertices.”
Towards real-time community detection in large networks. (2008, methodology): “We follow closely the implementation of the benchmark graphs as described in [12] and compare the original LPA with the improved version on the graphs of size 1000 and 5000.”
Community Discovery in Dynamic Networks (2017, positive): “es. Static Benchmarks. The classic and most famous static benchmarks are the Girvan-Newman (introduced by Girvan and Newman (Girvan and Newman, 2002)) and the LFR (introduced by Lancichinetti et al. (Lancichinetti et al., 2008)). The Girvan-Newman benchmark, also known as GN, is built upon the so-ca”
Using Geodesic Space Density Gradients for Network Community Detection (2017, background): “Index Terms—Complex Networks, Community Detection, Geodesic Space, Geodesic Distance, Density Field Gradients F”