Inference of a Rumor's Source in the Independent Cascade Model
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.