Influence of the seed in affine preferential attachment trees

DOI10.3150/19-BEJ1152zbMATH Open1439.05204arXiv1810.13275MaRDI QIDQ2174976FDOQ2174976

Authors: David Corlin Marchand, Ioan Manolescu 

Publication date: 27 April 2020

Published in: Bernoulli (Search for Journal in Brave)

Abstract: We study randomly growing trees governed by the affine preferential attachment rule. Starting with a seed tree $S$, vertices are attached one by one, each linked by an edge to a random vertex of the current tree, chosen with a probability proportional to an affine function of its degree. This yields a one-parameter family of preferential attachment trees $(T_n^S{)}_{ngeq|S|}$, of which the linear model is a particular case. Depending on the choice of the parameter, the power-laws governing the degrees in $T_n^S$ have different exponents. We study the problem of the asymptotic influence of the seed $S$ on the law of $T_n^S$. We show that, for any two distinct seeds $S$ and $S^{\prime }$, the laws of $T_n^S$ and $T_n^{S^{\prime }}$ remain at uniformly positive total-variation distance as $n$ increases. This is a continuation of Curien et al. (2015), which in turn was inspired by a conjecture of Bubeck et al. (2015). The technique developed here is more robust than previous ones and is likely to help in the study of more general attachment mechanisms.

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

Recommendations

• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Scaling limits and influence of the seed graph in preferential attachment trees
• Geometry of weighted recursive and affine preferential attachment trees
• Trees grown under young-age preferential attachment
• Finding the seed of uniform attachment trees

zbMATH Keywords

preferential attachmentseed recognitionBarábasi-Albert trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Martingales with discrete parameter (60G42) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• On the spread of viruses on the Internet
• The degree sequence of a scale-free random graph process
• On random trees
• Scaling limits and influence of the seed graph in preferential attachment trees
• Networks
• Connectivity Transitions in Networks with Super-Linear Preferential Attachment
• Finding Adam in random growing trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Finding the seed of uniform attachment trees

Cited In (5)

• Geometry of weighted recursive and affine preferential attachment trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Finding the seed of uniform attachment trees
• Scaling limits and influence of the seed graph in preferential attachment trees
• Trees grown under young-age preferential attachment

This page was built for publication: Influence of the seed in affine preferential attachment trees

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