Premium
Diameter in ultra‐small scale‐free random graphs
Author(s) -
Caravenna Francesco,
Garavaglia Alessandro,
van der Hofstad Remco
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20798
Subject(s) - combinatorics , mathematics , random graph , degree (music) , graph , preferential attachment , scale (ratio) , constant (computer programming) , order (exchange) , discrete mathematics , computer science , physics , complex network , quantum mechanics , finance , economics , acoustics , programming language
It is well known that many random graphs with infinite variance degrees are ultra‐small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k −( τ − 1) with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to2 log log n | log ( τ − 2 ) |and4 log log n | log ( τ − 2 ) | , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order log log n precisely when the minimal forward degree d fwd of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus 2 / log d fwd . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.