Reconstructing a cascade from temporal observations

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal

Other link related to publication
Date
2018
Major/Subject
Mcode
Degree programme
Language
en
Pages
666-674
Series
Proceedings of the 2018 SIAM International Conference on Data Mining
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 (SIAM) , 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