Diffusion Source Identification on Networks with Statistical Confidence

1研究问题：为什么要"集合"而不是"一个点"

传播源识别（DSI）的经典做法是给出一个点估计，比如 Shah 与 Zaman 的谣言中心。作者指出两件事：一是这类方法的理论保证基本只在规则树之类的理想图上成立；二是即使在理想的无穷正则树上，点估计猜中的概率也常低于 0.3，到一般网络上更低。

另一方面，DSI 天生只有一次观测：某一时刻谁被感染了。SI 模型有马尔可夫性，之后再多看几次快照也不会带来关于源的新信息。数据量没法靠"多采样"补足。

所以作者换了一个目标：在任意网络结构上，构造一个有限样本有效的置信集，即对真源 s*，P(s* ∈ S(Y)) ≥ 1 − α，并且希望这个集合尽量小。

2模型与数据

网络 G 无向无权（作者说可推广到加权）。传播用 SI 模型，但时间不是按轮计的，而是按感染次数计：

1. 初始只有源 s* 被感染。
2. 每一步，在所有"已感染—未感染"的边中均匀随机抽一条，把它的未感染端点感染。
3. 进行 T 次，得到一条传播路径 z = (v₀=s*, v₁, …, v_T)，记录了感染顺序。

但观测者看不到顺序，只看到快照 y：一个 n 维 0/1 向量，标出哪些节点被感染（约 T 个且连通；正文对路径写 T+1 个节点、对样本空间写恰好 T 个，记法略有出入）。路径到快照的映射 ζ 是多对一的，顺序信息丢了，DSI 要从 y 反推第一个节点。

3统一框架：用"差异函数"把旧方法装进来

作者把源当作模型参数 s，把识别写成一个优化问题：选一个 s，让它生成的随机路径 Z 与观测 y 的期望差异最小。

关键设计是差异函数 ℓ 比较的是快照 y 与完整路径 Z，而不只是两个快照，这样能用上路径里的感染顺序。两个已有方法是它的特例：

• ℓ = 1 − 𝟙(y = ζ(z))：在无穷正则树上就是谣言中心。
• ℓ = ‖y − ζ(z)‖²：对称差，等价于 Nguyen 等 2016 年的方法。

作者认为这两个都不够好：前者只取两个值，太粗；两者都没用到感染顺序。于是提出"规范族"：

直观地说：观测里被感染的节点，若在模拟路径里也很早被感染，相似度就高。ADiT（Averaged Deviation – inverse Time）取 h(t) = 1/t；取 h ≡ 2 就退化为对称差（论文记为 Euclidean/L2）。

4置信集：对每个候选节点做一次检验

对每个候选 s 检验原假设 H₀: s* = s。检验统计量就是上面的期望差异，p 值是"从 s 出发的随机传播，比观测更不像的概率"：

定理 1：这样得到的 S(y) 是有效的 1−α 置信集，与网络结构、选哪个差异函数都无关。这是标准的"检验反演"：在 s* 为真时，p 值不小于均匀分布，所以真源被拒绝的概率至多 α。

5算法 1：用蒙特卡洛近似 p 值

一般图上 SI 的概率质量函数算不出来，所以 T_s 和 ψ_s 都用模拟估计。对快照里的每个感染节点 s：

1. 从 s 出发模拟 2m 条长度为 T 的传播路径。
2. 用后一半（m 条）估计观测的统计量 T̂_s(y)。
3. 对前一半的每条路径 z_j，同样用后一半估计 T̂_s(ζ(z_j))，这是"零假设下统计量的分布"。
4. p 值估计为前一半中 T̂_s(ζ(z_j)) ≥ T̂_s(y) 的比例。
5. p̂ 大于 α 的节点进入置信集。

flowchart LR
  Y["观测快照 y
（T 个感染节点）"] --> C{"对每个感染节点 s"}
  C --> S["从 s 模拟 2m 条路径"]
  S --> A["后 m 条：估计统计量 T̂_s"]
  S --> B["前 m 条：零分布样本"]
  A --> P["p̂_s = 零分布中 ≥ T̂_s(y) 的比例"]
  B --> P
  P --> D{"p̂_s > α ?"}
  D -- 是 --> K["留在置信集"]
  D -- 否 --> R["排除"]

m 怎么选。作者用中心极限定理估计：p 值误差大约 2√(α(1−α)/m)。α=0.1、m=10000 时约为 0.006，也就是 0.6 个百分点。正文此处写作 "0.006%"，按公式应为 0.006（0.6%），疑为笔误。

复杂度。朴素实现是 Õ(mT² + m²T²)：后一项来自"每条零分布路径都要对 m 条参考路径求平均"。各候选节点之间互相独立，可直接并行。

6三种加速

(a) 规范族的缓存：把 m² 降到 m

规范族的统计量只依赖"每个节点在第 k 个被感染的次数" M_{v,k}。先把参考路径汇总成这张计数表，任何快照的 T̂_s 都能在 O(T) 内算出，单个 p 值总成本降到 Õ(mT)。这也是作者坚持用规范族的计算理由。

(b) 度为 1 节点的"满射重要性采样"

叶子 u 只有一个邻居 v₀，从 u 出发的传播必经 v₀。作者构造了从 v₀ 路径到 u 路径的映射，并给出似然比（定理 2），推广出一种映射不是一一对应的重要性采样（定理 3）。这样叶子节点不用自己采样，复用邻居的样本即可。

(c) 一阶同构节点共享样本

若存在一个只动 u、v 及其一阶邻居的置换，使邻接矩阵不变，则从 u 出发的路径经置换后与从 v 出发的路径同分布（定理 4）。用"度相同、邻居度序列相同、二阶邻居集相同"等必要条件先筛（命题 2），每个同构组只需采样一次。更高阶的同构识别代价指数增长，作者只用一阶。

7实验结果（论文报告值）

设置：4-正则树、优先连接（PA）、小世界（SW）三种随机网络，N=1365，平均度低于 4；T=150；m=10000。正文写 100 次重复，表 1、表 2 题注写 200 次，二者不一致。

点估计几乎猜不中（表 1）

置信集覆盖达标，大小随网络差异很大（表 2，90% 水平）

在正则树和 PA 上，ADiT 的集合比 Euclidean 小两到三成，说明感染顺序有信息；SW 上两者接近。集合大小与置信水平略超线性，与 T 大致线性。作者给的覆盖率标准误约 3%，ADiT 在正则树上的 86.2% 比名义 90% 低约 1.3 个标准误，偏低但不算显著。

加速效果（表 3、表 4，单位秒）

树和 PA 上约省一半以上，小世界网络上几乎无效（结构不对称，同构和叶子都少）。作为对比，谣言中心约 2 秒。作者另在 381 个真实网络上报告：经济、社会网络省 40% 以上，生物、信息网络省 10–20%（细节在附录）。

COVID-19 案例

中国 49 个主要城市的人口流动网络，2020 年 1 月 24 日有 21 个城市确诊不少于 5 例。所有点估计方法都没认出武汉（它在网络里不居中）；80% 和 90% 置信集分别有 6 个和 11 个城市，都包含武汉，封城后一周每天都如此。

8我们的本地复现（不是论文结果）

9作者代码讲解

仓库 lab-sigma/Diffusion-Source-Identification，本节依据提交 24691653。README 说明当前是更新版代码，ICML 论文实验对应 legacy/ 目录。

一次置信集计算的调用链

1. confidence_set(x, α) 调用 p_values(x)。候选集合由 source_candidates(x) 给出，基类直接返回感染节点。
2. create_groupings：iso=True 时把一阶同构节点并成一组；d1=True 时把度为 1 的节点挂到其邻居所在组，只对组长采样。
3. sample(s)：从组长出发生成 m_l + m_p 条路径。single_sample 每步在"感染—未感染"边集中均匀抽一条，正是论文的模型。
4. sample_prep：同构成员把路径做置换；叶子成员调用 compute_ratios 算重要性权重（定理 2 的似然比）。
5. compute_p_vals：规范族时，node_vals 先用后 m_l 条路径累计每个节点的 Σh(t)（即论文的 M_{v,k} 缓存），temporal_loss 再对观测和前 m_p 条路径各算一次损失。
6. p 值返回两部分：严格更差的比例 ψ_g 与相等的比例 ψ_e；confidence_set 用 ψ_g + U·ψ_e > α 判定，U 为均匀随机数，即随机化并列处理。

代码与论文的差别

• 默认 m_l = m_p = 1000，论文实验用 m = 10000。
• p 值没有 +1 修正；我们在小模型上测到 m=50 时逐源覆盖约少 1.6 个点（§8）。
• 只有 FixedTSI（固定感染数）一种传播模型，不是按轮推进的同步 SI。
• 已知缺陷：并行入口用到 Pool 却未导入；precompute_probabilities(samples=None) 引用裸变量 m_l；compute_ratios 在某节点边界边数为 1 时除零（本机约 5% 的复现重复因此中断）。
• 后续工作 Jian 等 2025 在自己的仓库里复制了这套代码（目录 DSI/），新增了一次算多个 α 的 confidence_set_mp，并把 G.neighbors[...] 改为 networkx 的 G.neighbors(...)。

10局限与读法

• 需要完整感染快照。候选集也只取感染节点。只有少数传感器时，未被观测的节点也可能是源，候选池和统计量都要重做。
• 需要准确的模型。定理 1 的有效性以"图已知、传播规律已知"为前提。图有缺边或传播参数不准时，没有保证。
• "有限样本有效"只对精确 p 值成立。蒙特卡洛 p 值没有用 +1 修正；重要性采样复用只有渐近保证。这些在大 m 下影响很小，在小 m 或很多候选时会累积。
• 集合不小。1365 个节点、150 个感染时，90% 集合在正则树和 PA 上是 57–81 个，占感染节点的四成到一半以上。点估计"猜不中"换来的是"圈出一大片"。
• 代价高。串行 20 分钟到近 1 小时，20 核约 1–3 分钟；谣言中心只要 2 秒。池化在不对称网络上基本失效。
• ADiT 是启发式统计量。它没有声称最优。在同一有效性下集合最小的检验是似然比，作者没有与它比较。

11你可能可以做的改进

下表把每个方向与原文的差别、已有近邻、我们手上的证据放在一起。"判断"是依据现有证据的建议，不是已证实的结论。

12相关研究地图：传感器 × 源集合

你问的"有限观测下构造尽量小的源集合，比较达到同一覆盖时所需的传感器数、集合大小和时间"，可以拆成两半，每一半都有人做过，两半合在一起的直接研究这次没有找到：