Diameter of P.A. random graphs with edge‐step functions. Issue 3 (26th May 2020) - Alves, Caio; Ribeiro, Rodrigo; Sanchis, Rémy
Abstract : In this work we prove general bounds for the diameter of random graphs generated by a preferential attachment model whose parameter is a function f :N→[0, 1] that drives the asymptotic proportion between the numbers of vertices and edges. These results are sharp when f is a regularly varying function at infinity with strictly negative index of regular variation − γ . For this particular class, we prove a characterization for the diameter that depends only on − γ . More specifically, we prove that the diameter of such graphs is of order 1/ γ with high probability, although its vertex set order goes to infinity polynomially. Sharp results for the diameter for a wide class of slowly varying functions are also obtained.