Reconstructing an epidemic over time

Polina Rozenshtein, Aristides Gionis, B. Aditya Prakash, Jilles Vreeken

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

22 Citations (Scopus)
119 Downloads (Pure)


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 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 are not reported. The problem we consider has multiple applications, from public health to social media and viral marketing purposes. Previous work explicitly factor-in many unrealistic assumptions: it is assumed that (a) the underlying network does not change; (b) we have access to perfect noise-free data; or (c) we know the exact propagation model. In contrast, we avoid these simplifications: we take into account the temporal network, we require only a small sample of reported infections, and we do not make any restrictive assumptions about the propagation model. We develop CulT, a scalable and effective algorithm to reconstruct epidemics that is also suited for online settings. CulT works by formulating the problem as that of a temporal Steiner-tree computation, for which we design a fast algorithm leveraging the specific problem structure. We demonstrate the effcacy of the proposed approach through extensive experiments on diverse datasets.

Original languageEnglish
Title of host publicationKDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Number of pages10
ISBN (Electronic)9781450342322
Publication statusPublished - 13 Aug 2016
MoE publication typeA4 Article in a conference publication
EventACM SIGKDD International Conference on Knowledge Discovery and Data Mining - San Francisco, United States
Duration: 13 Aug 201617 Aug 2016
Conference number: 22


ConferenceACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Abbreviated titleKDD
CountryUnited States
CitySan Francisco

Fingerprint Dive into the research topics of 'Reconstructing an epidemic over time'. Together they form a unique fingerprint.

Cite this