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.
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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 2018 SIAM International Conference on Data Mining |
Publisher | Society for Industrial and Applied Mathematics |
Pages | 666-674 |
ISBN (Electronic) | 978-1-61197-532-1 |
DOIs | |
Publication status | Published - 2018 |
MoE publication type | A4 Conference publication |
Event | SIAM International Conference on Data Mining - San Diego, United States Duration: 3 May 2018 → 5 May 2018 |
Conference
Conference | SIAM International Conference on Data Mining |
---|---|
Abbreviated title | SDM |
Country/Territory | United States |
City | San Diego |
Period | 03/05/2018 → 05/05/2018 |