Distance evolutions in growing preferential attachment graphs
Joost Jorritsma (Eindhoven University of Technology)
Júlia Komjáthy (TU Delft - Applied Probability)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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 powerlaw exponent τ ϵ (2, 3), sample two vertices ut , vt 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 ' ≥ t , called the distance evolution. We show that there is a tight strip around the function 4 log log(t)-log(log(t'/t)ν1) | log(τ-2)| ν 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 nonnegative random variable L.