Abstract. We consider the problem of reconstructing an epidemic over time, or, more general, reconstructing the propagation of an activity in a network. Our input consists of a temporal network, which contains information about when two nodes interacted, and a small sample of nodes that have been reported as infected. The goal is to recover the flow of the spread, including discovering the starting nodes, and identifying other likely-infected nodes that were not reported. This has multiple applications, from public health to social media and viral marketing purposes.
Previous work explicitly factor-in many unrealistic assumptions: (a) the underlying network does not change or that we see all interactions; (b) that we have access to perfect noise-free data; or (c) that we know the exact propagation model. In contrast, we avoid these simplifications, and take into account the temporal network, require only a small sample of reported infections, and do not make any restrictive assumptions on the propagation model.
We develop CulT, a scalable and effective algorithm to reconstruct epidemics that is also suited for an online setting. It works by formulating the problem as that of a temporal Steiner-tree computation, for which we design a fast algorithm leveraging the specific structure of our problem. We demonstrate the efficacy of CulT through extensive experiments on diverse datasets.
Reconstructing an Epidemic over Time. In: Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp 1835-1844, ACM, 2016. (18.1% acceptance rate) |
|
Efficiently Spotting the Starting Points of an Epidemic in a Large Graph. Knowledge and Information Systems vol.38(1), pp 35-59, Springer, 2014. (IF 2.225) |
|
Spotting Culprits in Epidemics: How many and Which ones?. In: Proceedings of the IEEE International Conference on Data Mining (ICDM), pp 11-20, IEEE, 2012. (full paper, 10.7% acceptance rate; overall 20%) |