IEEE TNSE 4(1), 2016 · arXiv 1510.05461
Confidence Sets for the Source of a Diffusion in Regular Trees
在无穷正则树上，这篇论文证明：要以 1−ε 的概率圈住传播源，所需集合的大小只和 ε 有关，与已感染节点数 n 无关。这是"源置信集"这条线最早的理论结果之一，Dawkins 等 2021 年的工作把它推广到任意图。
1研究问题
谣言中心（Shah 与 Zaman）这类方法只输出一个点，猜中概率不高。作者换了一个问题：能不能输出一个节点集合，以给定概率包含源，并且集合不随传播规模变大？此前 Bubeck、Devroye、Lugosi 对均匀连接树、优先连接树的"根节点"证明过这一点，本文把它搬到正则树上的传播。
2模型
- 底图是无穷 d-正则树。
- 传播按感染顺序展开：已感染节点集合的所有邻居中均匀随机选一个，感染它。这等价于每条边的传播时间服从同一个指数分布。
- 观测到的是 n 个已感染节点构成的子树，但不知道感染顺序，节点标签被抹去。
- 目标：构造集合 H，使 n→∞ 时"源不在 H 中"的概率上极限不超过 ε。
3两个估计量
| 估计量 | 定义（以 u 为根） | 含义 | 集合怎么取 |
|---|---|---|---|
| 子树乘积 φ | 以 u 为根时，所有非根节点的子树大小之积 | 最小化 φ 等价于最大似然，即谣言中心 | 到谣言中心距离 ≤ L 的所有节点 |
| 最大子树 ψ | 以 u 为根时，最大的那棵子树的大小 | 最小化 ψ 得到树的重心；是 φ 的松弛，证明更容易 | ψ 值最小的 K 个节点 |
两者都能用消息传递在 O(n) 时间内算出。
4主要结论
以下结论都要求 d ≥ 3。d = 2 时底图是一条线，传播相当于随机游走，不可能有固定大小的置信集。
最大子树（定理 1、推论 1）
取 ψ 最小的 K 个节点，漏掉源的概率上极限有一个只依赖 d、K 的上界，随 K 增大而下降。推论 1：要达到 1−ε，K 取 C/ε 量级就够，C 只依赖 d，与 n 无关。
子树乘积（定理 2、推论 2）
先证明：距离源 ℓ 步的节点，其 φ 值不比源大的概率随 ℓ 近似指数下降。由此，以谣言中心为圆心、半径为 L 的球是置信集，L 只需按 log(1/ε) / log log(1/ε) 增长。球内节点数随 L 指数增长，但整体所需大小仍比推论 1 小，是关于 1/ε 的次线性量级。这与 φ 对应最大似然的直觉一致。
证明工具
核心是 Pólya 罐模型：各子树中"未感染邻居"的数量像罐中小球一样增长，子树规模占比在极限下收敛到 Dirichlet 或 Beta 分布（引理 1、引理 3）。由这些极限分布直接算出"某个非源节点胜过源"的概率。
5不对称图的反例
作者构造了一个图：一棵 d-正则树和一棵 D-正则树（d < D），用一条边连起来。源在 d-正则树一侧时，n→∞ 下两个估计量都会以概率 1 把 D 树那一端的连接点排在源前面（命题 1），估计可以离源任意远。
补救办法（命题 2）是把图拆成两棵树，各自取谣言中心的球再求并。这能恢复保证，但要多输出节点，而且不能推广到一般图。作者把"考虑度不均匀的更好估计量"列为未来方向。
6局限
- 保证是 n→∞ 的渐近结果，常数 C 没有给出具体值，不能直接算出有限 n 时该取多大的集合。
- 只适用于无穷正则树，作者自己的反例说明对称性不可缺。
- 需要观测全部已感染节点。
- 没有数值实验，没有计算代价分析。
7代码情况
本文是纯理论工作，arXiv 版本没有数值实验。2026-10-13 在 GitHub 按题名、作者和关键词检索，没有找到作者发布的代码。论文中的两个估计量都能用消息传递在 O(n) 时间内算出：谣言中心可参考 Dawkins 等仓库 src/diffusion_source/algos.py 中的 rumor_center；最大子树（重心）只需对每个节点求最大子树大小。
8与你的方案（传感器部署 + 有效源集合）的关系
| 维度 | 本文 | 你的方案 |
|---|---|---|
| 观测 | 全部感染节点 | k 个传感器的首次到达时间 |
| 覆盖保证 | 渐近、无穷正则树 | 有限样本、任意已知图、逐源 |
| 集合大小 | 理论上界 O(1/ε) 或更小 | 以期望大小为部署目标 |
| 部署 | 不涉及 | 核心 |
可借鉴：把"集合大小与 ε、与观测规模的关系"作为理论问题的提法；两树一边的反例可作为方案里的困难测试图。不构成直接排重冲突。