Distance evolutions in growing preferential attachment graphs.

Abstract: In this talk we will study the evolution of the graph distance between two fixed vertices in dynamically growing random graph models. More precisely, we consider preferential attachment models with parameters such that the asymptotic degree distribution has infinite second moment. First, we grow the graph until it contains $t$ vertices, then we sample $u_t, v_t$ uniformly at random from the largest component and study the evolution of the graph distance as the surrounding graph grows. This yields a stochastic process in $t’\ge t$ that we call the distance evolution. We identify a function $f(t,t’)$ such that there exists a tight strip around this function that the distance evolution never leaves with high probability as $t$ tends to infinity.

If time permits, we will consider the generalization of graph distance to weighted distance, in which every edge is equipped with an i.i.d. copy of a non-negative random variable $L$. For any such edge-weight distribution $L$, we obtain explicit asymptotic results: either the typical weighted distance at time $t$ tends to an almost surely finite random variable as $t$ tends to infinity, or the typical weighted distance at time $t$ diverges, in which case we identify a function $f_L(t,t’)$ that describes the weighted-distance evolution for $t’>t$.

Posted on Dec 13, 2022 in Seminario de Probabilidades de Chile, Seminars