Reconstructing an epidemic over time

No Thumbnail Available

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa

Date

2016-08-13

Major/Subject

Mcode

Degree programme

Language

en

Pages

10
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