Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T07:14:43.197Z Has data issue: false hasContentIssue false

Nonuniversality of weighted random graphs with infinite variance degree

Published online by Cambridge University Press:  04 April 2017

Enrico Baroni*
Affiliation:
Eindhoven University of Technology
Remco van der Hofstad*
Affiliation:
Eindhoven University of Technology
Júlia Komjáthy*
Affiliation:
Eindhoven University of Technology
*
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB, Eindhoven,The Netherlands.
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB, Eindhoven,The Netherlands.
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB, Eindhoven,The Netherlands.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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).

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2017