Speeding up non-Markovian First Passage Percolation with a few extra edges
Authors:
Preprint
Abstract
One model of real-life spreading processes is First Passage Percolation (also called SI model) on random graphs. Social interactions often follow bursty patterns, which are usually modelled with i.i.d.~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, because of bottleneck edges with huge passage times. Here we consider the SI model with passage times following a power law distribution $\mathbb{P}(\xi>t)\sim 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 \leq \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 $\mathcal{T}$ typically increases $\kappa(\mathcal{T},s)$ from a bounded variable to a fraction of the size of $\mathcal{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 Erd\H{o}s-R\'enyi 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 24 references indexed in Scilit:
- 50 Years of First-Passage Percolation2017
- Epidemic processes in complex networksReviews of Modern Physics, 2015
- The mixing time of the giant component of a random graphRandom Structures & Algorithms, 2014
- Analytically Solvable Model of Spreading Dynamics with Non-Poissonian ProcessesPhysical Review X, 2014
- Modelling dynamical processes in complex socio-technical systemsNature Physics, 2011
- Small but slow world: How network topology and burstiness slow down spreadingPhysical Review E, 2011
- The continuum limit of critical random graphsProbability Theory and Related Fields, 2010
- Anatomy of a young giant component in the random graphRandom Structures & Algorithms, 2010
- The birth of the giant componentRandom Structures & Algorithms, 1993
- A time-dependent version of P lya's urnJournal of Theoretical Probability, 1990