Adaptive cut reveals multiscale complexity in networks
- 1Department of Applied Mathematics and Computer Science, Technical University of Denmark , Lyngby ,
- 2Copenhagen Center for Social Data Science (SODAS), University of Copenhagen , Copenhagen ,
- 3School of Data Science, University of Virginia , Charlottesville, Virginia ,
Abstract
Hierarchical clustering and community detection are important problems in machine learning and complex network analysis. A common approach to identify clusters is to simply cut dendrograms at some threshold. However, single-level cuts are often suboptimal in terms of capturing underlying structure in the data, especially when the dendrogram is unbalanced. In this paper, we present the adaptive cut, a method that uses the hierarchical structure of dendrograms through multi-level cuts to overcome the limitations of single-level approaches. The adaptive cut optimizes an objective function using a Markov chain Monte Carlo with simulated annealing, resulting in better partitions. We demonstrate the adaptive cut through applications to link clustering and modularity optimization, but note that the method is applicable to any clustering task that relies on a dendrogram and an objective function. Beyond the adaptive cut, we introduce the balancedness score, an information-theoretic metric that quantifies how balanced a dendrogram is. Balancedness predicts the potential benefits of using multi-level cuts. For the community detection examples, we evaluate our method on more than 200 real-world networks and multiple synthetic datasets, demonstrating improvements in partition density and modularity over traditional single-cut approaches. We also show the generality of the adaptive cut by applying it across hierarchical clustering techniques and objective functions. The adaptive cut improves clustering outcomes across a range of hierarchical clustering tasks.
Related
- From Airspace Degradation to Deconfliction: Predicting Safety-Critical Traffic States through the Evolution of Multiscale Complexity Metrics
- A Brownian dynamics study of liquid–liquid phase separation in multiscale chromatin networks
- Multiscale Reconstruction of Multiplex Networks with Higher-Order Interactions
- Multiscale Renormalization of Weighted Networks
- Making the Graph Laplacian Physical: Multiscale Coarse-Graining in Electrical Oscillator Networks
BibTeX
@article{boucherie2026adaptive,
title = {{Adaptive cut reveals multiscale complexity in networks}},
author = {Louis Boucherie and Yong-Yeol Ahn and Sune Lehmann},
journal = {PNAS Nexus},
year = {2026},
month = oct,
doi = {10.1093/pnasnexus/pgag344},
url = {https://academic.oup.com/pnasnexus/advance-article/doi/10.1093/pnasnexus/pgag344/8868688},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Adaptive cut reveals multiscale complexity in networks
AU - Louis Boucherie
AU - Yong-Yeol Ahn
AU - Sune Lehmann
PY - 2026
DA - 2026/10/06
JO - PNAS Nexus
DO - 10.1093/pnasnexus/pgag344
UR - https://academic.oup.com/pnasnexus/advance-article/doi/10.1093/pnasnexus/pgag344/8868688
AB - Hierarchical clustering and community detection are important problems in machine learning and complex network analysis. A common approach to identify clusters is to simply cut dendrograms at some threshold. However, single-level cuts are often suboptimal in terms of capturing underlying structure in the data, especially when the dendrogram is unbalanced. In this paper, we present the adaptive cut, a method that uses the hierarchical structure of dendrograms through multi-level cuts to overcome the limitations of single-level approaches. The adaptive cut optimizes an objective function using a Markov chain Monte Carlo with simulated annealing, resulting in better partitions. We demonstrate the adaptive cut through applications to link clustering and modularity optimization, but note that the method is applicable to any clustering task that relies on a dendrogram and an objective function. Beyond the adaptive cut, we introduce the balancedness score, an information-theoretic metric that quantifies how balanced a dendrogram is. Balancedness predicts the potential benefits of using multi-level cuts. For the community detection examples, we evaluate our method on more than 200 real-world networks and multiple synthetic datasets, demonstrating improvements in partition density and modularity over traditional single-cut approaches. We also show the generality of the adaptive cut by applying it across hierarchical clustering techniques and objective functions. The adaptive cut improves clustering outcomes across a range of hierarchical clustering tasks.
SN - 2752-6542
ER -