DISTANCE EVOLUTIONS IN GROWING PREFERENTIAL ATTACHMENT GRAPHS

• 成果类型: Article
• 署名作者: Jorritsma, Joost; Komjathy, Julia
• 署名单位: Eindhoven University of Technology; Delft University of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1789
• 发表日期: 2022
• 页码: 4356-4397
• 关键词: phase-transition; random networks; percolation; condensation; diameter

摘要

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 e (2, 3), sample two vertices ut, vt uniformly at random when the graph has t vertices and study the evolution of the graph dis-tance between these two fixed vertices as the surrounding graph grows. This yields a discrete-time stochastic process in t' > t, called the dis-tance evolution. We show that there is a tight strip around the function 4 log log(t)-log(log(t'/t)v1) | log(tau-2)| v 2 that the distance evolution never leaves with high probability as t tends to infinity. We extend our results to weighted dis-tances, where every edge is equipped with an i.i.d. copy of a nonnegative random variable L.