IEEE Transactions on Information Theory 57(8), 2011
Rumors in a Network: Who's the Culprit?
只知道谁被感染了、不知道先后顺序时，怎样找传播源？Shah 与 Zaman 证明：在正则树上，最大似然估计等价于选谣言中心性最大的节点，即能解释观测感染子图的"合法感染顺序"最多的节点；并精确刻画了这种估计在不同树上猜中的概率。
1研究问题
SI 模型：每条边的传播时间相互独立、服从指数分布。传播从源 v* 开始，经过一段时间后观测到 N 个被感染节点构成的连通子图 G_N，但不知道感染顺序和时间。目标是从 G_N 估计 v*。
2谣言中心性
以 v 为源时，一个"合法排列"是与图结构相容的感染顺序：每个节点都在它的某个邻居之后被感染。在正则树上，由于指数分布无记忆，每个合法排列出现的概率相同，于是 P(G_N | v) 正比于以 v 为源的合法排列个数，记为谣言中心性 R(v, G_N)。在树上它有闭式：
估计量就是 R 最大的节点，称为谣言中心。
3一个可核对的例子
7 个节点的感染树：1–2–3，3–4，3–5，4–6，5–7。按上式逐个计算：
| 候选源 | 各节点子树大小之积 | R = 7! / 积 | 占全部 R 之和 |
|---|---|---|---|
| 1 | 7·6·5·2·2·1·1 = 840 | 6 | 2.8% |
| 2 | 7·1·5·2·2·1·1 = 140 | 36 | 16.7% |
| 3 | 7·2·1·2·2·1·1 = 56 | 90 | 41.7% |
| 4 | 7·1·5·2·1·2·1 = 140 | 36 | 16.7% |
| 5 | 140 | 36 | 16.7% |
| 6、7 | 840 | 6 | 各 2.8% |
节点 3 是谣言中心。"占全部之和"只有在正则树假设下才等于后验概率；这棵小树本身度并不均匀，这里的比例只用于说明公式。表中数值已用程序按定义逐一核对。
4O(N) 算法
- 任选一个根做一次遍历，自下而上传递子树大小（"向上消息"），得到根的 R。
- 自上而下传递：父节点 u 的子节点 c 满足 R(c) = R(u) · T_c / (N − T_c)（"向下消息"）。
- 两遍遍历得到全部节点的 R，取最大者，并列时随机。
5推广到一般树与一般图
- 一般树：把每个候选的合法排列概率近似为"按广度优先顺序感染"那一个排列的概率 P(σ*_v | v)，估计量为 argmax P(σ*_v | v) · R(v, G_N)（式 7）。
- 一般图：不知道传播实际走的是哪棵生成树。作者假设若 v 是源，传播沿以 v 为根的广度优先树 T_bfs(v) 进行，估计量为 argmax P(σ*_v | v) · R(v, T_bfs(v))（式 8）。每个候选用自己的 BFS 树，这是启发式，没有最优性保证。
6主要结论
| 底图 | 谣言中心猜中源的渐近概率 |
|---|---|
| 路径（2-正则树） | 以 t^{-1/2} 衰减到 0（定理 1） |
| d-正则树，d > 2 | 下界为某个正常数 α_d，上界为 1/2（定理 2） |
| 3-正则树 | 恰为 1/4（定理 3） |
| 满足多项式增长的几何树 | 趋于 1（定理 4） |
在小世界、无标度合成网络以及美国电网、互联网 AS 网络上，作者用模拟说明 BFS 启发式在网络"不太不规则"时表现良好；这部分是实验结论，不是定理。
7代码情况
2026-10-13 在 GitHub 检索，没有找到作者发布的代码，只有若干课程项目的第三方实现，本页未审查。
Dawkins 等 2021 的仓库（lab-sigma/Diffusion-Source-Identification，src/diffusion_source/algos.py）中有一个可读的实现 rumor_center(G, x)：
- 用
message_up/message_down实现上面的两遍消息传递，阶乘用Decimal避免溢出。 - 同时计算按度修正的 BFS 排列概率 p，返回"R 最大"和"R·p 最大"两个中心。
- 差别：它在感染子图上只建一棵 BFS 树（根为任意第一个节点），所有候选共用这棵树的 R，而 Shah 的式 (8) 对每个候选用以它为根的 BFS 树。两者在感染子图本身是树时一致，有环时不同。
8局限
- 需要观测全部感染节点，没有传感器或时间信息。
- 精确的最大似然性质只在正则树上成立；一般图上是启发式。
- 即使在最有利的正则树上，猜中概率也不超过 1/2；3-正则树上只有 1/4。这正是 Dawkins 等转向"置信集合"的理由。
9与 PR-SD 的关系
- Shah 处理的是"完整快照、无时间"的观测；PR-SD 使用传感器的首次感染时间和发送者记录，观测条件不同，二者的准确率不能直接比较。
- PR-SD 用 PageRank 选传感器位置，不是用中心性估计源；不能因为两者都用到"中心性"就说直觉相通或继承关系。
- 在相关工作中，Shah 适合作为"完整观测下的经典点估计"引用，说明点估计的理论上限较低。
10本页更正记录
docs/references/visualizations/shah2011_explainer.html，原文件未改动）有三处错误：
- 示例树的谣言中心性写成 2、12、80、24、24、2、2 及 54.8% 等比例；按该页实际画出的树，正确值为 6、36、90、36、36、6、6，节点 3 占 41.7%。
- "数学证明即使没有时间记录也能牢牢锁定真凶"不符合论文：正则树上猜中概率不超过 1/2，路径上趋于 0。
- "PR-SD 的 PageRank 部署与谣言中心性直觉完全相通"属于没有依据的引申，已删除。