Algorithms Using Local Graph Features to Predict Epidemics
8Yeganeh Alimohammadi (Stanford)
https://simons.berkeley.edu/talks/algorithms-using-local-graph-features-predict-epidemics
Meet the Fellows Welcome Event Fall 2022
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 tree-like graphs, i.e., graphs with a few short cycles locally. 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. Based on a joint work with Christian Borgs and Amin Saberi. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.136