SPEEDING UP NON-MARKOVIAN FIRST-PASSAGE PERCOLATION WITH A FEW EXTRA EDGES
- 1 September 2018
- journal article
- research article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 50 (3) , 858-886
Abstract
One model of real-life spreading processes is that of first-passage percolation (also called the SI model) on random graphs. Social interactions often follow bursty patterns, which are usually modelled with independent and identically distributed heavy-tailed passage times on edges. On the other hand, random graphs are often locally tree-like, and spreading on trees with leaves might be very slow due to bottleneck edges with huge passage times. Here we consider the SI model with passage times following a power-law distribution P(xi > t) similar to t(-alpha) with infinite mean. For any finite connected graph G with a root s, we find the largest number of vertices kappa(G , s) that are infected in finite expected time, and prove that for every k <= kappa (G, s), the expected time to infect k vertices is at most O(k(1/alpha)). Then we show that adding a single edge from s to a random vertex in a random tree T typically increases kappa(T , s) from a bounded variable to a fraction of the size of T, thus severely accelerating the process. We examine this acceleration effect on some natural models of random graphs: critical Galton-Watson trees conditioned to be large, uniform spanning trees of the complete graph, and on the largest cluster of near-critical Erdos-Renyi graphs. In particular, at the upper end of the critical window, the process is already much faster than exactly at criticality.Keywords
All Related Versions
This publication has 46 references indexed in Scilit:
- Predicting and controlling infectious disease epidemics using temporal networksF1000Prime Reports, 2013
- A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spacesElectronic Journal of Probability, 2013
- Simply generated trees, conditioned Galton–Watson trees, random allocations and condensationProbability Surveys, 2012
- Anatomy of a young giant component in the random graphRandom Structures & Algorithms, 2010
- Percolation, First-Passage Percolation and Covering Times for Richardson's Model on the $n$-CubeThe Annals of Applied Probability, 1993
- The Continuum Random Tree IIIThe Annals of Probability, 1993
- The Continuum random tree II: an overview1991
- A time-dependent version of P lya's urnJournal of Theoretical Probability, 1990
- Percolation Theory and First-Passage PercolationThe Annals of Probability, 1987
- On the Altitude of Nodes in Random TreesCanadian Journal of Mathematics, 1978