Geometry of weighted recursive and affine preferential attachment trees

DOI10.1214/21-EJP640zbMATH Open1468.05034arXiv1904.07115OpenAlexW3172085584MaRDI QIDQ2042867FDOQ2042867

Authors: Delphin Sénizergues 

Publication date: 21 July 2021

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: We study two models of growing recursive trees. For both models, initially the tree only contains one vertex $u_1$ and at each time $ngeq2$ a new vertex $u_n$ is added to the tree and its parent is chosen randomly according to some rule. In the emph{weighted recursive tree}, we choose the parent $u_k$ of $u_n$ among $u_1,u_2,dots,u_{n-1}$ with probability proportional to $w_k$, where $(w_n{)}_{ngeq1}$ is some deterministic sequence that we fix beforehand. In the emph{affine preferential attachment tree with fitnesses}, the probability of choosing any $u_k$ is proportional to $a_k+mathrm{deg}^{+}(u_k)$, where $mathrm{deg}^{+}(u_k)$ denotes its current number of children, and the sequence of emph{fitnesses} $(a_n{)}_{ngeq1}$ is deterministic and chosen as a parameter of the model. We show that for any sequence $(a_n{)}_{ngeq1}$, the corresponding preferential attachment tree has the same distribution as some weighted recursive tree with a emph{random} sequence of weights (with some explicit distribution). We then prove almost sure scaling limit convergences for some statistics associated with weighted recursive trees as time goes to infinity, such as degree sequence, height, profile and also the weak convergence of some measures carried on the tree. Thanks to the connection between the two models, these results also apply to affine preferential attachment trees.

Full work available at URL: https://arxiv.org/abs/1904.07115

Recommendations

• Correction terms for the height of weighted recursive trees
• Degree distributions in recursive trees with fitnesses
• Influence of the seed in affine preferential attachment trees
• Trees grown under young-age preferential attachment
• Random recursive trees and preferential attachment trees are random split trees

zbMATH Keywords

limit theoremspreferential attachmentprofile of random treesweighted recursive trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Discrete-time Markov processes on general state spaces (60J05)

Cites Work

• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• The Structure and Function of Complex Networks
• Random-walk models of network formation and sequential Monte Carlo methods for graphs
• Title not available (Why is that?)
• Probability. Theory and examples.
• Random Trees
• Inequalities for the $r$th Absolute Moment of a Sum of Random Variables, $1 \leqq r \leqq 2$
• The profile of binary search trees
• The Maximum Degree of the Barabási–Albert Random Tree
• A preferential attachment model with random initial degrees
• Uniform convergence of martingales in the branching random walk
• Asymptotic behavior and distributional limits of preferential attachment graphs
• A survey of random processes with reinforcement
• Degree asymptotics with rates for preferential attachment random graphs
• Title not available (Why is that?)
• Limit theorems for triangular urn schemes
• Branching processes in the analysis of the heights of trees
• Note on the heights of random recursive trees and random m‐ary search trees
• Growing random networks with fitness
• Generalized gamma approximation with rates for urns, walks and trees
• A new family of Markov branching trees: the alpha-gamma model
• A phase transition for preferential attachment models with additive fitness
• Title not available (Why is that?)
• A time-dependent version of Pólya's urn
• Martingales and profile of binary search trees
• A functional limit theorem for the profile of \(b\)-ary trees
• Title not available (Why is that?)
• A line-breaking construction of the stable trees
• Scaling limits of \(k\)-ary growing trees
• Periodic Pólya urns, the density method and asymptotics of Young tableaux
• Joint degree distributions of preferential attachment random graphs
• Scaling limits for some random trees constructed inhomogeneously
• A functional limit law for the profile of plane-oriented recursive trees
• General Edgeworth expansions with applications to profiles of random trees
• Width of a scale-free tree
• Pólya urns with immigration at random times
• Asymptotic results on Hoppe trees and their variations
• Random trees constructed by aggregation
• On the asymptotic behaviour of random recursive trees in random environments
• Random walks with preferential relocations and fading memory: a study through random recursive trees
• Random recursive trees and preferential attachment trees are random split trees

Cited In (23)

• A new kind of geometric structures determining the chain good weight hierarchies
• ON SEVERAL PROPERTIES OF A CLASS OF PREFERENTIAL ATTACHMENT TREES—PLANE-ORIENTED RECURSIVE TREES
• Title not available (Why is that?)
• Degree centrality and root finding in growing random networks
• Degree distributions in recursive trees with fitnesses
• Large deviation principle for a stochastic process with random reinforced relocations
• Decorated stable trees
• Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights
• The maximal degree in random recursive graphs with random weights
• Height of weighted recursive trees with sub-polynomially growing total weight
• Condensation phenomena in preferential attachment trees with neighbourhood influence
• Random recursive trees and preferential attachment trees are random split trees
• On a sufficient condition for explosion in CMJ branching processes and applications to recursive trees
• Recognizing Geometric Trees as Positively Weighted Straight Skeletons and Reconstructing Their Input
• Depths in random recursive metric spaces
• Root finding algorithms and persistence of Jordan centrality in growing random trees
• Influence of the seed in affine preferential attachment trees
• Dynamical models for random simplicial complexes
• Scaling limits and influence of the seed graph in preferential attachment trees
• Stable graphs: distributions and line-breaking construction
• Trees grown under young-age preferential attachment
• Correction terms for the height of weighted recursive trees
• Growing random graphs with a preferential attachment structure

This page was built for publication: Geometry of weighted recursive and affine preferential attachment trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2042867)