Adaptive cut reveals multiscale complexity in networks

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.