Inference of a rumor’s source in the independent cascade model

Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser, Lena Krieg, Malin Rau
Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, PMLR 216:152-162, 2023.

Abstract

We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al. (2003). In this model, a node of a network is the source of a rumor – it is informed. In discrete time steps, each informed node “infects” each of its uninformed neighbors with probability p. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model. In this work we present a maximum likelihood estimator for the rumor’s source, given a snapshot of the process in terms of a set of active nodes X after t steps. Our results show that, for acyclic graphs, the likelihood estimator undergoes a phase transition as a function of $t$. We provide a rigorous analysis for two prominent classes of acyclic network, namely d-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v216-berenbrink23a, title = {Inference of a rumor’s source in the independent cascade model}, author = {Berenbrink, Petra and Hahn-Klimroth, Max and Kaaser, Dominik and Krieg, Lena and Rau, Malin}, booktitle = {Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence}, pages = {152--162}, year = {2023}, editor = {Evans, Robin J. and Shpitser, Ilya}, volume = {216}, series = {Proceedings of Machine Learning Research}, month = {31 Jul--04 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v216/berenbrink23a/berenbrink23a.pdf}, url = {https://proceedings.mlr.press/v216/berenbrink23a.html}, abstract = {We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al. (2003). In this model, a node of a network is the source of a rumor – it is informed. In discrete time steps, each informed node “infects” each of its uninformed neighbors with probability p. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model. In this work we present a maximum likelihood estimator for the rumor’s source, given a snapshot of the process in terms of a set of active nodes X after t steps. Our results show that, for acyclic graphs, the likelihood estimator undergoes a phase transition as a function of $t$. We provide a rigorous analysis for two prominent classes of acyclic network, namely d-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.} }
Endnote
%0 Conference Paper %T Inference of a rumor’s source in the independent cascade model %A Petra Berenbrink %A Max Hahn-Klimroth %A Dominik Kaaser %A Lena Krieg %A Malin Rau %B Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2023 %E Robin J. Evans %E Ilya Shpitser %F pmlr-v216-berenbrink23a %I PMLR %P 152--162 %U https://proceedings.mlr.press/v216/berenbrink23a.html %V 216 %X We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al. (2003). In this model, a node of a network is the source of a rumor – it is informed. In discrete time steps, each informed node “infects” each of its uninformed neighbors with probability p. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model. In this work we present a maximum likelihood estimator for the rumor’s source, given a snapshot of the process in terms of a set of active nodes X after t steps. Our results show that, for acyclic graphs, the likelihood estimator undergoes a phase transition as a function of $t$. We provide a rigorous analysis for two prominent classes of acyclic network, namely d-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.
APA
Berenbrink, P., Hahn-Klimroth, M., Kaaser, D., Krieg, L. & Rau, M.. (2023). Inference of a rumor’s source in the independent cascade model. Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 216:152-162 Available from https://proceedings.mlr.press/v216/berenbrink23a.html.

Related Material