传播溯源

前面的问题都是“正向”的：已知源头与网络，预测传播。传播溯源（source localization）是反问题：已知网络和部分传播观测，推断源头（零号病人、谣言发起者、污染源）。它在暴发调查、院内感染溯源、食源性疾病追查和虚假信息治理中都有需求。

问题设定

观测通常有两种：（1）某一时刻的感染快照（谁已感染）；（2）少数观测点（传感器节点）被感染的时刻。难点在于：同一个快照可以由许多不同源头以不同的传播路径产生，问题本质上是在指数多的传播历史上做推断。

主要方法

• 谣言中心性（Shah 与 Zaman 2011，IEEE Trans Inf Theory）：对树状网络上的 SI 传播，源头的似然正比于“与快照一致的感染顺序”数目。对节点 $v$ 为根的感染子树，这一数目为 $R(v)=n!\prod_{u}\dfrac{1}{T_u^v}$，$T_u^v$ 是以 $v$ 为根时 $u$ 的子树大小；最大化 $R(v)$ 的节点称为谣言中心，对正则树是最大似然估计。一般网络上常用其 BFS 树近似。
• Jordan 中心与距离中心：在感染子图中，取到其他感染节点最大距离（或平均距离）最小的节点。简单、稳健，在快照较早时效果不错。
• 基于观测点（Pinto、Thiran 与 Vetterli 2012，PRL）：若 $s$ 是源头，观测点 $o$ 的感染时刻约为 $t_o\approx t_0+d(s,o)\cdot\bar\tau$，加上沿路径累积的随机延迟；用高斯近似写出到达时刻的似然，选使之最大的候选源。它只需要少量观测点（稀疏观测）。简化版本是选择使 $t_o-d(s,o)$ 方差最小的 $s$。
• 动态消息传递（Lokhov 等 2014，PRE）：对每个候选源用动态消息传递计算快照的近似概率，在稀疏网络上精度高。
• 有效距离（Brockmann 与 Helbing 2013）：在流动网络上，以真实源头为中心时到达时间与有效距离的关系最接近线性，据此在候选城市中找源头（见集合种群与全球传播）。

观测点的选择

在基于观测点的方法中，放在哪里和放多少决定了能否定位。直觉上应选中心节点，但中心节点之间路径高度重叠、信息冗余。Zhang 等（2016，Physica A）研究了如何在复杂网络中识别高效的观测点以定位传播源；这一问题与网络可控性与稳定性中的“最少观测节点”有相似的组合结构，但目标不同：前者要区分传播源，后者要重构系统状态。代码示例“传播溯源”中，介数最高的 5% 节点作为观测点（平均误差约 1.3 跳）反而不如随机选取的观测点（约 1.1 跳），而早期快照上的 Jordan 中心命中率约 73%（代码）。