Vertices of high degree in the preferential attachment tree

DOI10.1214/EJP.V17-1803zbMATH Open1244.05197arXiv1012.5550MaRDI QIDQ428619FDOQ428619

Malwina Luczak, Graham Brightwell

Publication date: 22 June 2012

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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/el{l}^3$, for all $ellle(t/logt{)}^{-1/3}$; this is best possible up to a logarithmic factor.

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

Recommendations

• The power of choice over preferential attachment
• High degree vertices and eigenvalues in the preferential attachment graph
• High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
• The power of choice combined with preferential attachement
• A preferential attachment model with random initial degrees

zbMATH Keywords

martingalesrandom graphspreferential attachmentconcentration of measureweb graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Martingales with discrete parameter (60G42) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cited In (8)

• Weights and degrees in a random graph model based on 3-interactions
• High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
• Extinction time for the weaker of two competing SIS epidemics
• The supermarket model with bounded queue lengths in equilibrium
• Root finding algorithms and persistence of Jordan centrality in growing random trees
• Fluctuations in a general preferential attachment model via Stein's method
• Profile of random exponential recursive trees
• Concentration in the generalized Chinese restaurant process

This page was built for publication: Vertices of high degree in the preferential attachment tree

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