Local Algorithms to Predict Epidemics on Networks

Local Algorithms to Predict Epidemics on Networks (via Zoom)
Abstract: We study a simple model of epidemics where an infected node transmits the infection to its neighbors independently with probability p. Our study aims to estimate the likelihood and size of future outbreaks. Prior literature studied similar questions based on the underlying network model, for example, the configuration model and preferential attachment. Although these models capture super-spreaders' role in the spread of infection, they only consider tree-like graphs, i.e., graphs with no cycles. Here, we ask a different question: what information do we need 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.
Bio: Yeganeh is a fifth-year Ph.D. student in Operations Research at Stanford University, where she is advised by Amin Saberi. Currently, she is spending a semester at the Simons Institute for the Theory of Computing at UC Berkeley as a research fellow. Her research interests are algorithm design and operations research with an emphasis on applications. In particular, she studies the theoretical grounds of network models of practical importance, mainly focusing on 1) studying epidemics on networks, 2) designing efficient sampling algorithms from large networks, and 3) network optimization.