Influence of the seed in affine preferential attachment trees

DOI10.3150/19-BEJ1152MaRDI QIDQ2174976zbMATH OpenFDO

Authors David Corlin Marchand, Ioan Manolescu

Publication date 27 April 2020

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.13275, https://projecteuclid.org/euclid.bj/1587974520

zbMATH Keywords

Barábasi-Albert treespreferential attachmentseed recognition

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)

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.

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

Cites work

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

Cited in

(6)

• 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
• Detecting a late changepoint in the preferential attachment model

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)