TY - JOUR

T1 - Speeding up non-Markovian First Passage Percolation with a few extra edges

AU - Medvedev, Alexey

AU - Pete, Gábor

N1 - Funding Information:
We are indebted to János Kertész for drawing our attention to the phenomenon studied in the paper, for many useful discussions, and constant support; to Júlia Komjáthy for suggesting that we look at near-critical Erdos-Rényi graphs; to Balázs Ráth for many comments and discussions regarding the manuscript; and to Louigi Addario-Berry for some references. Most of the work was done while A. M. was a doctoral student at the Central European University, Budapest. A. M. also gratefully acknowledges financial support from the European Research Council grant 'Limits of discrete structures'(grant number 617747),ARC(FederationWallonia- Brussels) project 'Big Data Models', and from the Russian Foundation of Basic Research (grant number 16-01-00499). G. P. acknowledges support from the Hungarian National Research, Development, and Innovation Office, NKFIH (grant number K109684), and from an MTA Rényi Institute 'Lendület' Research Group.
Publisher Copyright:
Copyright © Applied Probability Trust 2018.

PY - 2018/9/1

Y1 - 2018/9/1

N2 - 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.

AB - 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.

KW - temporal networks

KW - near-critical random graphs

KW - Galton-Watson tree

KW - Erdős-Rényi graph

KW - Pólya urn process

KW - First Passage Percolation

KW - SI model

KW - bursty time series

KW - non-Markovian processes

KW - non-Markovian process

KW - Erdos-Rényi graph

KW - spreading phenomena

KW - Temporal network

KW - first-passage percolation

KW - near-critical random graph

UR - http://www.scopus.com/inward/record.url?scp=85056667555&partnerID=8YFLogxK

U2 - 10.1017/apr.2018.39

DO - 10.1017/apr.2018.39

M3 - Article

SN - 1475-6064

VL - 50

SP - 858

EP - 886

JO - Advances in Applied Probability

JF - Advances in Applied Probability

IS - 3

ER -