Yeganeh Alimohammadi, Stanford University

Abstract

We study a simple model of epidemics where an infected node transmits the infection to its neighbors independently with probability p. The size of an outbreak in this model is closely related to that of the giant connected component in 'edge percolation', studied for a large class of networks including configuration model and preferential attachment. Even though these models capture the role of super-spreaders in the spread of an epidemic, they only consider graphs that are locally tree-like i.e. have a few short cycles. Some generalizations of the configuration model were suggested to capture local communities, known as household models, or hierarchical configuration models.

Here, we ask a different question: what information is needed for general networks to predict the size of an outbreak? Is it possible to make predictions by accessing the distribution of small subgraphs (or motifs)? We answer the question in the affirmative for large-set expanders with Benjamini-Schramm limits. In particular, we show that there is an algorithm that gives a (1−ϵ) approximation of the probability and the final size of an outbreak by accessing a constant-size neighborhood of a constant number of nodes chosen uniformly at random. We also present corollaries of the theorem for the preferential attachment model and study generalizations with household (or motif) structure. The latter was only known for the configuration model.

This is joint work with Christian Borgs and Amin Saberi.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar