Reconstructing an Epidemic over Time
Polina Rozenshtein, Aalto University; Aristides Gionis*, Aalto University; B. Aditya Prakash, Virginia Tech; Jilles Vreeken, Max-Planck Institute for Informatics and Saarland University
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 ﬂow 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 simpliﬁcations: we take into account the temporal net-work, 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 eﬀective 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 speciﬁc problem structure. We demonstrate the eﬃcacy of the proposed approach through extensive experiments on diverse datasets.
Filed under: Graph Mining and Social Networks