The rank and layer distributions in random recursive trees

2026/08/05 by Huck Stepanyants, P. L. Krapivsky, Harrison Hartle +1
Mathematics · Physics and Astronomy · #math.PR #cond-mat.stat-mech #physics.soc-ph #msc:60C05 #msc:05C05 #msc:05C80

paper · pdf

arxiv created 2026/08/05 · arxiv updated 2026/08/06

Abstract

The distribution of node depths in a network is crucial for analyzing network structure. Two measures, rank and layer, quantify how deep inside a network a node is. The rank is the node's distance to the closest leaf, a node of degree 1. The layer is the number of times all leaves must be stripped off for the node to become a leaf. We derive exact recursive expressions for the rank and layer distributions in random recursive trees. We show that the rank and layer distributions decay factorially and geometrically, respectively, and prove the self-averaging of the numbers of nodes with fixed rank or layer. Unlike previous studies, our approach does not depend on labels or a root node, providing a more versatile framework for analyzing rank and layer distributions in complex networks.

Citations

• Statistics of leaves in growing random trees
• A Clarified Typology of Core-Periphery Structure in Networks
• Core–periphery structure in directed networks
• Finding multiple core-periphery pairs in networks
• k-protected vertices in unlabeled rooted plane trees
• Emergence of core-peripheries in networks
• Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
• Identification of core-periphery structure in networks
• Protected nodes and fringe subtrees in some random trees
• Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis
• Core-Periphery Structure in Networks
• A model of Internet topology using k -shell decomposition
• K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases
• k-Core Organization of Complex Networks
• Core-periphery organization of complex networks
• Front propagation into unstable states
• Extreme value statistics and traveling fronts: Application to computer science
• Models of core/periphery structures
• Traveling Waves, Front Selection, and Exact Nontrivial Exponents in a Random Fragmentation Problem
• Shift in the velocity of a front due to a cutoff
• Network structure and minimum degree