Vertices of high degree in the preferential attachment tree

Abstract

We study the basic preferential attachment process, which generates a sequence of random trees, each obtained from the previous one by introducing a new vertex and joining it to one existing vertex, chosen with probability proportional to its degree. We investigate the number $D_t(\ell )$ of vertices of each degree $\ell$ at each time $t$, focussing particularly on the case where $\ell$ is a growing function of $t$. We show that $D_t(\ell )$ is concentrated around its mean, which is approximately $4t/{\ell }^3$, for all $\ell \le (t/\log t{)}^{-1/3}$; this is best possible up to a logarithmic factor.

52 pages; to appear in Electronic Journal of Probability

References in corpus (2)

• Emergence of scaling in random networks
• Differential equation approximations for Markov chains