Adaptive cut reveals multiscale complexity in networks
Oct 20, 2026 · By Louis Boucherie · Writing assisted by AI
Hierarchical clustering builds a tree, called a dendrogram, that goes step by step from single items to one large group. To get clusters, the usual approach is to cut the tree at a single level. The level is chosen by optimizing a measure of how good the groups are (modularity for communities in a network or the silhouette score for clusters of data points).
However, single-level cuts are often suboptimal at capturing the multilevel structure underlying the data, especially when the dendrogram is unbalanced. When dense groups form low in the tree and sparse ones high up, no single threshold fits them all.
Figure 1 shows this on two toy networks with five groups each. In the balanced network they are equally dense, and the best single cut finds all five. In the varying-density network they go from very dense to very sparse, and no single cut can: cut low and the sparse groups fall apart, cut high and the dense ones merge.
Figure 1. Drag the dashed line to move the cut. Left: the network as an adjacency matrix, one square per link, coloured by group (grey: groups with no triangles, mostly single links, which add nothing to the score). Middle: the dendrogram. Right: the partition density of every possible single cut (see below); the circle marks the best one. Bottom: the network itself, with the same colours.
Here we show the adaptive cut, a method that uses the hierarchical structure of the dendrogram to make multi-level cuts and overcome the limitations of a single-level cut.
The figures use link clustering (Ahn, Bagrow & Lehmann, 2010), which groups the links of a network by how similar their neighbourhoods are, so a node can belong to several groups, the way you belong to both a family and a workplace. Each leaf of the dendrogram is a link, and a cut is scored by its partition density: 1 if every group is a clique, 0 if every group is a tree.
Many cuts
But why should the cut be a straight line? The adaptive cut lets it bend to follow the density of the network, low where groups are dense and high where they are sparse. Try it yourself in Figure 2. Click a branch to cut it or merge it, or click a link in the matrix to merge its group with its neighbour, and see whether you can beat the best single cut.
It's harder than it looks. This tree can be cut in about ways, far more than anyone could ever check. So we do the search with Markov chain Monte Carlo (MCMC). At each step it picks a group and proposes a small change: merge it with its neighbouring branch, or split it. A change that raises the partition density is kept. A change that lowers it is sometimes kept anyway, so the chain doesn't get stuck on the first small hill it climbs. That matters most on bigger networks, like the one at the end of this post. How often we keep a move that decreases the partition density is set by the temperature.
Figure 2. Press play to watch the chain. The circle marks the group picked at each step and the arrow the change it proposes (green: kept, red: refused); the matrix outlines the same group. Click a branch below the cut to cut it, a branch above to merge everything under it, or a link in the matrix to merge its group with its neighbour, then press play to carry on from there. The temperature slider sets how hot the chain runs. Bottom: partition density along the run, against the best single cut (dashed) and the best adaptive cut we found (dotted).
On the varying-density network, the chain ends up cutting each group at its own height, low for the dense groups and high for the sparse ones. Its best adaptive cut reaches a partition density of 0.39, against 0.29 for the best single cut. On the balanced network there is nothing to gain, because the best single cut was already the best cut.
So which trees need an adaptive cut? The unbalanced ones. To make that precise we came up with a measure called balancedness, which has a post of its own.
References
- Y.-Y. Ahn, J. P. Bagrow and S. Lehmann. Link communities reveal multiscale complexity in networks. Nature 466, 761–764 (2010).
- L. Boucherie, Y.-Y. Ahn and S. Lehmann. Adaptive cut reveals multiscale complexity in networks. PNAS Nexus, pgag344 (2026).
paper · code · balancedness
Bonus: a bigger network
Just for fun, here is the varying-density network again, made bigger: fifteen groups instead of five, 562 nodes and 4,909 links. The best single cut scores 0.25, and the best adaptive cut we found 0.38.
Figure 3. Same as Figure 2, on the bigger network, with a longer run and a colder chain. Each run is different: press reset and play to try again.
Starting from the best single cut, the chain climbs in steps: long plateaus, then a sudden jump when it finds a better way to cut part of the tree. About two runs in three reach 0.38; the others stay stuck near 0.30. Start it from one cluster and it ends near 0.36 every time, on a different hill. On a landscape this rugged, it pays to run the chain more than once.
Want more? There is an even bigger one, with thirty groups.