Back to Search
Start Over
Diameter in ultra‐small scale‐free random graphs
- Source :
- Random Structures and Algorithms, 54(3), 444-498. Wiley, Random Structures & Algorithms
- Publication Year :
- 2018
- Publisher :
- Wiley, 2018.
-
Abstract
- 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 to 2 log log n | log ( τ - 2 ) | and 4 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.
- Subjects :
- Random graph
scale free
Applied Mathematics
General Mathematics
0102 computer and information sciences
Preferential attachment
preferential attachment model
01 natural sciences
Computer Graphics and Computer-Aided Design
configuration model
Graph
Combinatorics
ultra-small
010201 computation theory & mathematics
Log-log plot
diameter
Research Articles
random graphs
Software
random graph
Research Article
ultra‐small
Mathematics
Subjects
Details
- ISSN :
- 10982418 and 10429832
- Volume :
- 54
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi.dedup.....bb52ef223f6673e84e0a6975a125c4fd