Robust Cascade Reconstruction by Steiner Tree Sampling
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review
observed to be infected, and avoid the nodes that have been observed to be uninfected. The sampling problem corresponds to sampling directed Steiner trees with a given set of terminals, which is a problem of independent interest and has received limited attention in the literature. For the latter problem we propose two novel algorithms with provable guarantees on the sampling distribution of the returned Steiner trees.
The resulting method improves over state-of-the-art approaches that often make explicit assumptions about the infection-propagation model, or require additional parameters. Our method provides a more robust approach to the cascadereconstruction problem, which makes weaker assumptions about the infection model, requires fewer additional parameters, and can be used to estimate node infection probabilities. We experimentally validate the proposed reconstruction algorithm on realworld graphs with both synthetic and real cascades. We show that our method outperforms all other baseline strategies in most cases.
|Title of host publication||2018 IEEE International Conference on Data Mining (ICDM)|
|Publication status||Published - Nov 2018|
|MoE publication type||A4 Article in a conference publication|
|Event||IEEE International Conference on Data Mining - Singapore, Singapore|
Duration: 17 Nov 2018 → 20 Nov 2018
|Name||IEEE International Conference on Data Mining Proceedings|
|Conference||IEEE International Conference on Data Mining|
|Period||17/11/2018 → 20/11/2018|