Source-linked AI summary
Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
Scott Emmons, Stephen Kobourov, Mike Gallant, Katy Börner
TL;DR
The paper addresses uncertainty about how network cluster-quality metrics relate and whether benchmark evaluations support consistent algorithm comparisons. It experimentally compares four algorithms and six metrics across synthetic and empirical graphs at multiple scales, finding substantial metric disagreement and favoring conductance among stand-alone measures. The authors therefore reject absolute algorithm-superiority claims and emphasize domain-specific evaluation.
Problem
The study addresses the limited understanding of how stand-alone quality metrics, information recovery metrics, and metric choice affect network clustering evaluation.
Method
The paper evaluates Louvain, Infomap, label propagation, and smart local moving using modularity, conductance, coverage, adjusted Rand score, normalized mutual information, and its cover-based variant on synthetic and empirical graphs.
Results
The metrics disagree overall; conductance is the best stand-alone indicator of information recovery, while the normalized mutual information variant can differ significantly from traditional normalized mutual information.
Takeaways & Limitations
Metric discrepancies prevent declaring smart local moving absolutely superior, so practitioners should test algorithm effectiveness in their respective domains.
Takeaways & Limitations
Benchmark conclusions are constrained by synthetic-model assumptions, including power-law node-degree distributions, and by the absence of a universal mathematical definition of community.
Abstract
from arXiv · showhide
Notions of community quality underlie network clustering. While studies surrounding network clustering are increasingly common, a precise understanding of the realtionship between different cluster quality metrics is unknown. In this paper, we examine the relationship between stand-alone cluster quality metrics and information recovery metrics through a rigorous analysis of four widely-used network clustering algorithms -- Louvain, Infomap, label propagation, and smart local moving. We consider the stand-alone quality metrics of modularity, conductance, and coverage, and we consider the information recovery metrics of adjusted Rand score, normalized mutual information, and a variant of normalized mutual information used in previous work. Our study includes both synthetic graphs and empirical data sets of sizes varying from 1,000 to 1,000,000 nodes. We find significant differences among the results of the different cluster quality metrics. For example, clustering algorithms can return a value of 0.4 out of 1 on modularity but score 0 out of 1 on information recovery. We find conductance, though imperfect, to be the stand-alone quality metric that best indicates performance on information recovery metrics. Our study shows that the variant of normalized mutual information used in previous work cannot be assumed to differ only slightly from traditional normalized mutual information. Smart local moving is the best performing algorithm in our study, but discrepancies between cluster evaluation metrics prevent us from declaring it absolutely superior. Louvain performed better than Infomap in nearly all the tests in our study, contradicting the results of previous work in which Infomap was superior to Louvain. We find that although label propagation performs poorly when clusters are less clearly defined, it scales efficiently and accurately to large graphs with well-defined clusters.
Introduction
The paper examines whether benchmark-based information recovery adequately evaluates network clustering and how metric choice affects algorithm comparisons. It compares multiple metrics and algorithms across synthetic graphs, real-world networks, and graph sizes from 1,000 to 1,000,000 nodes.
- Benchmark graphs embed known clusterings treated as gold standards for measuring how much information algorithms recover.
- Relying only on benchmark performance assumes the embedded clustering captures the entirety of algorithm performance, while overlooking modularity, conductance, and coverage.
- Previous benchmark studies commonly used one information recovery metric, leaving the effect of metric choice insufficiently evaluated.
- The experiments measure information recovery and cluster quality for algorithms on graphs ranging from 1,000 nodes and 12,400 edges to 1M nodes and 13.3M edges, then test Flickr and DBLP networks.
- The study asks how information recovery metrics affect rankings, how performance scales with graph size, and how benchmark results compare with real-world graphs.
Methods
The methods combine LFR synthetic benchmarks and empirical networks with four scalable clustering algorithms and several stand-alone and information-recovery metrics. The study emphasizes how graph structure, metric definitions, and metric trade-offs affect evaluation.
- Benchmark and Empirical Graphs: LFR benchmarks vary cluster structure through a mixing parameter µ, with larger µ making embedded communities harder to detect.
- Benchmark and Empirical Graphs: The evaluation uses LFR graphs and Flickr and DBLP networks, including datasets with 105,938 and 317,080 nodes.
- Clustering Algorithms: The four compared algorithms are Louvain, smart local moving, Infomap, and label propagation, each designed to scale beyond one million nodes.
- Cluster Quality Metrics: Modularity, conductance, and coverage are normalized from 0 to 1, with 1 representing the optimal score.
- Cluster Quality Metrics: Conductance emphasizes inter-cluster sparsity but does not fully capture intra-cluster density, whereas coverage captures intra-cluster density but can favor assigning all nodes to one cluster.
- Information Recovery Metrics: Information recovery uses adjusted Rand score, traditional normalized mutual information, and a cover-based normalized mutual information variant.
Results
Across synthetic and real-world graphs, cluster-quality metrics often disagree with information recovery and with one another, complicating absolute algorithm rankings. Conductance aligns best with benchmark performance, while algorithm outcomes depend on graph size, cluster definition, and metric choice.
- Synthetic graph results: Performance generally decreases as the mixing parameter µ and network size increase, reflecting less-defined clusters and scale-related limitations.The study attributes these declines to LFR parameters, modularity’s resolution limit, and the field-of-view limit.
- Information recovery metrics: At µ = 0.40 and N = 1,000,000, Lancichinetti’s variant ranks label propagation highest, while traditional normalized mutual information and adjusted Rand score rank SLM highest.Louvain outperforms Infomap on traditional normalized mutual information but loses on adjusted Rand score in the same setting.
- Information recovery metrics: Lancichinetti’s normalized mutual information variant differs from the traditional formulation by as much as 0.4 at N = 1,000,000.Therefore, results based solely on the variant cannot be directly applied to traditional normalized mutual information.
- Comparison of cluster quality metrics: Coverage and modularity are unreliable indicators of benchmark performance because they can diverge from information recovery and capture different clustering properties.Coverage can increase as µ rises toward the trivial all-nodes-in-one-cluster case, while modularity can remain stable as information recovery deteriorates.
- Comparison of cluster quality metrics: Conductance best indicates benchmark graph performance in these experiments, although it remains imperfect and sometimes fails to reflect changes in information recovery.In one example, conductance declines alongside all three information recovery metrics while other stand-alone metrics do not.
- Comparison of clustering algorithms: Louvain surpasses Infomap in nearly all experiments, contradicting earlier results; the authors relate this difference to community size and algorithmic limits.The study used Infomap’s bottom hierarchical level, which suffers from the field-of-view limit, while relatively large communities favor Louvain’s resolution-limit behavior.
- Comparison of clustering algorithms: Infomap’s traditional normalized mutual information mean falls from 1.0 at N = 1,000 to 0.70 at N = 1,000,000 when µ = 0.50.Infomap still scales remarkably well to larger graph sizes but experiences performance loss.
- Comparison of clustering algorithms: Label propagation has the widest performance variability: it can outperform other algorithms at µ = 0.40 but rapidly deteriorates at µ = 0.60.Its relative sensitivity to µ and relative insensitivity to size make cluster definition important when selecting algorithms for large networks.
Discussion
The study finds disagreement between stand-alone and information-recovery metrics, limiting claims about universally superior clustering algorithms. It recommends domain-specific evaluation and better alignment among community definitions and metric interpretations.
- Conductance is the best stand-alone quality metric for indicating performance on information recovery, though it remains imperfect.
- Smart local moving performs best overall, but metric disagreement prevents declaring it absolutely superior.
- Benchmark-based conclusions are constrained because LFR graphs encode assumptions such as power-law node-degree distributions, creating circularity in evaluation.
- Practitioners must test clustering effectiveness in their application domain because no rigorous, universally applicable notion of community exists.
- Unifying community notions and clarifying metric-value significance could enable more meaningful claims from cluster quality metrics.