Confidence Sets for the Source of a Diffusion in Regular Trees

Abstract

We study the problem of identifying the source of a diffusion spreading over a regular tree. When the degree of each node is at least three, we show that it is possible to construct confidence sets for the diffusion source with size independent of the number of infected nodes. Our estimators are motivated by analogous results in the literature concerning identification of the root node in preferential attachment and uniform attachment trees. At the core of our proofs is a probabilistic analysis of Pólya urns corresponding to the number of uninfected neighbors in specific subtrees of the infection tree. We also provide an example illustrating the shortcomings of source estimation techniques in settings where the underlying graph is asymmetric.

23 pages

References in corpus (2)

• Locating the Source of Diffusion in Large-Scale Networks
• Source Localization in Networks: Trees and Beyond

Cited by in corpus (16)

• Epidemic Source Detection in Contact Tracing Networks: Epidemic Centrality in Graphs and Message-Passing Algorithms
• Finding Patient Zero: Learning Contagion Source with Graph Neural Networks
• Anonymity Properties of the Bitcoin P2P Network
• Detection of Rumors and Their Sources in Social Networks: A Comprehensive Survey
• On the discovery of the seed in uniform attachment trees
• Rumor Source Detection under Querying with Untruthful Answers
• Quickest Inference of Network Cascades with Noisy Information
• Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process
• Inference on the History of a Randomly Growing Tree
• Diffusion Source Identification on Networks with Statistical Confidence
• Necessary and Sufficient Budgets in Information Source Finding with Querying: Adaptivity Gap
• Root and community inference on the latent growth process of a network
• Degree centrality and root finding in growing random networks
• Joint Inference on Truth/Rumor and Their Sources in Social Networks
• Information Source Finding in Networks: Querying with Budgets
• On a Tail Bound for Root-Finding in Randomly Growing Trees