论文标题
增长的优先附着图中的距离演变
Distance evolutions in growing preferential attachment graphs
论文作者
论文摘要
我们研究了动态生长的随机图模型中两个固定顶点之间的图形距离和加权距离的演变。更准确地说，我们考虑使用Power-Law指数$τ\ in（2,3）$，在图形具有$ t $ Vertices时随机统一的两个顶点$ u_t $均匀地考虑优先固定模型，并研究了这两个固定顶点的图形距离的演变。这在$ t'\ geq t $中得出一个离散的随机过程，称为距离演变。我们表明，该功能周围有一个紧条带$ 4 \ frac {\ log \ log \ log \ log（t） - \ log（\ log（t'/t）\ vee1）} {| \ log log（τ-2）|} \ vee 2 $，距离进化永远不会以$ t $ t $ iffinity的高可能性离开。我们将结果扩展到加权距离，每个边缘都配备了I.I.D。非负随机变量$ L $的副本。
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 $τ\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'\geq t$, called the distance evolution. We show that there is a tight strip around the function $4\frac{\log\log(t)-\log(\log(t'/t)\vee1)}{|\log(τ-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$.
