Source-linked AI summary
Benchmark graphs for testing community detection algorithms
Andrea Lancichinetti, Santo Fortunato, Filippo Radicchi
TL;DR
Community-detection algorithms lack realistic, discriminating benchmarks because standard artificial graphs simplify node degrees, community sizes, and network scale. The paper introduces a benchmark with heterogeneous degree and community-size distributions, then tests modularity optimization and Potts-model clustering. The benchmark is a more severe test that exposes limitations including modularity’s resolution limit and performance dependence on graph size and link density.
Problem
Community-detection testing remains difficult because standard generated benchmarks do not reflect the heterogeneous properties of real networks.
Method
The paper constructs benchmark graphs with power-law degree and community-size distributions, controls internal and external connectivity, and applies two community-detection methods.
Results
The new benchmark poses a harder test than standard benchmarks and reveals modularity’s resolution limit and dependence on graph size and link density.
Takeaways & Limitations
Realistic heterogeneity and variable graph scale should be included when testing community-detection algorithms.
Abstract
from arXiv · showhide
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 new class of benchmark graphs, that account for the heterogeneity in the distributions of node degrees and of community sizes. We use this new benchmark to test two popular methods of community detection, modularity optimization and Potts model clustering. The results show that the new benchmark poses a much more severe test to algorithms than standard benchmarks, revealing limits that may not be apparent at a first analysis.
I. INTRODUCTION
Reliable community-detection testing remains difficult because standard benchmarks use simplified structures that poorly represent real networks. The paper proposes a benchmark incorporating heterogeneous node degrees and community sizes.
- Motivation: Testing community-detection algorithms requires estimating accuracy and comparing methods, but this issue has received less attention than algorithm design.
- Existing benchmarks: Standard tests use generated networks with known communities because real networks rarely provide precisely identified modules.
- Existing benchmarks: The GN benchmark contains 128 nodes in four equal groups, with approximately uniform degree and an external-degree parameter kout.
- Benchmark limitations: Its main caveats are uniform node degrees, equal community sizes, and a small network.
- Benchmark limitations: Real networks instead exhibit heterogeneous, often power-law degree distributions and broad community-size distributions.
- Proposed benchmark: The proposed benchmark accounts for heterogeneity in both degree and community size, creating a more realistic and challenging test.
II. THE BENCHMARK
The benchmark generates graphs with power-law degree and community-size distributions while controlling each node’s internal and external connectivity. Its construction preserves degree sequences, enforces approximate mixing levels, and scales to large networks, though convergence can occasionally fail.
- Design assumptions: The benchmark assumes power-law degree and community-size distributions with exponents γ and β, respectively.
- Construction: Nodes receive power-law-distributed degrees, and the configuration model connects them while preserving the degree sequence.
- Construction: Each node assigns fraction 1 −µ of its links internally and fraction µ externally, where µ is the mixing parameter.
- Construction: Community sizes follow a power law, with bounds chosen so nodes of every degree can fit into at least one community.
- Construction: Rewiring preserves all node degrees while adjusting internal and external links to approximate the desired mixing fraction.
- Performance and limitations: The procedure scales linearly with the number of links and can construct networks of up to 10^5−10^6 nodes in reasonable time.
- Performance and limitations: For small-degree nodes, discrete feasible mixing values prevent the realized µ distribution from being a delta function around the target.
III. TESTS
The benchmark is used to test modularity optimization and Potts model clustering under heterogeneous graph structures, exposing performance limits that standard benchmarks may miss.
- The authors test modularity optimization and Potts model clustering using the new benchmark graphs.
- The benchmark tests algorithmic complexity by varying average degree, exponents γ and β, mixing parameter µ, and graph size.
- Modularity optimization: Modularity optimization performs well on the GN benchmark until kout = 6, then begins to fail, although it still finds good partitions for fuzzy communities.
- Modularity optimization: On the new benchmark, modularity optimization begins to fail even when communities are only loosely connected, revealing its intrinsic resolution limit.
- Modularity optimization: The detected partition systematically contains fewer clusters because small communities are merged into larger groups.
- Modularity optimization: Performance improves with larger average degree and worsens when community sizes become more similar, corresponding to larger β.
IV. SUMMARY
The paper introduces benchmark graphs incorporating heterogeneity in node degrees and community sizes, making community-detection tests more demanding. The benchmark also supports systematic analysis of how graph size and link density affect algorithm performance.
- The new benchmark extends the GN graphs with heterogeneous node-degree and community-size distributions found in real networks.
- The benchmark poses a harder test to existing community-detection methods than standard benchmarks.
- Tests of modularity optimization reveal the resolution limit immediately on the new benchmark.
- Graph size and link density have a sizeable effect on algorithm performance, so both dependencies should be studied when testing new algorithms.
- The benchmark graphs can be constructed quickly and span several orders of magnitude in network size.