Nonuniversality of weighted random graphs with infinite variance degree

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

Abstract

We prove nonuniversality results for first-passage percolation on the configuration model with independent and identically distributed (i.i.d.) degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviours are possible. When the weights are almost surely larger than a constant, the weight and number of edges in the graph grow proportionally to log log n, as for the graph distances. On the other hand, when the continuous-time branching process describing the first-passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the continuous-time processes started from the two sources. This nonuniversality is in sharp contrast to the setting where the degree sequence has a finite variance, Bhamidi et al. (2012).

Original languageEnglish
Pages (from-to)146-164
Number of pages19
JournalJournal of Applied Probability
Volume54
Issue number1
DOIs
Publication statusPublished - 1 Mar 2017

Keywords

  • Configuration model
  • first-passage percolation
  • power-law degree
  • universality

Fingerprint

Dive into the research topics of 'Nonuniversality of weighted random graphs with infinite variance degree'. Together they form a unique fingerprint.

Cite this