Robust Cascade Reconstruction by Steiner Tree Sampling

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussavertaisarvioitu

Tutkijat

Organisaatiot

Kuvaus

We consider a network where an infection has taken place and a subset of infected nodes has been partially observed. Our goal is to reconstruct the underlying cascade that is likely to have generated these observations. We reduce this cascadereconstruction problem to computing the marginal probability that a node is infected given the partial observations, which is a #P-hard problem. To circumvent this issue, we resort to estimating infection probabilities by generating a sample of probable cascades, which span the nodes that have already been
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.

Yksityiskohdat

AlkuperäiskieliEnglanti
Otsikko2018 IEEE International Conference on Data Mining (ICDM)
TilaJulkaistu - marraskuuta 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaIEEE International Conference on Data Mining - Singapore, Singapore
Kesto: 17 marraskuuta 201820 marraskuuta 2018

Julkaisusarja

NimiIEEE International Conference on Data Mining Proceedings
KustantajaIEEE
ISSN (painettu)1550-4786
ISSN (elektroninen)2374-8486

Conference

ConferenceIEEE International Conference on Data Mining
LyhennettäICDM
MaaSingapore
KaupunkiSingapore
Ajanjakso17/11/201820/11/2018

ID: 30233697