Balancedness: how balanced is a tree?
Oct 20, 2026 · By Louis Boucherie · Writing assisted by AI
Dendrograms come in many shapes. In a balanced dendrogram, every branch splits into parts of about the same size. In an unbalanced one, the splits are uneven. In the extreme case, the caterpillar, every split separates a single leaf from the rest.
Many dendrograms are unbalanced, often because the density of the data varies: dense groups merge low in the tree and sparse groups high up, so the merges are spread over a wide range of heights. This is when a single-level cut fails, as the adaptive cut post shows, because no single height suits all the groups. To measure it, we introduced balancedness, a score based on information theory that goes from 0 for a caterpillar to 1 for a perfectly balanced tree.
Measuring the balancedness of a tree
At each level of the dendrogram, the branches divide the leaves into groups. The Shannon entropy of the group sizes measures how even this division is, but it also grows with the number of groups. So we compare it with its two bounds for the same number of groups: the maximal entropy, when all groups are as equal in size as possible, and the minimal entropy, when every group but one is a single leaf. Where the entropy falls between the two bounds, from 0 to 1, is the evenness at that level. Balancedness is the average evenness over all levels.
Figure 1. Slide split from a caterpillar, where every split separates a single leaf from the rest, to a balanced tree. Middle, as in the paper: the entropy at each level of the tree (pink), between the most balanced split (dashed) and the most unbalanced one (dotted) with the same number of branches. The pink area shows how far the tree gets from the most unbalanced split. Right: balancedness. Hover a level to colour its branches.
The caterpillar sits on the minimal entropy at every level and scores 0. The balanced tree sits on the maximal entropy and scores 1. Every other tree lands somewhere in between.
Many other tree balance indices exist. The closest to ours is the normalized tree balance of Fernández & Gómez (2020), which also averages a Shannon entropy, but over the branching points of the tree rather than over its levels. Working level by level is what makes balancedness relevant for cutting a tree at a given height.
The toy networks
Now back to the two toy networks of the adaptive cut post. The varying-density network scores 0.41, well below the 0.76 of the balanced network. Its dense groups merge low and its sparse groups high, so its merges are spread over a wide range of heights: exactly the case where a single cut struggles.
Figure 2. Link dendrograms of the two toy networks, with the same entropy panel and the balancedness bar; the tick on the bar marks the other network. The dendrogram and the entropy panel share the height axis. Hover either one to colour the branches at that height.
In the paper, we computed balancedness for 202 real networks. Most of their dendrograms are unbalanced, and the lower the balancedness, the more the adaptive cut improves on the single cut.
References
- L. Boucherie, Y.-Y. Ahn and S. Lehmann. Adaptive cut reveals multiscale complexity in networks. PNAS Nexus, pgag344 (2026).
- A. Fernández and S. Gómez. Versatile linkage: a family of space-conserving strategies for agglomerative hierarchical clustering. Journal of Classification 37, 584–597 (2020).
paper · code · adaptive cut