# Confidence Sets for the Source of a Diffusion in Regular Trees

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2015.

## Built on by (most cited first, 3 of 3)

- [Diffusion Source Identification on Networks with Statistical Confidence](https://mlsanity.com/paper/2106.04800/) (2021)
- [Archaeology of random recursive dags and Cooper-Frieze random networks](https://mlsanity.com/paper/2207.14601/) (2022)
- [Leaf Stripping on Uniform Attachment Trees](https://mlsanity.com/paper/2410.06481/) (2024)

## Abstract (arXiv)

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'olya 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.