SPEEDING UP NON-MARKOVIAN FIRST-PASSAGE PERCOLATION WITH A FEW EXTRA EDGES

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.