Subcritical Reed–Frost epidemics on one-dimensional small-world graphs (EPI-6) #
L. Becchetti, A. Clementi, R. Denni, F. Pasquale, L. Trevisan, I. Ziccardi, Percolation and epidemic processes in one-dimensional small-world networks, arXiv:2103.16398 [BCDPTZ22], Theorems 2.4 and 2.5, claim 2.
The Reed–Frost epidemic with transmission probability p on a sampled graph G, started from a
set I₀ of sources, is run G ω I₀ with one coin per edge, ω ~ coins p (EPI-1). Below the
threshold the percolation graph has only components of O(log n) nodes (swg_subcritical,
swg3_subcritical), so, by the deterministic lemmas of EPI-2 (card_recovered_le,
infected_eq_empty_of_ncard_le), the epidemic is over within O(log n) rounds after infecting
O(|I₀| log n) nodes, as observed in the paper (Appendix C):
SWG(n, c/n):swg_reedFrost_subcritical(Theorem 2.4, claim 2: belowp* − ε);3-SWG(n):swg3_reedFrost_subcritical(Theorem 2.5, claim 2, with the threshold1/2of Theorem 2.2; the paper's v3 repeats theSWG(n, c/n)threshold there).
Small components stop the epidemic (deterministic, from EPI-2): if every connected
component of the percolation graph has at most B nodes, then the Reed–Frost epidemic from I₀
is over at some time t ≤ B and infects at most B |I₀| nodes in total.
Subcritical Reed–Frost on SWG(n, c/n) ([BCDPTZ22] Theorem 2.4, claim 2; Appendix C):
for every c > 0 and ε > 0 there are β and C such that, for n ≥ 3, bridge probability
q = c / n, transmission probability p < p* − ε and any set I₀ of sources, with probability
at least 1 - C / n the Reed–Frost epidemic from I₀ is over (no infectious node) at some time
t ≤ β log n, and at most β |I₀| log n nodes are recovered at the end.
Subcritical Reed–Frost on 3-SWG(n) ([BCDPTZ22] Theorem 2.5, claim 2, with the
threshold 1/2 of Theorem 2.2; Appendix E): for every ε > 0 there are β and C such that,
for even n ≥ 4, transmission probability p < 1/2 − ε and any set I₀ of sources, with
probability at least 1 - C / n the Reed–Frost epidemic from I₀ is over at some time
t ≤ β log n, and at most β |I₀| log n nodes are recovered at the end.