Allerton 2016 / Applied Network Science 2017 · WWW 2017 · IEEE TNSE 2019

Observer Placement for Source Localization（Spinelli、Celis、Thiran 系列）

EPFL 这组工作研究：预算只有 k 个观测节点时，放在哪里最能定位传播源。核心结论是：传输时延方差低和方差高时，最优部署不同；若能在传播过程中追加传感器，所需数量可以大幅减少。

本页依据 arXiv 1608.04567 v3（Allerton 版，期刊版的前身）和 arXiv 1702.01056（Back to the Source 在线方法）全文；2019 年 TNSE 框架论文只取得官方摘要。

1研究问题

已知网络，单一未知源，不知道传播开始时间。只有被选中的观测节点会报告自己的感染时间。问题是：给定预算 k，选哪 k 个节点，使最大似然估计猜中源的概率 Ps 最大（另一个指标是估计源与真源的期望距离，作者实验显示两者基本一致）。

2模型与估计

带权无向图，边权 w_uv 是传输时延的期望；实际时延是随机变量，实验中用截断高斯，标准差与 w_uv 成正比，比例记为 σ。
因为开始时间未知，只能用观测节点之间感染时间的差。
估计：在给定先验下取使观测似然最大的节点。

3低方差：等价类与 LV-OBS

零方差时，候选源 u 对观测集合 O 的"距离差向量"决定一切：两个节点的距离差向量相同，就无法区分，属于同一等价类。观测集合把全图划分成若干等价类。

零方差下，估计只能落到正确的等价类，再在类内按先验随机选一个，所以

Ps(O) = Σ_s Q(s)² / Q([s]_O) 均匀先验时 Ps(O) = 等价类个数 / n

要把所有节点区分开所需的最少观测数叫双重解析集（DRS），它常常接近 n−1，不现实。作者证明低方差时最优部署与零方差时相同，问题仍是 NP 难，于是给出贪心算法 LV-OBS：每次加入使 Ps 增加最多的节点，直到预算用完。

零方差下，"等价类"就是"观测之后仍然无法排除的候选源集合"。所以 LV-OBS 实际上是在零方差、确定性的意义下，用"类的个数"做目标来压缩候选集合。这是你的方案在确定性情形下的直接前身。

4高方差：HV-OBS

时延噪声沿路径累积，离所有观测节点都远的两个候选源，即使距离差向量不同，也会因为噪声而难以区分。HV-OBS 增加一个约束：只用长度不超过 L 的路径来区分节点，迫使观测节点在网络中分布得更均匀。L 需要标定；存在一个方差阈值 σ1，低于它用 LV-OBS 更好，高于它用调好 L 的 HV-OBS 更好。

5实验（Allerton 版）

网络	节点 / 边	平均度	直径	使 Ps(LV-OBS)=1 的最小预算
Friends & Families	120 / 563	9.38	6	约 9%
Facebook 消息	1020 / 6205	12.16	5	约 5%
California 道路	1259 / 1801	2.86	66	约 9%

每个节点轮流作源，F&F 每节点 20 次、另两个网络各 5 次；后两个网络只用前 20 个观测。对照：介数中心性、覆盖率（Zhang 等）、K-median。作者报告 LV-OBS 与 HV-OBS 都系统性优于这三个基线；F&F 和 California 上高方差时 HV-OBS 优于 LV-OBS，Facebook 上没有。

6Back to the Source（WWW 2017）：在线追加传感器

先放少量静态传感器；第一个静态传感器被感染后，开始逐个放置动态传感器。
维护候选源集合 B_i：在已有观测下后验概率大于 0 的节点。未感染的传感器也提供信息。
时延取有界支撑的连续分布（如 [(1−ε)w, (1+ε)w] 上的分布）时，真源永远不会被排除，传感器足够多时一定收敛到真源（定理 1、2）。
选下一个传感器的"增益"有三种，其中 Size-Gain 就是候选集合大小的期望减少量。
作者报告：动态预算受限时，成功率从静态策略的约 5% 提高到约 75%；预算不限时，各拓扑上约 3% 的节点作传感器即可唯一定位源，而许多纯静态方法需要超过 30%。

这是你的方案最直接的近邻：它已经按"缩小候选源集合"选传感器。差别在于它的集合基于"概率是否为零"，靠时延有界保证真源不丢；高斯等无界时延下这种集合会非常大或失去意义。

72019 年 TNSE 框架论文

官方摘要显示，它把"静态 / 动态传感器"和"离线 / 在线定位"组合成一个通用框架，并实证研究了四种组合，结论是动态传感器能显著减少所需传感器数。全文出版商页面无法取得，本页不转述其中的定理和数字。

8本项目的本地复现（不是论文结果）

2026-10-12 实测

仓库 bmspinelli/observers_for_source_loc（提交 2474797）是 Python 2 代码，原样不能运行；在副本中做了 24 条替换后可运行，其中 1 条是对作者意图的假设。三个数据集与论文表 I 的节点、边数完全一致。

F&F 上 LV-OBS 需要 12 个观测节点（10%）才把不可分辨比例降到 0，论文报告约 9%，差一个。
σ=0 时只有 LV-OBS 的估计集合恰为 1 个节点，其他部署靠并列才"命中"。
作者的模拟每次调用都重新用系统熵播种，同一配置两次运行可差 0.06；在每节点 3 次的样本量下，未能确认方法间的排名。

详见 output/thesis_code_repro_20261012/README_zh.md。

9作者代码讲解

仓库 bmspinelli/observers_for_source_loc，提交 24747976（2017-02-07）。README 说明它对应 Allerton 2017 版本，附三个数据集。仓库里没有 Back to the Source 在线方法的代码。

文件	作用
`diffusion.py`	连续时间 SI 模拟：从源出发按最早感染时间逐个处理节点，每条边的时延取截断高斯（均值为边权、标准差为 σ×边权，截断在 [0.5w, 1.5w]），也可选高斯或指数
`source_estimation.py`	`preprocess` 计算每条边的时延方差、观测节点到全图的最短路；`ml_estimate` 给出最大似然源估计
`source_est_tools.py`	距离差均值向量 `mu_vector_s`、协方差 `cov_mat`、等价类 `classes`、只保留前若干个观测的 `filter_diffusion_data`
`ln_obs.py`	LV-OBS：对每个可能的首个观测节点各跑一遍贪心，取不可分辨比例最小的方案
`hn_obs.py`	HV-OBS：只用长度不超过 l 的观测间路径，贪心增加"被这些路径覆盖的节点数"
`kmedian.py`、`betweenness_centrality.py`	对照方法：K-median 贪心、介数
`test_source_loc.py`	Python 2 驱动脚本：读图与观测、模拟 20 次、估计源

`ml_estimate` 的三个分支

σ = 0：按到观测节点的距离差把所有节点分类；与观测到的时间差完全一致的那一类就是估计集合，类内均匀。
图是树：对每个候选源算距离差均值 μ_s，协方差 Λ 对所有候选相同，按高斯对数似然打分。这就是 Pinto 等 2012 命题 1 的估计。
一般图：对每个等价类中的每个候选 s，用"s 到各观测节点的最短路"拼成一棵树，在树上求 Λ_s，再算似然；最后把同一等价类内各节点的对数似然取平均，赋给整个类。最终输出后验最大的所有节点。

LV-OBS 的打分

ln_obs.__prob_err 计算 Σ_类(|类| − 1)/n，等于 1 − 等价类个数/n，即均匀先验下"猜错概率"。贪心每步加入使它最小的节点。

已核实的问题

Python 2 语法（print 语句、cPickle、iteritems）、scipy.misc.logsumexp 已被移除，在当前环境原样不能运行。
hn_obs.place_observers(graph, …) 内部用了未定义的 g；__update 把单条路径当成"路径列表"遍历。
ln_obs.approx_budget 预算为 1 时 UnboundLocalError。
diffusion.diffusion 每次调用都以 seed(None) 重新播种，外部固定种子无效，结果不可重复。
HV-OBS 代码优化的是"短路径覆盖的节点数"；它与论文算法 2 的逐行对应关系本次没有核对。

10与你的方案（传感器部署 + 有效源集合）的关系

维度	LV/HV-OBS	Back to the Source	你的方案
部署方式	静态，一次放完	静态 + 在线追加	静态
输出	点估计	候选集合（概率不为零）	α 水平的置信集合
覆盖	不讨论	有界时延下为 1	对每个固定源 ≥ 1−α
部署目标	猜中概率（≈ 等价类个数）	候选集合的期望缩小量	有效集合的期望大小
传播模型	连续时延，开始时间未知	有界支撑连续时延	同步 SI（几何时延），时刻已知

排重结论："按候选集合大小选传感器"已有前作。你的方案能站住的区别只剩：时延无界时，用允许 α 误差的检验集合代替"概率不为零"的集合；以及在静态部署下优化它。阶段 1 的小图实验应直接把 LV-OBS 和 Size-Gain 的静态版本作为基线。