PaperlayerView exact revision on arXiv

Source-linked AI summary

Community detection algorithms: a comparative analysis

Andrea Lancichinetti, Santo Fortunato

arXiv:0908.1062v2physics.soc-phphysics.comp-ph

TL;DR

Community-detection algorithms lacked strict evaluation on graph structures resembling real networks. The paper compares a broad algorithm set across heterogeneous benchmarks, GN graphs, and random graphs, finding several strong performers, with Infomap best overall in the examined benchmarks. These results support using the strongest methods for larger and more realistic network analyses, while the benchmark remains an artificial approximation of real systems.

  • Problem

    The reliability of community-detection algorithms is unclear because prior tests often used small networks or simplified artificial graphs unlike real systems.

  • Method

    The paper comparatively tests a representative subset of algorithms on GN, LFR, and random graphs, including directed, weighted, and overlapping-community cases.

  • Results

    Infomap is the best-performing method across the examined benchmarks, while Infomap and Ronhovde–Nussinov recover the planted partition in 100% of cases up to µt ∼1/2 on tested LFR graphs.

  • Takeaways & Limitations

    Infomap, Ronhovde–Nussinov, and Blondel et al. are identified as strong algorithms, with Infomap and Blondel et al. also essentially linear in network size.

Abstract

from arXiv · show

Uncovering the community structure exhibited by real networks is a crucial step towards an understanding of complex systems that goes beyond the local organization of their constituents. Many algorithms have been proposed so far, but none of them has been subjected to strict tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of benchmark graphs, with heterogeneous distributions of degree and community size. The methods are also tested against the benchmark by Girvan and Newman and on random graphs. As a result of our analysis, three recent algorithms introduced by Rosvall and Bergstrom, Blondel et al. and Ronhovde and Nussinov, respectively, have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.

I. INTRODUCTION

Community detection is fundamental for understanding how complex systems are organized, but the reliability of proposed algorithms remains unclear. This paper addresses the gap by comparing methods on benchmarks that better reflect real-network heterogeneity.

  • Community detection seeks densely connected groups that correspond to compartments in complex systems.Finding such compartments may illuminate system organization and function.
  • Algorithm reliability remains difficult to assess because shared definitions of communities and partitions are still missing.The paper describes this uncertainty as persisting despite extensive literature.
  • The GN benchmark uses 128 nodes with expected degree 16, divided into four groups of 32.Its equal degrees and equal community sizes are identified as drawbacks because they are uncommon in real systems.
  • The paper proposes a comparative analysis using the LFR benchmark, then evaluates algorithms on GN, LFR variants, and random graphs.The tests include weighted, directed, and overlapping-community graphs, as well as networks without expected community structure.

II. THE LFR BENCHMARK

The LFR benchmark extends planted-partition graphs with heterogeneous node degrees and community sizes. Its mixing parameter controls external connectivity, while community existence and detectability impose distinct boundaries.

  • The LFR benchmark assigns node degrees and community sizes from power-law distributions, unlike the equal-sized, equal-degree GN setup.Each node keeps its assigned degree throughout graph construction.
  • The mixing parameter µ is the ratio of a node’s external degree to its total degree and replaces pin or pout as the practical control parameter.Under the standard construction, pin and pout are linked once µ is fixed.
  • For node i, kin_i counts links within its community, whereas kout_i counts links to other communities.These quantities define the node’s internal and external connectivity in the benchmark.
  • The condition pin > pout defines communities in the planted-partition model.The benchmark derives this condition by comparing internal and external linking probabilities.
  • When the largest community has size nmax_c, µ < (N − nmax_c)/N safely ensures that all communities are well defined.For the GN benchmark, this becomes µ < 3/4, although detectability can fail earlier because graph fluctuations may resemble randomness.

III. COMPARING PARTITIONS

The paper compares detected and expected partitions using information-theoretic similarity measures. Normalized mutual information addresses a limitation of raw mutual information and provides a standard partition-comparison scale.

  • Algorithmic partitions are evaluated against expected partitions using quantitative similarity measures.The fraction of correctly identified nodes is noted as an earlier measure, while information-theoretic measures are described as reliable alternatives.
  • Partition comparison represents cluster labels as random variables X and Y with joint probabilities based on cluster overlaps.The overlap nxy and cluster sizes determine the distributions used for information calculations.
  • Mutual information I(X, Y) measures how much learning Y reduces uncertainty about X.It is expressed as H(X) − H(X|Y), linking mutual information to entropy and conditional entropy.
  • Raw mutual information can assign the same value to partitions that further subdivide clusters in substantially different ways.This motivates using normalized mutual information for community-detection tests.
  • Normalized mutual information equals 1 for identical partitions and has expected value 0 for independent partitions.The paper notes that it is widely used in community-detection evaluations.

IV. THE ALGORITHMS

The paper compares a representative set of community-detection algorithms spanning diffusion, information compression, spectral, Bayesian, Potts-model, divisive, modularity, and clique-based approaches. The methods differ substantially in optimization strategy, computational complexity, and ability to handle overlapping communities.

  • The study evaluates a representative subset of algorithms because the number of existing community-detection techniques is too large for exhaustive analysis.Particularly slow methods were excluded a priori.
  • The Girvan–Newman algorithm iteratively removes links by edge betweenness and stops when modularity is maximized, with complexity O(N^3) on sparse graphs.
  • Modularity methods range from fast greedy optimization and simulated annealing to Blondel et al.’s multistep local optimization with community aggregation.The fast greedy method has complexity O(N log^2 N) on sparse graphs, while simulated annealing improves precision at the expense of speed.
  • Rosvall and Bergstrom’s structural method compresses graph-structure information, whereas its dynamic counterpart compresses a random walk using Minimum Description Length and is called Infomap.
  • Other evaluated approaches include spectral clustering, expectation-maximization, Potts-model optimization, diffusion, and local methods for overlapping communities.The RN Potts approach uses a resolution parameter and has slightly superlinear complexity in the number of links; Cfinder identifies communities by rolling k-cliques and can be computationally expensive as graph size grows.

V. TESTS ON THE GN BENCHMARK

On the GN benchmark, most algorithms perform well at low mixing but begin failing before the theoretical community-existence threshold. Modularity-based methods and several newer approaches perform particularly strongly, while Cfinder fails even when communities are clearly separated.

  • 100-realization averages show that most methods perform well initially but begin failing substantially before the theoretical mixing threshold µt = 0.75.
  • Cfinder fails to detect GN communities even when µt is approximately zero because clique exploration can cross groups and merge them into much larger communities.
  • Modularity-based methods generally outperform MCL and Radicchi et al. on the GN benchmark, with simulated annealing, Clauset et al., and Blondel et al. performing well.
  • DM and RN perform comparably to exhaustive modularity optimization by simulated annealing, while GN performs about as well as MCL.
  • Both Rosvall and Bergstrom methods recover the planted four-cluster partition consistently up to approximately µt = 0.4.

VI. TESTS ON THE LFR BENCHMARK

The LFR evaluation extends testing beyond the GN benchmark by considering heterogeneous benchmark variants with weighted, directed, and overlapping communities. Performance is measured using normalized mutual information averaged over repeated realizations.

  • The LFR tests cover benchmark variants with weighted or unweighted links, directed or undirected links, and overlapping communities.
  • Each LFR test averages normalized mutual information over 100 realizations for every mixing-parameter value.

A. Undirected and unweighted graphs

On the undirected, unweighted LFR benchmark, algorithm performance varies with network and community size. Infomap, Ronhovde and Nussinov, and Blondel et al. perform best, while larger graphs and communities expose important differences.

  • The LFR benchmark discriminates algorithm performance better than the GN benchmark, while most modularity-based methods worsen for larger systems and smaller communities.
  • Cfinder, MCL, and Radicchi et al. perform worse for larger communities but remain relatively insensitive to network size.
  • Infomap, RN, and Blondel et al. are the best-performing algorithms on the undirected, unweighted LFR benchmark.
  • On graphs with 50000 and 100000 nodes, Blondel et al. performs worse than on smaller graphs, whereas Infomap remains stable.

B. Directed and unweighted graphs

The study extends evaluation to directed, unweighted networks, where ignoring link direction can reduce or mislead structural information. It compares Infomap with exhaustive modularity optimization using simulated annealing on the directed LFR benchmark.

  • Directed links can contain essential network information, and neglecting them may produce partial or misleading community-detection results.
  • The directed LFR benchmark enables evaluation of community-detection algorithms on directed graphs.
  • The comparison tests Infomap against exhaustive modularity optimization via simulated annealing on directed, unweighted LFR graphs.

C. Undirected and weighted graphs

The weighted-network analysis evaluates community detection on undirected graphs while preserving both topology and link-weight information. The weighted LFR benchmark introduces separate topological and weighted mixing parameters.

  • Ignoring link weights may conceal important features of real systems that cannot be deduced from topology alone.
  • The weighted LFR benchmark uses topological mixing µt and weighted mixing µw to represent external links by topology and node strength.
  • The weighted benchmark additionally sets the strength-distribution exponent to 1.5 and varies one mixing parameter while fixing the other.
  • In the extreme of high topological mixture and large communities, the tested method fails for every value of µw.
  • Modularity optimization appears more sensitive to community size than to the other parameters.

D. Undirected and unweighted graphs with overlapping communities

The Cfinder is evaluated on LFR networks with overlapping communities by varying the fraction of overlapping nodes and network size. Performance depends on clique size and community size, and improves on larger networks.

  • The tests vary the fraction of overlapping nodes on LFR networks with undirected, unweighted links and fixed benchmark parameters.Figures 6 and 7 use networks of 1000 and 5000 nodes, respectively.
  • Triangles (k = 3) yield the worst performance, whereas 4- and 5-cliques give better results.
  • Cfinder performs better when communities are smaller, with tested community-size ranges of 10–50 and 20–100 nodes.
  • Cfinder performs better on the 5000-node networks of Fig. 7 than on the 1000-node networks of Fig. 6.

VII. TESTS ON RANDOM GRAPHS

The paper tests community detection methods on Erdős–Rényi and scale-free random graphs, where no community structure is expected. The methods differ substantially in how many modules they report as average degree changes.

  • The tests use Erdős–Rényi graphs with binomial degree distributions and scale-free graphs with power-law degree distributions, all containing 1000 nodes.
  • Each plotted point averages the number of modules found over 100 graph realizations as a function of average degree.
  • The EM results are omitted because the number of modules must be supplied as input, and GN is omitted because it is too slow for the analysis.
  • Radicchi et al. always finds a single cluster comprising all nodes, while MCL can find as many clusters as nodes depending on average degree.
  • Modularity-based methods always find a few clusters even at large average degree, whereas Infomod and RN find non-trivial partitions across average-degree values.

VIII. SUMMARY

The comparative analysis evaluates community detection algorithms on GN and LFR benchmarks and random graphs, including weighted, directed, and overlapping cases. Infomap performs best overall, while Blondel et al. and RN also perform well, although benchmark realism and hierarchical structure remain limitations.

  • The analysis covers GN and LFR benchmarks and random graphs, with dedicated tests for link direction, weights, and overlapping communities.
  • Infomap is the best-performing method across the examined benchmarks, with especially encouraging results on the more difficult LFR graphs.
  • Blondel et al. and RN also perform well and could be used alongside Infomap to extract algorithm-independent information.
  • The artificial LFR graphs remain different from real systems because their clustering coefficient is very low, although triangles could be added to improve the benchmark.
  • The analysis uses flat community structures without hierarchy, whereas many real networks have hierarchical communities.
Loading 0908.1062v2…