Diameter in ultra-small scale-free random graphs

DOI10.1002/RSA.20798MaRDI QIDQ5381052zbMATH OpenOpenAlexWikidataFDO

Authors Francesco Caravenna, Alessandro Garavaglia, Remco van der Hofstad

Publication date 7 June 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1605.02714

zbMATH Keywords

configuration modeldiameterpreferential attachment modelrandom graphsscale free graphultra-small graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80)

Abstract: It is well known that many random graphs with infinite variance degrees are ultrasmall. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least $k$ is approximately $k^{-(au-1)}$ with $auin(2,3)$, typical distances between pairs of vertices in a graph of size $n$ are asymptotic to $frac2loglogn|log(au-2)|$ and $frac4loglogn|log(au-2)|$, respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order $loglogn$ precisely when the minimal forward degree $d$ of vertices is at least $2$. We identify the exact constant, which equals that of the typical distances plus $2/logd$. Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.

Recommendations

• The diameter of a scale-free random graph
• When is a scale-free graph ultra-small?
• Typical distances in ultrasmall random networks
• Diameters in preferential attachment models
• Diameter of P.A. random graphs with edge-step functions

Cites work

• A Phase Transition for the Diameter of the Configuration Model
• Diameter in ultra-small scale-free random graphs
• Diameters in preferential attachment models
• Distances in random graphs with finite mean and infinite variance degrees
• Distances in random graphs with finite variance degrees
• Paths in graphs
• Random graphs and complex networks. Volume 1
• The average distances in random graphs with given expected degrees
• The degree sequence of a scale-free random graph process
• The diameter of a scale-free random graph
• The Diameter of Random Graphs
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• The probability that a random multigraph is simple
• Typical distances in ultrasmall random networks
• Universality for the distance in finite variance random graphs
• When is a scale-free graph ultra-small?

Cited in

(13)

• When is a scale-free graph ultra-small?
• The diameter of a scale-free random graph
• Linking the mixing times of random walks on static and dynamic random graphs
• Distance evolutions in growing preferential attachment graphs
• Local weak convergence for PageRank
• Typical distances in ultrasmall random networks
• An estimate of the probability of localisation of the diameter of a random scale-free graph
• A Phase Transition for the Diameter of the Configuration Model
• Diameter of P.A. random graphs with edge-step functions
• Diameter in ultra-small scale-free random graphs
• MATRIX-MFO tandem workshop: Stochastic reinforcement processes and graphs. Abstracts from the MATRIX-MFO tandem workshop held March 5--10, 2023
• Open problems in stochastic reinforcement models
• Asymptotic diameter of preferential attachment model

This page was built for publication: Diameter in ultra-small scale-free random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5381052)