Physical Review Letters 109, 2012 · arXiv 1208.2534
Locating the Source of Diffusion in Large-Scale Networks
网络太大，无法观测每个节点。Pinto、Thiran 与 Vetterli 证明：只用少数观测节点记录的到达时间和来向，也能估计传播源；在任意树上给出了使正确定位概率最大的估计，并给出一般图上 O(N³) 的近似。
1研究问题
源 s* 在未知时刻 t* 开始传播，源在全部节点上先验均匀。只有 K 个观测节点会报告信息，目标是最大化正确定位概率，等价于最大似然估计。直接计算似然要对所有可能路径和所有边时延求和，复杂度随节点数指数增长。
2模型与观测
- 节点首次从某个邻居收到信息后，向其他邻居转发；边 uv 上的传播时延 θ_uv 为随机变量，联合分布已知。
- 每个观测节点 o 记录从哪个邻居、在什么时刻收到信息，即 (o, v, t_{v,o})。
- 树上的结论假设各边时延独立同分布，服从 N(μ, σ²)，μ、σ 已知。
3树上的最优估计（命题 1）
- 确定活跃子树：树上只有部分观测节点能收到信息（活跃观测）；它们记录的"来向"确定了源所在的活跃子树 T_a，源只可能在其中。
- 取时间差：以第一个活跃观测 o_1 为参照，d_k = t_{k+1} − t_1。未知开始时刻 t* 在相减时抵消。
- 写出均值与协方差：若 s 是源，d 的均值为 [μ_s]_k = μ·(|P(s, o_{k+1})| − |P(s, o_1)|)；协方差 Λ 由观测之间路径的公共部分决定：对角线为 σ²·|P(o_1, o_{k+1})|，非对角为 σ²·|P(o_1, o_{k+1}) ∩ P(o_1, o_{i+1})|。在树上 Λ 不依赖候选 s。
- 打分：ŝ = argmax_{s∈T_a} μ_sᵀ Λ⁻¹ (d − μ_s/2)，复杂度 O(N)。
作者说明：观测稀疏时 d 是多段时延之和，按中心极限定理近似高斯，所以非高斯时延下该估计也接近最优（证明在补充材料中）。
4为什么只看时间差：一个反例
观测节点 A、B 分别位于候选源 X 和 Y 的两侧，且 X 到 A、B 的距离都是 3，Y 到 A、B 的距离都是 1。
| 真源 | A 的到达时刻 | B 的到达时刻 | 时间差 A − B |
|---|---|---|---|
| X | t* + 约 3μ | t* + 约 3μ | 约 0 |
| Y | t* + 约 μ | t* + 约 μ | 约 0 |
因为 t* 未知，"到达得早"不构成证据；两种情况的时间差分布相同，这两个观测无法区分 X 和 Y，它们落在同一个等价类里。要区分它们，需要再放一个与 X、Y 距离差不同的观测节点。这也是后来 Spinelli 等研究"观测节点放在哪里"的出发点。
5一般图：BFS 近似（式 6）
一般图上，实际传播走的是某棵生成树，但生成树的数量可能指数级多。作者假设：若 s 是源，信息沿以 s 为根的广度优先树（最短路径）到达各观测。于是对每个候选 s，在它自己的 BFS 树上计算 μ_s 和 Λ_s，取 argmax μ_sᵀ Λ_s⁻¹ (d − μ_s/2)。总复杂度 O(N³)，属于次优近似。
6结果
达到 90% 定位概率所需的观测比例（N = 100，μ/σ = 4）
| 网络 | 按高度数放观测 | 随机放观测 |
|---|---|---|
| Apollonian | 4% | 25% |
| Barabási–Albert | 18% | 41% |
| Erdős–Rényi（Np = 0.5） | 34% | 49% |
| Erdős–Rényi（Np = 2） | 32% | 44% |
- 多次级联（命题 2）：源发出 C 次独立传播时，正确定位概率以指数速度逼近确定性时延下的上限 P_max。
- 霍乱案例：KwaZulu-Natal 2000 年霍乱，Thukela 流域网络，随机选 20% 社区作观测时，估计源与首个报告社区的平均误差小于 4 跳（表中 3.3 跳、约 23.7 km）。作者注明首个报告社区不一定是真源。
7代码情况
2026-10-13 在 GitHub 检索，没有找到作者发布的代码。两个可读的相关实现：
- Spinelli 等的仓库（
bmspinelli/observers_for_source_loc，source_estimation.py）：mu_vector_s正是 [μ_s]_k 的距离差，cov_mat按观测路径公共部分求协方差，树上与命题 1 一致；一般图上用"候选到各观测的最短路"拼成树，并把同一等价类内的对数似然取平均。时延用截断高斯，方差按边权逐边累加。 - NetOrigin（Li、Manitz 等）的
origin_bayesian：同样是"以源为分量的高斯混合"，但 μ、Λ 由模拟得到的样本均值和收缩协方差估计，并且直接用绝对到达时间（假设开始时刻已知），不是 Pinto 的时间差公式。
8局限
- 需要已知网络、已知时延分布；作者在结论中指出网络不准时的稳健性有待研究。
- 观测节点的选择对结果影响很大，本文没有给出部署方法，只比较了高度数与随机。
- 树上的最优性依赖独立同分布高斯时延；一般图上的 BFS 假设没有最优性保证。
- 观测需要记录"来向"，这比只记录时间要求更多。
9与 PR-SD 的关系
- Pinto 是"少数传感器记录时间、反推源"这条研究线的经典起点之一，SDSA、PR-SD 等使用传感器时间戳的方法都在这条线上；但各方法的模型与估计方式不同，不能说它们的数学原型"都来自"本文。
- 本文留下的"观测节点放在哪里"问题，后续由 Spinelli 等专门研究；SDSA 用多次模拟加贪心部署，PR-SD 用不完整图上的 PageRank 排名部署。"无需传播模拟"只描述 PR-SD 的部署阶段。
10本页更正记录
此前同名页面（
docs/references/visualizations/pinto2012_explainer.html，原文件未改动）有三处问题：
- 互动演示中，两个候选源对两个哨兵的时间差都约为 0，按本文方法无法区分；该页却根据"两名哨兵约 1 秒就触发"判定源在节点 ④，用了开始时刻已知的绝对时间，与它自己写的"时间差消去未知开始时刻"相矛盾。本页改为第 4 节的反例。
- "SDSA、SDSI、RGAB 的数学原型全部诞生自 Pinto 2012"没有依据，已改为谨慎表述。
- 步骤 3"通过协方差检验"不准确：估计是最大化高斯似然（命题 1、式 6），不是检验。