Distance evolutions in growing preferential attachment graphs

Abstract

We study the evolution of the graph distance and weighted distance between two fixed vertices in dynamically growing random graph models. More precisely, we consider preferential attachment models with power-law exponent $\tau \in (2,3)$, sample two vertices $u_t,v_t$ uniformly at random when the graph has $t$ vertices, and study the evolution of the graph distance between these two fixed vertices as the surrounding graph grows. This yields a discrete-time stochastic process in $t^{\prime }\ge t$, called the distance evolution. We show that there is a tight strip around the function $4\frac{\log \log (t)-\log (\log (t^{\prime }/t)\vee 1)}{|\log (\tau -2)|}\vee 2$ that the distance evolution never leaves with high probability as $t$ tends to infinity. We extend our results to weighted distances, where every edge is equipped with an i.i.d. copy of a non-negative random variable $L$.

arXiv comment42 pages, 4 figures. Revised version with corrected typos and more elaborate proofs. Includes correction of an error in Theorem 2.5 that required a shift of indices in the summation

References in corpus (15)

• Bose-Einstein condensation in complex networks
• Diameters in preferential attachment models
• Spatial preferential attachment networks: Power laws and clustering coefficients
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Random networks with sublinear preferential attachment: The giant component
• First passage percolation on random graphs with finite mean degrees
• The age-dependent random connection model
• Robust analysis of preferential attachment models with fitness
• Growing networks with preferential addition and deletion of edges
• Percolation phase transition in weight-dependent random connection models
• Weighted distances in scale-free configuration models
• Weighted distances in scale-free preferential attachment models
• Preferential attachment without vertex growth: emergence of the giant component
• Extensive Condensation in a model of Preferential Attachment with Fitnesses
• Diameter in ultra-small scale-free random graphs: Extended version

Cited by in corpus (1)

• Graph distances in scale-free percolation: the logarithmic case