Speeding up non-Markovian first-passage percolation with a few extra edges. (16th November 2018)

• Record Type: Journal Article
• Authors: Medvedev, Alexey; Pete, Gábor
• Is Part Of: Advances in applied probability. Volume 50:Number 3(2018)
• Page Start: 858
• Page End: 886
• Publication Date: 2018-11-16
• Subjects: Temporal network, -- near-critical random graph, -- Galton‒Watson tree, -- Erdős‒Rényi graph, -- Pólya urn process, -- spreading phenomena, -- SI model, -- first-passage percolation, -- bursty time series, -- non-Markovian process; Primary 60K35, -- 60K37, -- 05C80, -- Secondary 82C99, -- 90B18; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2018.39
• Languages: English
• ISSNs: 0001-8678

Abstract

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 ℙ(ξ> 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 κ(𝒯, 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 Erdős‒Rényi graphs. In particular, at the upper end of the critical window, the process is already much faster than exactly at criticality.