Diameter in ultra-small scale-free random graphs

Francesco Caravenna, Alessandro Garavaglia, Remco van der Hofstad (Corresponding author)

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    43 Downloads (Pure)

    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.

    Original languageEnglish
    Pages (from-to)444-498
    Number of pages55
    JournalRandom Structures and Algorithms
    Volume54
    Issue number3
    DOIs
    Publication statusPublished - May 2019

    Keywords

    • configuration model
    • diameter
    • preferential attachment model
    • random graphs
    • scale free
    • ultra-small

    Fingerprint

    Dive into the research topics of 'Diameter in ultra-small scale-free random graphs'. Together they form a unique fingerprint.

    Cite this