Reconstructing an epidemic over time
No Thumbnail Available
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2016-08-13
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
10
1835-1844
1835-1844
Series
KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Volume 13-17-August-2016
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.Description
| openaire: EC/H2020/654024/EU//SoBigData
Keywords
Other note
Citation
Rozenshtein, P, Gionis, A, Prakash, B A & Vreeken, J 2016, Reconstructing an epidemic over time . in KDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . vol. 13-17-August-2016, ACM, pp. 1835-1844, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, California, United States, 13/08/2016 . https://doi.org/10.1145/2939672.2939865