Leaves of preferential attachment trees
- 21 April 2026
- journal article
- Published by IOP Publishing in Journal of Physics A: Mathematical and Theoretical
- Vol. 59 (16) , 165001
Abstract
We provide a local probabilistic description of the limiting statistics of large preferential attachment (PA) trees in terms of the ordinary degree (number of neighbors) but augmented with information on leafdegree (number of neighbors that are leaves). The full description is the joint degree-leafdegree distribution n k , ℓ , which we derive from its associated multivariate generating function. From n k , ℓ we obtain the leafdegree distribution, m ℓ , as well as the fraction of vertices that are protected (nonleaves with leafdegree zero) as a function of degree, n k , 0 , among numerous other results. We also examine fluctuations and concentration of joint degree-leafdegree empirical counts N k , ℓ . Although our main findings pertain to the PA tree, the approach we present is highly generalizable and can characterize numerous existing models, in addition to facilitating the development of tractable new models. We further demonstrate the approach by analyzing n k , ℓ in two other models: the random recursive tree, and a redirection-based model.Keywords
All Related Versions
This publication has 46 references indexed in Scilit:
- The magic of networks grown by redirectionIndian Journal of Physics, 2023
- Barabasi–Albert trees are hypoenergeticBoletín de la Sociedad Matemática Mexicana, 2022
- Asymptotic normality in random graphs with given vertex degreesRandom Structures & Algorithms, 2020
- Sparse graphs: Metrics and random modelsRandom Structures & Algorithms, 2011
- Asymptotic degree distribution in random recursive treesRandom Structures & Algorithms, 2004
- The Diameter of a Scale-Free Random GraphCombinatorica, 2004
- The degree sequence of a scale‐free random graph processRandom Structures & Algorithms, 2001
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- How to deal with unlabeled random graphsJournal of Graph Theory, 1991
- An asymptotic evaluation of the cycle index of a symmetric groupDiscrete Mathematics, 1977