Vertices of high degree in the preferential attachment tree

DOI10.1214/EJP.V17-1803MaRDI QIDQ428619zbMATH OpenFDO

Authors Graham Brightwell, Malwina Luczak

Publication date 22 June 2012

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

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

zbMATH Keywords

concentration of measuremartingalespreferential attachmentrandom graphsweb 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)

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.

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

Cited in

(20)

• The supermarket model with bounded queue lengths in equilibrium
• On a preferential attachment and generalized Pólya's urn model
• Concentration in the generalized Chinese restaurant process
• Root finding algorithms and persistence of Jordan centrality in growing random trees
• Extinction time for the weaker of two competing SIS epidemics
• Preferential attachment without vertex growth: emergence of the giant component
• Consistent estimation in general sublinear preferential attachment trees
• Profile of random exponential recursive trees
• Stratification in the preferential attachment network
• The power of choice over preferential attachment
• Weights and degrees in a random graph model based on 3-interactions
• The power of choice combined with preferential attachement
• On terminal nodes and the degree profile of preferential dynamic attachment circuits
• Fluctuations in a general preferential attachment model via Stein's method
• High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
• Existence of a persistent hub in the convex preferential attachment model
• High degree vertices and eigenvalues in the preferential attachment graph
• Eve, Adam and the preferential attachment tree
• The degree sequence of the preferential attachment model
• Is this correct? Let's check!

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)