Reconstructing a cascade from temporal observations

Han Xiao, Polina Rozenshtein, Nikolaj Tatti, Aristides Gionis

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

13 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings of the 2018 SIAM International Conference on Data Mining
PublisherSociety for Industrial and Applied Mathematics
Pages666-674
ISBN (Electronic)978-1-61197-532-1
DOIs
Publication statusPublished - 2018
MoE publication typeA4 Conference publication
EventSIAM International Conference on Data Mining - San Diego, United States
Duration: 3 May 20185 May 2018

Conference

ConferenceSIAM International Conference on Data Mining
Abbreviated titleSDM
Country/TerritoryUnited States
CitySan Diego
Period03/05/201805/05/2018

Fingerprint

Dive into the research topics of 'Reconstructing a cascade from temporal observations'. Together they form a unique fingerprint.

Cite this