Weighted distances in scale-free configuration models

Erwin Adriaans, Júlia Komjáthy

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
48 Downloads (Pure)

Abstract

In this paper we study first-passage percolation in the configuration model with empirical degree distribution that follows a power-law with exponent τ∈ (2 , 3). We assign independent and identically distributed (i.i.d.) weights to the edges of the graph. We investigate the weighted distance (the length of the shortest weighted path) between two uniformly chosen vertices, called typical distances. When the underlying age-dependent branching process approximating the local neighborhoods of vertices is found to produce infinitely many individuals in finite time—called explosive branching process—Baroni, Hofstad and the second author showed in Baroni et al. (J Appl Probab 54(1):146–164, 2017) that typical distances converge in distribution to a bounded random variable. The order of magnitude of typical distances remained open for the τ∈ (2 , 3) case when the underlying branching process is not explosive. We close this gap by determining the first order of magnitude of typical distances in this regime for arbitrary, not necessary continuous edge-weight distributions that produce a non-explosive age-dependent branching process with infinite mean power-law offspring distributions. This sequence tends to infinity with the amount of vertices, and, by choosing an appropriate weight distribution, can be tuned to be any growing function that is O(log log n) , where n is the number of vertices in the graph. We show that the result remains valid for the the erased configuration model as well, where we delete loops and any second and further edges between two vertices.

Original languageEnglish
Pages (from-to)1082-1109
Number of pages28
JournalJournal of Statistical Physics
Volume173
Issue number3-4
DOIs
Publication statusPublished - 1 Nov 2018

Keywords

  • Configuration model
  • First passage percolation
  • Power-law degrees
  • Random networks
  • Scale-free
  • Typical distances

Fingerprint

Dive into the research topics of 'Weighted distances in scale-free configuration models'. Together they form a unique fingerprint.

Cite this