### 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(ξ>t)t
^{-α} with infinite mean. For any finite connected graph G with a root s, we find the largest number of vertices κ(G,s) that are infected in finite expected time, and prove that for every k≤κ(G,s), the expected time to infect k vertices is at most O(k
^{1/α}). Then we show that adding a single edge from s to a random vertex in a random tree typically increases κ(T,s) from a bounded variable to a fraction of the size of , 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-Rényi graphs. In particular, at the upper end of the critical window, the process is already much faster than exactly at criticality.

Original language | English |
---|---|

Pages (from-to) | 858-886 |

Number of pages | 29 |

Journal | Advances in Applied Probability |

Volume | 50 |

Issue number | 3 |

Early online date | 31 Aug 2017 |

DOIs | |

Publication status | Published - 1 Sep 2018 |

### Keywords

- temporal networks
- near-critical random graphs
- Galton-Watson tree
- Erdős-Rényi graph
- Pólya urn process
- First Passage Percolation
- SI model
- bursty time series
- non-Markovian processes
- non-Markovian process
- Erdos-Rényi graph
- spreading phenomena
- Temporal network
- first-passage percolation
- near-critical random graph

## Fingerprint Dive into the research topics of 'Speeding up non-Markovian First Passage Percolation with a few extra edges'. Together they form a unique fingerprint.

## Cite this

*Advances in Applied Probability*,

*50*(3), 858-886. https://doi.org/10.1017/apr.2018.39