Learning from Contagion (Without Timestamps)


Kareem Amin, Hoda Heidari, Michael Kearns ;
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1845-1853, 2014.


We introduce and study new models for learning from contagion processes in a network. A learning algorithm is allowed to either choose or passively observe an initial set of seed infections. This seed set then induces a final set of infections resulting from the underlying stochastic contagion dynamics. Our models differ 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 theoretical 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.

Related Material