# Inference of a Rumor's Source in the Independent Cascade Model

arXiv: https://arxiv.org/abs/2205.12125 · HTML: https://mlsanity.com/paper/2205.12125/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 47 references that are in the map.
- First posted on arXiv 24 May 2022.

## Builds on (most cited first, 7 of 7)

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Locality defeats the curse of dimensionality in convolutional teacher-student scenarios](https://mlsanity.com/paper/2106.08619/) (2021)
- [Catch'Em All: Locating Multiple Diffusion Sources in Networks with Partial Observations](https://mlsanity.com/paper/1611.06963/) (2016)
- [Finding Patient Zero: Learning Contagion Source with Graph Neural Networks](https://mlsanity.com/paper/2006.11913/) (2020)
- [Reconstructing parameters of spreading models from partial observations](https://mlsanity.com/paper/1608.08698/) (2016)
- [Balancing spreads of influence in a social network](https://mlsanity.com/paper/1906.00074/) (2019)
- [Approximate Identification of the Optimal Epidemic Source in Complex Networks](https://mlsanity.com/paper/1906.03052/) (2019)

## Abstract (arXiv)

We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al. [2003]. In this model, a small subset of nodes from a network are the source of a rumor. 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, see, e.g., Lokhov [NeurIPS'16] or Mastakouri et al. [NeurIPS'20]. 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 cycle-free graphs, the likelihood estimator undergoes a non-trivial phase transition as a function 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.