Learning from Contagion (Without Timestamps)

We introduce and study new models for learn-ing from contagion processes in a network. A learning algorithm is allowed to either choose or passively observe an initial set of seed in-fections. This seed set then induces a final set of infections resulting from the underlying stochastic contagion dynamics. Our models dif-fer from prior work in that detailed vertex-by-vertex timestamps for the spread of the contagion are not observed. The goal of learning is to infer the unknown network structure. Our main the-oretical results are efficient and provably correct algorithms for exactly learning trees. We provide empirical evidence that our algorithm performs well more generally on realistic sparse graphs. 1