Diameter of P.A. random graphs with edge‐step functions. Issue 3 (26th May 2020)

• Record Type: Journal Article
• Authors: Alves, Caio; Ribeiro, Rodrigo; Sanchis, Rémy
• Is Part Of: Random structures & algorithms. Volume 57:Issue 3(2020)
• Page Start: 612
• Page End: 636
• Publication Date: 2020-05-26
• Subjects: cliques -- complex networks -- concentration bounds -- diameter -- preferential attachment -- scale‐free -- small‐world; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20929
• Languages: English
• ISSNs: 1042-9832

Abstract

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.