Influence of the seed in affine preferential attachment trees

Wednesday, 31 October, 2018

Published in: 

arXiv:1810.13275

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)_{n\geq|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′, the laws of T_n^S and T_n^{S'} 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.

Author(s): 

David Corlin Marchand
Ioan Manolescu