PR-SD 公式与算法实现讲解

0. 全局图景与符号速查

论文 3.1PR-SD 分两个阶段（phase）。第一阶段在不完整图 $G_{\delta }$ 上按 PageRank 得分选出 $m$ 个传感器；第二阶段在一次传播发生后，用感染节点集合、已感染传感器的首次感染时间戳与信息发送者、经验跳数频率 $q_h$ 和 $G_{\delta }$ 给候选源打分，取最高分者作为估计源。

实验里还有两件事不属于 PR-SD 本身，但离不开它们：在完整图 $G$ 上生成真实传播与传感器记录；在 $G$ 上为每个传感器集合标定 $q_h$。下图把四件事和它们用到的图分开画出。

符号速查

术语与符号以 writing_memos/03_术语符号与规范表述库.md 为准。该术语表 5.4 节把时间距离写作 $d({\mathbf{t}}_{O_{+}},{\mathbf{t}}_{O_{+}}^{\prime }(v_i))$，当前双语稿已统一写作 $D_t(v_i)$，本文档跟随双语稿。

1. 图、传播与观测（论文 3.1）

1.1 完整图与不完整图

逐项含义。$G_{\delta }$ 保留全部 $n$ 个节点，只少了边。$\lfloor \cdot \rfloor$ 是向下取整，所以删去的边数是整数 $\lfloor \delta |E|\rfloor$。删边以后可能出现零度节点（孤立点），它们仍在 $V$ 中，这正是算法 1 要为零度节点单独规定转移概率的原因。

讲解算例：Jazz 有 $|E|=2,742$ 条边，$\delta =0.2$ 时 $\delta |E|=548.4$，删去 548 条，剩 2,194 条。冻结结果 results/active/pr_sd_protocol_v4/v4_exp02_supporting_structural_controls/results/jazz__pdnd__delta0p20__seed111__rho0p05__pr_sd/result.json 中 incomplete_edge_count 恰为 2194。

两种删边策略

论文 4.1RDS 对边均匀抽样；PDND 以完整图中的端点度和为抽样权重：

两者都无放回，正好删去 $\lfloor \delta |E|\rfloor$ 条。

讲解为什么论文说 RDS 移除任一节点度数的比例约为 $\delta$。RDS 下每条边被删的概率都是 $k/|E|$，其中 $k=\lfloor \delta |E|\rfloor \approx \delta |E|$。节点 $v$ 有 $d_G(v)$ 条关联边，被删条数的期望为

与 $v$ 的度大小无关。PDND 则让关联高度节点的边权重更大，于是高度节点被删得更多（论文 4.5 节实测为 RDS 的 1.22–1.55 倍）。

讲解np.random.choice 带权无放回抽样是逐次抽取、每次在剩余边上重新归一化的过程，因此某条边最终被删的概率并不严格正比于 $w(u,v)$；“以 $w$ 为抽样权重”的说法准确，但不宜写成“删除概率正比于 $w$”。

1.2 传感器数量与预算

讲解这些数可以和正文对上：4.4 节“5% 预算下六个传感器”（Football）、图 4“每种方法部署 10 个传感器”（Jazz, $\rho =0.05$）。

实现pr_sd/runner.py:1207–1211：math.ceil(node_count * ratio)，并取三个预算中的最大值 sensor_count_max 只部署一次（见 2.5 节前缀）。

1.3 异质 SI 传播

实现真实传播在 core/parallel.py:285–323。离散时间的规则可以写成：

三个记录量的区别。$t_j$ 是时间步；${\mathrm{id}}_j$ 是使 $j$ 首次感染的那个邻居；$h_j$ 是 $j$ 在本次传播树中的深度（从源数起经过几条感染边）。$h_j\ge d_G(s,j)$，因为传播树里的路径不一定是最短路。

讲解一条边上的传播延迟服从几何分布。设 $i$ 在时刻 $t_i$ 被感染，邻居 $j$ 只有 $i$ 一个感染邻居。$i$ 从下一步起每步独立地以 $p_i$ 成功，所以

若 $j$ 有多个感染邻居，$t_j$ 取各条边“先到者”。$p_i$ 越小，延迟越长、越分散。这有助于理解两件事：其一，时间戳携带了到源距离的信息，但带有较大随机性；其二，MLE-P、DISGE 假设所有边的延迟服从同一均值和方差（6.3 节），与“每个节点 $p_i$ 不同”的传播设置不完全吻合。后一点只是理解模型假设差异的角度，论文没有据此作结论，也没有做检验。

IC 与 SIR（论文 4.7）

实现core/parallel.py:42–61 的 _advance_frontier 决定下一步谁仍在传播：

• SI：所有感染节点保留在 $Q$ 中，每步都重试；
• IC：只有本步新感染的节点进入下一步，每个节点对每个邻居只尝试一次，成功概率 $p_i$；
• SIR：每个仍在传播的节点在本步尝试后以 0.05 的概率恢复，恢复后停止转发，但仍算在 $I_{\sigma }$ 中。

1.4 停止规则与感染集合

实现core/config.py:46–59：

return min(node_count, max(1, math.ceil(infection_ratio * node_count)))

代码注释说明：原作者代码的条件是“感染数 $\ge$ 比例 $\times n$”，由于感染数是整数，二者等价于向上取整。Football 在 $\sigma =0.1$ 时目标为 $\lceil 11.5\rceil =12$ 个节点；LastFM 为 $\lceil 762.4\rceil =763$ 个。

讲解因为达到目标就在步内立即停止，最后一步只有一部分节点有机会尝试传播。停止时 $|I_{\sigma }|=\lceil \sigma n\rceil$，除非先撞到 10,000 步上限（例如源所在连通分量太小）。

1.5 传感器记录、最早传感器与输出

实现core/parallel.py:331–339 按升序遍历传感器 ID，只在 infect_time < min_time（严格小于）时更新，所以同一时刻最先遇到的就是最小 ID。

2. 第一阶段：PageRank 引导的传感器部署（论文 3.2）

2.1 PageRank 方程

转移矩阵 $P$ 是什么

设 $A$ 为 $G_{\delta }$ 的邻接矩阵，$d_i={\sum }_j{A}_{ij}$ 为节点 $i$ 在 $G_{\delta }$ 中的度。则

每一行加起来都是 1，所以叫“行随机”。第 $i$ 行描述随机游走者站在 $i$ 时下一步走到各节点的概率：有邻居就等概率挑一个邻居；没有邻居就等概率跳到任意节点。

按分量写开

第一项：每个邻居 $i$ 把自己的得分平均分给 $d_i$ 个邻居，$j$ 拿其中一份。邻居越重要、邻居的邻居越少，$j$ 分到越多。第二项：孤立节点的得分均匀撒给所有节点。第三项：均匀重启，保证每个节点至少有 $(1-\alpha )/n$。论文所说“将邻居得分按其度数归一化后递归传递”就是第一项。

讲解为什么 $\Vert \mathbf{r}{\Vert }_1=1$ 会自动保持。对上式两边求和，由 $P$ 行和为 1 得 $1^{\mathsf{T}}{P}^{\mathsf{T}}\mathbf{r}=(P1{)}^{\mathsf{T}}\mathbf{r}=1^{\mathsf{T}}\mathbf{r}$，于是

从均匀向量 $1/n$ 出发，每次迭代后仍是概率分布，所以算法 1 不需要再归一化。

解存在且唯一

讲解利用 $1^{\mathsf{T}}\mathbf{r}=1$，可以把方程写成 $\mathbf{r}={\mathcal{G}}^{\mathsf{T}}\mathbf{r}$，其中 $\mathcal{G}=\alpha P+\frac{1-\alpha }{n}11^{\mathsf{T}}$ 每个元素都为正。由 Perron–Frobenius 定理，正的随机矩阵有唯一的平稳分布，因此 PageRank 向量存在且唯一。等价地，$I-\alpha P^{\mathsf{T}}$ 可逆，有闭式解

2.2 PageRank 的三种读法

读法一：带重启的随机游走。论文 3.2$\mathbf{r}$ 是这样一个游走者的长期停留比例：每步以 $\alpha$ 沿边走，以 $1-\alpha$ 跳回一个均匀随机节点。

读法二：不同长度游走的加权和。讲解上面的级数里，$\frac{1}{n}(P^{\mathsf{T}}{)}^{k}1$ 是“从均匀随机节点出发走 $k$ 步后所在位置”的分布，权重 $(1-\alpha ){\alpha }^k$ 是几何分布。所以 PageRank 是“随机长度游走的终点分布”，平均游走长度为

这就是论文所说 PageRank“能够利用直接邻居之外的连接关系”的具体含义：$\alpha =0.85$ 时平均看大约 5–6 步远的结构。

读法三：两个极端。讲解

• $\alpha$ 很小：保留到一阶，$\mathbf{r}\approx \frac{1-\alpha }{n}(1+\alpha P^{\mathsf{T}}1)$，而 $(P^{\mathsf{T}}1{)}_j={\sum }_{i\in N(j)}1/d_i$。排序主要由“邻居度数倒数之和”决定，不是由 $j$ 自己的度决定：一个节点如果有很多“只连着它”的低度邻居，得分高。
• $\alpha \to 1$，图连通：无向图上随机游走的平稳分布是 ${\pi }_j=d_j/(2|E_{\delta }|)$。验证：$(P^{\mathsf{T}}\mathbf{\pi }{)}_j={\sum }_{i\in N(j)}\frac{1}{d_i}\cdot \frac{d_i}{2|E_{\delta }|}=\frac{d_j}{2|E_{\delta }|}$。所以 PageRank 排序趋近于度排序。

论文 4.8 节引用 Gleich 的文献（引用键 gleich2015pagerank）写“$\alpha \to 1$ 时 PageRank 趋向与度成比例的平稳分布”，并实测 PR-SD 与 Degree-SD 传感器集合的平均 Jaccard 相似度从 $\alpha =0.50$ 的 0.507 升到 $\alpha =0.95$ 的 0.673，与读法三的方向一致。

2.3 算法 1 逐行对照

实现PR-SD 调用 nx.pagerank(graph, alpha=0.85)（pr_sd/runner.py:337–342）。本机 exp_env 中 NetworkX 为 3.2.1，实际执行的是 _pagerank_scipy，核心循环为：

A = Q @ A                                  # Q = diag(1/d_i)，A 变为行随机（零度行仍为 0）
x = np.repeat(1.0 / N, N)                  # 算法 1 第 3 行
p = np.repeat(1.0 / N, N)                  # 均匀重启向量
dangling_weights = p                       # 零度节点的质量也均匀分配
for _ in range(max_iter):                  # max_iter = 100 → T_max
    xlast = x
    x = alpha * (x @ A + sum(x[is_dangling]) * dangling_weights) + (1 - alpha) * p
    err = np.absolute(x - xlast).sum()     # L1 范数
    if err < N * tol:                      # tol = 1e-6 → ε
        return dict(zip(nodelist, map(float, x)))
raise nx.PowerIterationFailedConvergence(max_iter)

来源：D:\Anaconda\envs\exp_env 中 networkx/algorithms/link_analysis/pagerank_alg.py 的 _pagerank_scipy（本次用 inspect.getsource 读出）。

实现sensor/strategies.py:52 也有一个 deploy_pagerank，逻辑相同，但正式实验走的是 pr_sd/runner.py 的 _pagerank_sequence。

2.4 收敛与迭代次数

讲解设 ${\mathbf{r}}^{\ast }$ 是精确解，${\mathbf{e}}^{(t)}={\mathbf{r}}^{(t)}-{\mathbf{r}}^{\ast }$。两式相减，重启项抵消：

$P^{\mathsf{T}}$ 每列和为 1、元素非负，对任意向量 $\mathbf{x}$ 有 $\Vert P^{\mathsf{T}}\mathbf{x}{\Vert }_1\le \Vert \mathbf{x}{\Vert }_1$。所以每迭代一次误差至少缩小到 $\alpha$ 倍。相邻两次迭代之差同理：

（两个概率向量之差的 $L_1$ 范数不超过 2。）令 $2{\alpha }^t<n\epsilon$，得到一个保守的迭代次数上界

这只是最坏情况上界，真实迭代通常少得多。它说明了两点：$\alpha =0.85$ 时 100 次上限很宽裕；$\alpha$ 越接近 1 收敛越慢，这是 $\alpha =0.95$ 的计算代价。按代码逻辑，若某次运行 100 次仍未收敛会抛出异常并中止，论文 4.8 节已报告 $\alpha =0.95$ 的结果，说明那些运行没有触发该异常。

2.5 排序、并列与前缀嵌套

嵌套性的证明只有一句：两个集合都是同一个排序的前缀，短前缀必然包含在长前缀里。

2.6 小玩具图算例

讲解七个节点：两个三角形 $\{0,1,2\}$、$\{4,5,6\}$，由路径 $0-3-4$ 连起来。下表是用 nx.pagerank(G, alpha=0.85) 实际算出的数值（构造示例，非实验数据）。

• PageRank 顺序为 $0,4,1,2,5,6,3$。1、2、5、6 分数相同，按 ID 升序。取 $\rho =0.3$，$m=\lceil 2.1\rceil =3$，$O_3=\{0,4,1\}$。
• 节点 3 与 1、2、5、6 的度都是 2，但它的两个邻居度都是 3，各自只分给它 1/3，所以 PageRank 最低。这就是 2.2 节“邻居度数倒数之和”的一阶效应。
• 介数中心性却把 3 排第一。PageRank 与介数关注的结构不同，这有助于理解论文表 3、4 中二者准确率接近而传感器集合并不相同。
• 改变 $\alpha$：$\alpha =0.5$ 时 0 号为 0.1700、3 号为 0.1281；$\alpha =0.99$ 时 0 号为 0.1872、3 号为 0.1250，逐渐接近度比例 $3/16=0.1875$ 与 $2/16=0.125$，与 2.2 节的极限一致。

2.7 计算量：PageRank 与 MC 贪心

讲解（推导与 writing_memos/01_方法与实现核对.md 第 6 节一致）

• PageRank 部署：每次迭代处理全部节点和边，$O(n+|E_{\delta }|)$；迭代 $T_{\mathrm{PR}}$ 次；再对 $n$ 个节点排序 $O(n\log n)$。合计 $O(T_{\mathrm{PR}}(n+|E_{\delta }|)+n\log n)$，与预算 $m$ 基本无关。
• MC 贪心部署：选 $m$ 个传感器要 $m$ 轮，每轮 $N_{\mathrm{MC}}=800$ 次传播模拟，每次感染 $\lceil 0.3n\rceil$ 个节点。模拟总次数为 $800m$。

论文表 2 中 SDSA 在 LastFM 上部署需 1,480 秒，PR-SD 为 0.0401 秒；数量级差异主要来自上表的模拟次数随 $m$ 线性增长，而 PageRank 只做一次。

3. 对照：蒙特卡洛贪心部署（SDSA-MC）

这一节帮助理解论文中被比较的 SDSA 部署，以及为什么它慢。

实现core/parallel.py:484–649（部署对照用）与 baselines_ext/sdsa_author.py:82–123（完整方法比较中调用作者代码）。两者做的是同一件事。第 $k$ 轮（已选 $O_{k-1}$）：

其中第 $j$ 次模拟的源从 $V\setminus O_{k-1}$ 均匀抽取，在 $G_{\delta }$ 上以 $p_i$ 传播到 30% 规模，$h^{(j)}(v)$ 是 $v$ 在该次传播树中的深度。代码参数 hops=1，所以 $c_k(v)$ 数的是“$v$ 被源直接感染”的次数；$c_k(v)/N_{\mathrm{MC}}$ 是这一事件概率的蒙特卡洛估计。并列时 np.argmax 取最小 ID。

实现一个容易忽略的细节：计数本身不扣除“已被已选传感器覆盖”的模拟；各轮之间的差别只来自两处，一是已选传感器不再作为源被抽到，二是每轮用新的随机流（core/parallel.py:564–606，作者代码 observer 也是如此）。

SDSA 原文在 Sec. IV-A 用 $f_h(O)$、${\hat{f}}_h(O)$ 等符号表述期望检测概率目标；按术语表 4.3 节的规定，这些原符号只在介绍 SDSA 来源时使用，不移植到 PR-SD。

4. 第二阶段：源检测（论文 3.3）

4.1 贝叶斯公式与最大后验估计

为什么可以去掉分母。分母 $P(\mathcal{D}\mid G_{\delta })={\sum }_{v}P(s=v\mid G_{\delta })P(\mathcal{D}\mid s=v,G_{\delta })$ 是对所有候选求和的结果，对每个候选都一样；比较大小时乘以同一个正数不改变谁最大。

两项分别是什么。先验 $P(s=v_i\mid G_{\delta })$：还没看到这次传播的记录时，$v_i$ 有多大可能是源。似然 $P(\mathcal{D}\mid s=v_i,G_{\delta })$：如果源真是 $v_i$，看到眼前这组感染集合和传感器记录的可能性有多大。

讲解PR-SD 的评分怎样对应这两项。论文写的是“借鉴这一估计思路，采用经验评分规则”。对照关系是：

所以只能说“借鉴 MAP 思路的经验评分”，不能说 PR-SD 计算了后验概率。

4.2 经验跳数频率 $q_h$

写成公式（本文档的展开写法，论文用文字定义）：

若第 $j$ 次模拟没有感染任何传感器，括号里的最小值不存在，该次不计入任何 $q_h$ 的分子，但仍在分母 $N_q$ 中。

best_hop = N + 999
for obs_id in obs_indices:                 # 所有传感器
    hop = total_hop_arr[obs_id]
    if hop != 0 and hop < best_hop:        # 只看已感染者（深度非零）
        best_hop = hop
if best_hop < N:
    detect_hops[best_hop] += 1.0
...
detect_hops /= nr                          # 分母为全部 800 次

实现一个真实例子。上文 1.1 节那个 Jazz 结果（PDND，$\delta =0.2$，$\rho =0.05$，10 个传感器）记录的 hop_prior_distribution 前几项为

这里 $\sum q_h=1$，说明 800 次 40% 规模的模拟每次都至少感染了一个传感器。网络大、预算小、$\sigma$ 小时和会小于 1。

4.3 检测流程逐步对照

讲解补边与临时边各起什么作用。

• 补发送者边：传感器知道“谁把信息传给了我”，这条边在真实传播中一定存在。若它恰好在删边时被删掉，补回来能修复一部分缺边。补边只限已感染传感器的发送者边，不会暴露其他缺失边。每次试验用独立副本，避免上次补的边留给下次（baselines_ext/sdsa_author.py 的说明指出，作者原脚本对所有试验复用同一张图，补过的边会累积）。
• 临时边 $(v_i,{\mathrm{id}}_{\hat{o}})$：可以理解为对“$v_i\to {\mathrm{id}}_{\hat{o}}\to \hat{o}$”这一两跳假设的检验，即假定 $v_i$ 是源、经 ${\mathrm{id}}_{\hat{o}}$ 两跳到达最早传感器。这与其他候选使用 $q_2$（两跳）权重相呼应。它只在评估该候选时存在，不代表断言这条边属于 $G$。这一做法沿用自 SDSA 公开代码（SDSA-main/main_source_detection_RDS_code_in_paper.py 的 find_source）。

4.4 时间戳距离与评分公式

实现代码写的是另一种形式，二者恒等：

prob[suspect] = prior1 * (1.0 - euc_dis / (euc_dis + 1.0))     # core/parallel.py:397
prob[cand]    = prior2 * (1.0 - euc_dis / (euc_dis + 1.0))     # core/parallel.py:439

论文采用右边更简洁的写法。prior1、prior2 就是 hop_prior[1]、hop_prior[2]，即 $q_1,q_2$。

$-1$ 约定的效果。讲解某传感器在观测中于时刻 $t_o$ 被感染、在候选模拟中却没被感染时，该分量的差是 $t_o-(-1)=t_o+1$，平方后为 $(t_o+1{)}^2$。观测时间越晚，惩罚越重。由于模拟和观测都在 $\lceil 0.1n\rceil$ 处停止，“模拟中没感染到”通常意味着候选离该传感器太远，或在 $G_{\delta }$ 上到不了它。

4.5 评分规则的性质

讲解以下都由公式直接推出，便于回答审稿问题。

1. 取值范围。$D_t\ge 0$，所以 $1/(1+D_t)\in (0,1]$；$D_t=0$（时间完全吻合）时取 1，距离增大单调下降。于是 $\mathrm{score}({\mathrm{id}}_{\hat{o}})\in (0,q_1]$，其他候选 $\in (0,q_2]$（$q$ 为 0 时得分为 0）。
2. 其他候选战胜 ${\mathrm{id}}_{\hat{o}}$ 的条件。
   $$\frac{q_2}{1+D_t(v_i)}>\frac{q_1}{1+D_t({\mathrm{id}}_{\hat{o}})}⟺1+D_t(v_i)<\frac{q_2}{q_1}(1+D_t({\mathrm{id}}_{\hat{o}})).$$
   当 $q_1>q_2$ 时，其他候选的时间吻合程度要比 ${\mathrm{id}}_{\hat{o}}$ 好出 $q_1/q_2$ 倍以上才能胜出。
3. ${\mathrm{id}}_{\hat{o}}$ 必然胜出的充分条件。其他候选得分最高为 $q_2$，所以只要
   $$D_t({\mathrm{id}}_{\hat{o}})<\frac{q_1}{q_2}-1,$$
   ${\mathrm{id}}_{\hat{o}}$ 就一定是估计源。用上面 Jazz 例子，$q_1/q_2=0.7788/0.2025=3.85$，即 $D_t({\mathrm{id}}_{\hat{o}})<2.85$ 时其他候选无论如何都赢不了。
4. 与“一跳率”的关系。结合 1.5 节事实（b）：真实源被 $q_1$ 加权当且仅当 $h_{\hat{o}}=1$。一跳率高，意味着真实源更常落在被加权的那个候选上。Jazz 例子中该条件的一跳率为 0.798，可观测条件下的准确率为 0.760，二者接近。这为论文表 4 中“一跳率与准确率同为 PR-SD 最优”提供了一个机制层面的理解；论文没有把它写成因果结论，正文若要使用需另行分析。
5. 随机性。每个候选只模拟一次，所以评分本身是随机的；同一候选重算可能得分不同。代码中候选模拟与真实传播共用同一个试验随机流（rng = np.random.RandomState(seed)，core/parallel.py:283），因此给定试验种子可完全重放。

4.6 完整算例

讲解构造的数字，只为演示计算。设 $O_{+}=\{o_1,o_2,o_3\}$（已按 ID 升序），观测时间 ${\mathbf{t}}_{O_{+}}=(3,4,6)$；$q_1=0.7788$，$q_2=0.2025$（借用 Jazz 实例的值）。

$\hat{s}={\mathrm{id}}_{\hat{o}}$。注意 $v_a$ 的时间吻合比 ${\mathrm{id}}_{\hat{o}}$ 更好，但权重相差 3.85 倍，仍然落后；而 ${\mathrm{id}}_{\hat{o}}$ 的 $D_t=1.732<2.85$，满足 4.5 节第 3 条，结果在算 $v_a,v_b$ 之前就已确定。$v_b$ 的第三个传感器在模拟中未感染，单这一项就贡献了 49。

5. 实验中的评价公式（论文第 4 节）

5.1 源检测准确率 Acc

实现core/parallel.py:830：accuracy = correct / max(1, attempted)，分母是全部尝试的试验，与公式一致。结果文件字段为 metrics.acc。

讲解由定义可分解为

Jazz 例子：$0.9567\times 0.7596=0.7267$，与 acc 一致。observable_acc 只在结果文件里，论文没有报告。这个分解说明部署可以从两条路影响准确率：让传播更常被看到（DetRate），或让看到时更容易判对。

5.2 传播检测率 DetRate

实现runner.py:971：observed_trials / attempted_trials，字段 metrics.det_rate。

5.3 首个感染传感器的传播跳数、一跳率与估计误差

论文 4.3平均 $h_{\hat{o}}$、一跳率（$h_{\hat{o}}\le 1$ 的比例）、平均 $d(s,\hat{s})$ 都只在至少一个传感器被感染的试验上计算。

实现runner.py:817–840（_detection_distance_metrics）。$h_{\hat{o}}$ 取真实传播树中 $\hat{o}$ 的深度（parallel.py:472）；$d(s,\hat{s})$ 用 nx.shortest_path 在完整图上计算（:453–459），二者不连通时记为 None 并不计入均值。

讲解由于源不是传感器，$h_{\hat{o}}\ge 1$，所以“$h_{\hat{o}}\le 1$”就是“$h_{\hat{o}}=1$”。由 1.5 节事实（b），一跳率也就是“真实源 $={\mathrm{id}}_{\hat{o}}$”的比例。

5.4 真实源抽样范围 $S_{\rho }$

实现runner.py:1245–1269：先求所有比较方法传感器集合的并集，再用 RandomState(source_seed).choice(source_pool, size=300, replace=True) 有放回抽 300 个真实源，所有方法共用这一序列。

讲解为什么要排除并集：如果真实源恰好是某方法的传感器，该方法就无法在 $I_{\sigma }\setminus O$ 中找到它，比较就不公平。代价是预算越大、方法越多，可抽源范围越小，且被排除的往往是高中心性节点（论文 4.6 节：10% 起度排名前十分位节点全部被排除）。所以准确率只在同一张表内可比。

论文 4.2完整方法比较中，再剔除源属于 SDSA 或 GRSL 自身传感器集合的试验：$16,200$ 次中保留 $14,444$ 次，比例 $14,444/16,200=89.2\%$。

5.5 汇总方式：先组合内平均，再组合间等权

论文 4.2、4.3记 $\mathcal{B}$ 为预算集合，$\mathcal{C}$ 为完整图—不完整图组合集合：

每个组合权重相同，与网络大小无关。论文的“总体 62.40%”就是对 54 个组合这样算的。（上式是本文档对论文文字的形式化。）

5.6 部署时间的几何均值与倍率

论文 4.1部署耗时及耗时比采用图组合等权的几何均值汇总。

实现scripts/analyze_ext_e1.py:146–148：np.exp(np.mean(np.log(values)))。

讲解为什么用几何均值：各网络耗时跨越多个数量级（0.0009 秒到 1,480 秒），算术均值会被最大的网络主导；几何均值等价于在对数尺度上取平均。它还有一个好性质：在同一组组合上，

所以“几何均值之比”就是“逐组合倍率的几何均值”。核对：表 2 中 $59.1/0.00813\approx 7,270$，与正文一致；$0.223/0.00813\approx 27.4$，正文写 27.5，差异来自用未四舍五入的值计算。

5.7 Wilcoxon 符号秩检验（论文 4.5，表 6）

论文 4.5双侧配对 Wilcoxon 检验在各策略 27 个匹配组合上、对三个预算取平均后进行，$p$ 值未经多重比较校正。

讲解对每个组合 $c$ 求差 ${\Delta }_c={\mathrm{Acc}}_c^{\text{PR-SD}}-{\mathrm{Acc}}_c^{\text{对照}}$，去掉 ${\Delta }_c=0$ 的组合，把其余 $|{\Delta }_c|$ 从小到大排秩 $R_c$，统计量为

若两方法无差异，正负差应大致对称，$W^{+}$ 接近其期望 $n^{\prime }(n^{\prime }+1)/4$（$n^{\prime }$ 为非零差个数）；偏离越大 $p$ 越小。它只用差的符号和相对大小，不要求差服从正态分布，适合 27 个组合这样的小样本。

实现scripts/analyze_pr_sd_deletion_strategy_split.py:121：scipy.stats.wilcoxon(ours, theirs, zero_method="wilcox")，默认双侧。

5.8 Spearman 相关、Jaccard 相似度与社区覆盖率

论文 4.4、4.8

• Spearman 秩相关：把两组数分别换成秩，再算 Pearson 相关。无并列时有 ${\rho }_s=1-\frac{6{\sum }_i{d}_i^2}{N(N^2-1)}$，$d_i$ 为第 $i$ 对的秩差。它只看单调关系。论文用 $\rho$ 表示传感器比例，所以相关系数应写 ${\rho }_s$ 以免冲突（术语表 4.5 节）。实现：scripts/analyze_pr_sd_community_coverage.py:168，scipy.stats.spearmanr。
• Jaccard 相似度：$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$，两个传感器集合完全相同为 1、无交集为 0。实现：runner.py:733–738。
• 社区覆盖率：在不完整图 $G_{\delta }$ 上用 Louvain 得到社区划分 $\mathcal{P}$，
  $$\mathrm{Cov}(O)=\frac{|\{C\in \mathcal{P}:C\cap O\ne \varnothing \}|}{|\mathcal{P}|}.$$
  实现：networkx.community.louvain_communities(graph, seed=20260918)，graph 为不完整图（analyze_pr_sd_community_coverage.py:62–67, 109–110）。

5.9 累计运行时间（论文 4.9，表 7）

论文 4.9累计时间对 170 个条件的部署、$q_h$ 估计与“传播生成与源推断”记录求和。

讲解表 7 有两个不同的倍率：部署一项是 $41,600/5.84\approx 7,120$；合计是 $45,200/3,540\approx 12.8$。合计倍率小得多，是因为 $q_h$ 标定与源检测两部分两者几乎相同（倍率 1.02）。对应字段在 runner.py:988–995 的 runtime_seconds。

6. 完整方法比较中的基线公式（论文 4.2）

这些方法的原始公式以各自论文为准。下面描述的是本项目代码实际计算的内容，便于理解表 2 的差异。凡涉及原文式号之处，引用前应回到原始 PDF 核对（TODO-VERIFY）。

6.1 SDSA（作者代码）

实现baselines_ext/sdsa_author.py：把作者脚本 SDSA-main/main_source_detection_RDS_code_in_paper.py 中的 SI、observer、hops_test、find_source 原样执行，只替换输入的图、转发概率与传播。

• 部署：第 3 节的 MC 贪心，每轮 800 次模拟分到 16 个工作进程；计时从工作进程启动后开始（与论文 4.2 节“部署计时”一致）。
• 检测：评分形式与 PR-SD 第二阶段相同（find_source 第 344、359 行：hops_test_reserve[1]／[2] 乘 1 - euc_dis/(euc_dis+1)）。
• 差别：作者代码的候选条件 ... and snapshot[i].node_I and ... 对未感染状态 $-1$ 也为真，所以候选是全部非传感器节点，不只是感染节点。论文 4.2 节已写明“检测候选为全部非传感器节点”。每次试验使用独立的不完整图副本。

6.2 GRSL：贪心部署（GS）与推断策略（IS）

实现GS：experiments/generate_gs_sensors.py 调用作者 Java 代码 SI.initNet_SIR_Greedy_lowComplexity（固定提交 a7f6a0f）在 $G_{\delta }$ 上选点。该例程每轮加入一串传感器，可能超出预算，超出部分用由条件名派生的种子随机去掉，使数量等于 $m$。Java 使用 Math.random() 无法设种子，所以每个条件只存一次结果。

IS：baselines_ext/grsl.py，主比较用 variant="code"，不补发送者边，候选为全部非传感器节点（与 Agent.md 第 04 节“GRSL 主配置不补发送者边、不限定感染节点候选”一致）。计算步骤：

1. 取最早感染的 4 个传感器 $O_Y$（并列按 ID）。
2. 时间平移：若这 4 个时间的最小值 $t_{\min }\ge 6$，则 $t\leftarrow t-t_{\min }+2$；$\ge 4$ 则 $+1.5$；$\ge 3$ 则 $+1$；否则不变。
3. 对每个节点 $v$ 与 $o\in O_Y$：$d_{o,v}=d_{G_{\delta }}({\mathrm{id}}_o,v)+1$（到不了记为 $n+1$），以及
   $$\otimes (t_o,d_{o,v})=\max (\frac{t_o}{d_{o,v}},\frac{d_{o,v}}{t_o})\ge 1.$$
4. 得分（越小越好）：
   $$\mathrm{sc}(v)=\left(\sum _{o\in O_Y}{d}_{o,v}{)}^{3/4}\right(\sum _{o\in O_Y}\otimes (t_o,d_{o,v}){)}^{2/3}\cdot rp(v),\hat{s}=\underset{v\notin O}{\mathrm{argmin}}\mathrm{sc}(v).$$
5. $rp(v)=1.02^{|N(v)\cap O_N|}$，$O_N$ 为未被感染的传感器；若 $v$ 是某个相邻已用传感器记录的发送者，再乘 0.9 或 0.95。

讲解直观含义：第一项偏好离这些传感器的发送者都近的节点；第二项 $\otimes$ 在“时间约等于距离”（每步传一跳）时取最小值 1，用来惩罚时间与距离不匹配；$rp$ 惩罚邻居中有未被感染传感器的节点（如果源在那里，这些传感器本应被感染）。它不做传播模拟，所以推断很快。

6.3 MLE-P（Pinto 等的高斯估计）

实现baselines_ext/mle_p.py。为避免与本文的传播规模 $\sigma$ 冲突，下面把边延迟的均值、方差写成 ${\mu }_d,s_d^2$（Pinto 原文记号为 $\mu ,{\sigma }^2$）。

设定。已感染传感器按到达时间排序为 $o_1,\dots ,o_K$（并列按 ID），以 $o_1$ 为参照。对候选 $v$，取 $G_{\delta }$（补入发送者边）上以 $v$ 为根的 BFS 树 $T_v$：

$P(a,b)$ 是树中两点间路径，$|\cdot |$ 为边数。

讲解估计式从哪里来。假设每条边延迟独立、均值 ${\mu }_d$、方差 $s_d^2$，到达时间是路径上延迟之和，近似为高斯，$\mathbf{d}\sim \mathcal{N}({\mathbf{\mu }}_v,{\Lambda }_v)$。对数似然为

展开平方项：$-\frac{1}{2}{\mathbf{d}}^{\mathsf{T}}{\Lambda }^{-1}\mathbf{d}+{\mathbf{\mu }}^{\mathsf{T}}{\Lambda }^{-1}\mathbf{d}-\frac{1}{2}{\mathbf{\mu }}^{\mathsf{T}}{\Lambda }^{-1}\mathbf{\mu }$。把 $\Lambda$ 视作与候选无关时，第一项和常数项可以丢掉，剩下 ${\mathbf{\mu }}^{\mathsf{T}}{\Lambda }^{-1}(\mathbf{d}-\frac{1}{2}\mathbf{\mu })$，就是上面的估计式。代码对每个候选按其 BFS 树计算 ${\Lambda }_v$，但仍使用该估计式。

讲解协方差为什么是共享路径长度。$t_{o_{k+1}}-t_{o_1}$ 与 $t_{o_{i+1}}-t_{o_1}$ 相关，是因为二者从 $o_1$ 出发走过了公共的一段边，公共边的延迟同时出现在两者中。树上的公共长度可以由距离算出：

代码 _score_candidate（第 119–139 行）正是这样算的：先由最近公共祖先深度得树上距离，再取 0.5*(first[:,None]+first[None,:]-tree_dist)。

实现其余细节：

• 延迟标定（estimate_delay_moments，第 39–81 行）：在完整图上做 200 次、40% 规模的 SI 传播，源在全部节点中均匀抽取；每次感染事件记录“接收者时间 − 发送者时间”，取均值和样本方差（ddof=1）。
• 至少需要两个已感染传感器，否则只有一个到达时间、无法比较，不返回估计（Acc 中记错）。
• 候选为已感染的非传感器节点；协方差加 $10^{-9}I$ 防止奇异；有传感器在 $T_v$ 中到达不了的候选不参与比较。

6.4 DISGE（方向诱导树）

实现baselines_ext/mle_p.py:142–155。与 MLE-P 用同样的高斯评分，只是把 BFS 树换成“方向诱导”的有向搜索：进入一个已感染传感器 $u$ 的边，只保留来自其记录发送者 ${\mathrm{id}}_u$ 的那条；其他边双向可走。于是从候选出发的搜索树中，每个已感染传感器都必须经由它真实的发送者到达。若某候选在这一约束下到不了全部已感染传感器，就不对它评分（主配置 disge 不回退到普通 BFS）。

讲解方向信息让树的形状更贴近真实传播路径，从而 $|P(v,o)|$ 更接近真实传播距离。论文表 2 中，DISGE 两种部署配置的总体平均准确率在三个预算下均高于对应的 MLE-P 配置；论文没有把这一差异归因于方向信息，这里的解释只是一种理解角度。

7. 随机种子与可复现性

实现pr_sd/runner.py:75–78, 123–125 与 core/parallel.py:78–89。

逻辑分片。800 次模拟被固定分成 16 个“逻辑分片”，每片的种子由 np.random.SeedSequence([基础种子, 命名空间, 轮次]) 生成（命名空间 1＝MC 部署，2＝$q_h$，3＝试验）。分片数固定为 16，与机器实际进程数无关，所以换一台核数不同的电脑结果仍一样；MC 部署中断后也能从任意轮精确续跑。

8. 公式—代码对照总表

9. 核对结论与需作者留意之处

9.1 本次逐项核对后一致的内容

• 算法 1 的初始化、迭代式、零度节点处理、$L_1$ 收敛判据 $n\epsilon$、迭代上限与异常，均与 NetworkX 3.2.1 _pagerank_scipy 一致；排序并列规则与 runner.py:341 一致。
• 评分式 $q_h/[1+D_t]$ 与代码 $q_h(1-D/(D+1))$ 恒等；$q_1,q_2$ 取自 hop_prior[1]、[2]；未感染位置记 $-1$ 与代码 sim_time 初始值一致。
• $q_h$ 的定义（最小非零深度、分母含未检测模拟、在 $G$ 上标定、源取自 $V\setminus O$）与代码一致。
• 候选为 $I_{\sigma }\setminus O$、发送者边补入逐试验独立副本、临时边仅对非 ${\mathrm{id}}_{\hat{o}}$ 候选加入并在评估后移除、最高分并列取最小 ID，均与代码一致。
• Acc 分母为全部尝试试验、DetRate、条件化的跳数指标、$S_{\rho }$ 的构造与代码一致。
• 删边数取整、传感器数取整、停止阈值取整与代码一致。

9.2 不是错误，但值得作者知道的细节

1. PDND 的带权无放回抽样是逐次重新归一化，单条边最终被删的概率并不严格正比于权重（1.1 节）。论文写“以……为固定抽样权重”是准确的。
2. 术语表 03_术语符号与规范表述库.md 5.4 节仍把时间距离写作 $d(\cdot ,\cdot )$，双语稿已改为 $D_t(v_i)$。是否同步术语表由作者决定。
3. 01_方法与实现核对.md 第 6 节写“无观测的 hop error 在实现中赋值为 $n$”，这是旧 schema；v3 及以后为 None（core/parallel.py:349–352），与 Agent.md 第 04 节一致。
4. 4.5 节第 3、4 条（${\mathrm{id}}_{\hat{o}}$ 必胜条件、一跳率与 $q_1$ 加权的关系）是由公式推出的解读，论文中没有；如要写入讨论，需先由作者确认并用结果数据检验。

10. 自测问题

以下问题用于检验自己能否不看稿件讲清公式。请先自己写答案，再回到对应小节核对。

1. Jazz 网络在 $\delta =0.2$、$\rho =0.10$ 时，$|E_{\delta }|$ 和 $m$ 各是多少？（1.1、1.2 节）
2. 为什么 PageRank 迭代不需要每步重新归一化？用一行式子说明。（2.1 节）
3. $\alpha$ 从 0.85 调到 0.5，PageRank 平均“看”多远的结构？这和论文 4.8 节 Jaccard 结果的变化方向是否一致？（2.2 节）
4. 审稿人问：“PR-SD 声称无需传播模拟，但表 7 中 PR-SD 也有 3,280 秒的检测耗时，怎么解释？”（2.7 节、5.9 节）
5. $q_h$ 的三个关键词：在哪个图上标定？“最小”是对什么取最小？为什么和可以小于 1？（4.2 节）
6. 为什么其他候选要临时连到 ${\mathrm{id}}_{\hat{o}}$，而 ${\mathrm{id}}_{\hat{o}}$ 自己不需要？（4.3 节）
7. 若 $q_1=0.6,q_2=0.3$，${\mathrm{id}}_{\hat{o}}$ 的 $D_t$ 小于多少时，结果一定是它？（4.5 节）
8. 为什么表 4 的一跳率等于“真实源恰为最早感染传感器记录的发送者”的比例？（1.5 节、5.3 节）
9. 为什么部署时间用几何均值而不用算术均值？（5.6 节）
10. Betweenness-SD 对比的 $p=0.063$ 应怎样表述？（5.7 节）

文档源文件：formula_guide/src/guide_source.html；生成脚本：formula_guide/src/build_guide.mjs（KaTeX 预渲染并内嵌字体，再用本机 Edge 导出 PDF）。本文档不属于论文正文，不随稿件自动更新。