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)

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 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
PublisherACM
Pages1835-1844
Number of pages10
Volume13-17-August-2016
ISBN (Electronic)9781450342322
DOIs
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

Conference

ConferenceACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Abbreviated titleKDD
CountryUnited States
CitySan Francisco
Period13/08/201617/08/2016

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

Cite this