Reconstructing a cascade from temporal observations
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)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2018
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Proceedings of the 2018 SIAM International Conference on Data Mining, pp. 666-674
Abstract
Given a subset of active nodes in a network can we reconstruct the cascade that has generated these observations? This is a problem that has been studied in the literature, but here we focus in the case that temporal information is available about the active nodes. In particular, we assume that in addition to the subset of active nodes we also know their activation time. We formulate this cascade-reconstruction problem as a variant of a Steiner-tree problem: we ask to find a tree that spans all reported active nodes while satisfying temporal-consistency constraints. For the proposed problem we present three approximation algorithms. The best algorithm in terms of quality achieves a O(√k)-approximation guarantee, where k is the number of active nodes, while the most efficient algorithm has linearithmic running time, making it scalable to very large graphs. We evaluate our algorithms on real-world networks with both simulated and real cascades. Our results indicate that utilizing the available temporal information allows for more accurate cascade reconstruction. Furthermore, our objective leads to finding the “backbone” of the cascade and it gives solutions of very high precision.Description
| openaire: EC/H2020/654024/EU//SoBigData
Keywords
Other note
Citation
Xiao, H, Rozenshtein, P, Tatti, N & Gionis, A 2018, Reconstructing a cascade from temporal observations . in Proceedings of the 2018 SIAM International Conference on Data Mining . Society for Industrial and Applied Mathematics, pp. 666-674, SIAM International Conference on Data Mining, San Diego, California, United States, 03/05/2018 . https://doi.org/10.1137/1.9781611975321.75