We study a simple model of epidemics where an infected node transmits theinfection to its neighbors independently with probability $p$. This is alsoknown as the independent cascade or Susceptible-Infected-Recovered (SIR) model . The size of an outbreak in this model is closelyrelated to that of the giant connected component in “edge percolation”, whereeach edge of the graph is kept independently . We also presentcorollaries of the theorem for the preferential attachment model, and studygeneralizations with household (or motif) structure . We answer the question in the affirmative for large-set expanders with local weak limits(also known as Benjamini-Schramm limits) In particular, we show that there isan algorithm which gives a $(1-\epsilon)$ approximation of the probability and the final size of the outbreak by accessing a constant-size neighborhood of nodes chosen uniformly at random at random . The latter was only knownfor the configuration model, the latter was previously known for the configurationmodel, Theory of the Preferential attachment model. We also show there is an algorithm which provides an algorithm that gives a \$1-

Author(s) : Yeganeh Alimohammadi, Christian Borgs, Amin Saberi

Links : PDF - Abstract

Code :

Keywords : model - size - algorithm - outbreak - edge -