Vertices of high degree in the preferential attachment tree

2010/12/26 by Brightwell, Graham, Luczak, Malwina J.
#05C80 #60G42 #60J10 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1012.5550

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(ℓ) of vertices of each degree ℓ at each time t, focussing particularly on the case where ℓ is a growing function of t. We show that D_t(ℓ) is concentrated around its mean, which is approximately 4t/ℓ³, for all ℓ ≤ (t/log t)^-1/3; this is best possible up to a logarithmic factor.

Related

• The number of descendants in a preferential attachment graph
• Influence of the seed in affine preferential attachment trees
• High degree vertices in the Power of Choice model combined with Preferential Attachment
• A Multi-type Preferential Attachment Tree
• Preferential Attachment Graphs with Planted Communities