先选在哪里记录，
再推断从哪里开始。

本讲解依据2026年10月9日当前双语主稿第三节，以及当前 pr_sd/runner.py、core/parallel.py 的执行过程。它是作者学习与核对材料，不是论文正文修订。所有手算数字、七节点排名和八节点评分案例都是教学示例，不是论文实验结果。

推荐阅读顺序：先读第1–5部分建立概念，再读第6–11部分理解执行，最后读第12–16部分学习复杂度。HTML中的交互演示可以帮助核对计算；文档中的完整步骤可独立阅读。

1. 先用一句话理解 PR-SD

PR-SD先回答“在哪些节点安放记录传播的传感器”，再回答“利用已有感染信息和传感器记录，哪个节点最可能是起点”。

可以把网络想成一张人员联系图。传播发生前，我们只能选择一部分人作为记录员。传播发生后，这些记录员报告“我什么时候第一次收到信息、是谁传给我的”。算法结合感染节点集合和可获得的关系图，逐个假设不同的人是最初传播者，模拟一遍传播，比较模拟记录与实际记录的吻合程度。

第一阶段是选记录员；第二阶段是依据记录推断起点。两个阶段处理的问题不同，不能用“选出的节点就是估计源”理解 PR-SD。

感染节点集合也是检测输入。当前方法并不是仅靠几个传感器的时间戳就获得所有感染节点；实验通过传播生成该集合。实际使用时，获取这一集合也需要相应的观测条件。

2. 图、集合与符号：先把每个字母读懂

“|集合|”表示元素个数；“∩”表示交集；“A\B”表示属于A而不属于B；“⌈x⌉”表示向上取整；“⌊x⌋”表示向下取整。

教学例子：n=101、ρ=0.05，则ρn=5.05，m=6。人数必须是整数，当前定义使用向上取整。如果完整图有100条边、δ=0.20，就移除20条边，不完整图仍保留所有101个节点。

传播源从非传感器节点中抽取，即 s∈V\O。论文实验中的预算使这个集合非空。排序算法本身可以选出全部节点，但那时本实验所定义的非传感器源抽样就没有可用节点。

3. 四张“信息账单”：哪里使用完整图，哪里使用不完整图

当前实验在完整图上生成传播，是因为需要一个可控的真实过程。算法检测时不会因此自动得到完整图所有缺失边：它以 Gδ 为基础，仅补入被传感器记录直接揭示的发送者边，并按候选规则暂时加入一条连接。

qₕ的完整图标定是当前实验条件。实际部署若无法取得完整图，需要相应的标定来源；本讲解忠实解释现有做法，不替它设计新的标定算法。

“无需传播模拟”只描述第一阶段。离线标定和第二阶段检测仍使用传播模拟。

4. SI传播和观测是怎样产生的

SI是“易感—感染”模型。尚未收到信息的节点是易感节点；收到信息后成为感染节点，并保持感染状态。

当前异质SI实现给每个节点固定一个 pᵢ。在某一时间步，当前感染节点 i 遍历自己的邻居：如果邻居 j 尚未感染，就生成一个0到1之间的随机数；当该数小于 pᵢ 时，j 被感染。不同节点的 pᵢ 可以不同。

新感染节点从下一时间步开始转发。在当前时间步内先标记感染状态，可以避免同一节点被不同邻居重复感染和重复计数。

感染节点在后续时间步继续尝试。某条边本轮没有成功传播，不意味着以后永远无法成功。因此感染时间并不等于图上的最短路径长度。

异质SI模拟（基础教学伪代码）
输入：图H、起点u、节点转发概率p、目标比例β、时间步上限T
1. 把所有节点设为未感染，首次感染时间设为-1。
2. 把u设为感染，时间为0，传播树深度为0。
3. 当前感染节点列表 ← [u]；累计感染数 ← 1。
4. 每个时间步依次执行：
   a. 新感染节点列表 ← 空。
   b. 遍历当前感染节点i及其邻居j。
   c. 若j未感染且随机数 < p[i]：
      标记j感染；时间[j] ← 当前时间步；
      发送者[j] ← i；深度[j] ← 深度[i]+1；
      将j加入新感染列表，累计感染数加1。
   d. 累计感染数达到⌈βn⌉时，结束本次传播。
   e. 若还未结束，把新感染节点加入后续可传播的节点列表。
5. 达到目标规模或时间步上限后返回感染状态、时间、发送者及深度。

标定与检测可能使用不同目标规模。当前实验中 qₕ 标定的目标比例为40%，真实观测及候选模拟使用10%；这些参数对应不同工作的停止点，不是两个不同的“源检测算法”。

Iσ保留截至停止时曾感染的累计节点。方法章节以SI为主；IC、SIR扩展的具体规则在论文实验部分介绍，其中SIR恢复节点仍保留在累计记录中。

5. 第一阶段：为什么 PageRank 能用来选传感器

5.1 先理解“重要节点的邻居也重要”

度数只数一个节点有多少邻居。PageRank还考虑这些邻居获得了多少分数，并让每个邻居把自己的分数按其度数分出去。

例如，节点A有一个得分0.30、度数为3的邻居B，B向A贡献0.10；另一个邻居C得分0.10、度数为2，C向A贡献0.05。α=0.85时，来自这两个邻居的加权贡献是0.85×(0.10+0.05)=0.1275，再加均匀重启份额。

这使排名利用递归的结构信息。PR-SD用它选择监测位置，并通过实验评价所得准确率和部署时间。PageRank本身没有直接优化本文的源检测准确率；排名高不代表在每个网络、预算和传播中都能得到最佳传感器集合。

5.2 随机游走解释

想象一个人在网络上不断移动。他以概率α沿当前节点的一条边走到邻居，以概率1−α跳到任意节点。移动很久后，在某节点停留的长期比例就是该节点的PageRank分数。

重启让游走能够跳到别的区域。对于零度节点，没有邻居可以走，当前处理把它的质量均匀分给全体节点。

5.3 公式里的转置是什么意思

r_new = α Pᵀ r + ((1−α)/n) 1
最终：r = α Pᵀ r + ((1−α)/n) 1，且 Σᵢr(vᵢ)=1

P的第i行描述“从i往哪里走”。r是列向量；Pᵀr把所有节点流入某节点的贡献加起来。转置是为了让“出发概率表”作用到列形式的分数上，与改变网络边的方向不是一回事。

在无权图上，非孤立节点 i 向每个邻居贡献 r(i)/degree(i)。P只是一种数学写法，实际稀疏实现不必构造一个 n×n 的密集矩阵，更不必把每个孤立节点的均匀行逐项存储。

5.4 实际怎么计算

先把所有节点分数设为1/n，然后反复使用上面的式子。若本轮与上一轮分数差的绝对值之和小于 nε，就认为收敛。

当前论文使用 α=0.85、ε=10⁻⁶、迭代上限100。ε、α和100不是三个相同用途的参数：α控制游走，ε控制停止精度，上限控制最多付出多少迭代工作。

收敛后按分数降序排列；完全同分时按整数节点标识升序。取前m个节点，就是传感器集合。

5.5 预算改变时能复用什么

固定不完整图、α与并列处理规则后，排序不变。小预算取较短的名单，大预算取较长的名单，因此传感器集合嵌套。

这来自固定排序的前缀选择机制。它不是PageRank自动求解传感器预算问题，也不需要给每个预算重新模拟传播。

能复用的是排名。不同预算产生不同传感器集合，qₕ通常仍需针对各集合重新标定；不能把“排名复用”理解成“所有准备工作都复用”。

6. 论文算法1：14行逐行读

算法1只描述传感器部署，第二阶段没有被这一伪代码省略成“无需计算”。下面完整保留14步的含义。

第一阶段完整伪代码
输入：Gδ、ρ、α、ε、T_max
输出：Oₘ
1. n ← |V|；m ← ⌈ρn⌉
2. 根据Gδ定义稀疏转移P，零度节点质量均匀分配
3. r ← 长度n、每项1/n的向量
4. for t = 1,…,T_max:
5.     r_new ← αPᵀr + ((1−α)/n)1
6.     if Σᵢ|r_new[i]−r[i]| < nε:
7.         r ← r_new；break
8.     end if
9.     r ← r_new
10. end for
11. 若未收敛，抛出收敛错误
12. ranked ← 按(-r[i], i)升序排序所有节点
13. Oₘ ← ranked的前m项
14. return Oₘ

7. 检测准备：qₕ到底怎么估计

7.1 一次标定模拟记录什么

固定传感器集合O，在完整图G上从V\O均匀抽取源，独立模拟传播。每次感染一个节点时，记录“是谁感染它的”，并把其传播树深度设为发送者深度加1。

对本次所有已感染传感器，找出最小的非零深度 h_min。如果没有传感器感染，本次不增加任何h桶的计数，但这次模拟仍然计入总模拟次数N_q。

qₕ = “最小非零传感器传播深度等于h”的模拟次数 / N_q

7.2 一个可以手算的例子

仅作为教学演示，假设做10次模拟：6次最小深度为1，3次为2，1次没有任何传感器感染。于是 q₁=0.6，q₂=0.3，二者之和为0.9。

不能把它们改成6/9和3/9，因为那会把“没有观测”的模拟从分母排除，变成另一种条件化口径。

qₕ并不一定只有h=1、2；标定数组可记录更多深度。当前检测评分只使用其中q₁和q₂。

7.3 三种“距离”要区分

时间最早不一定树深度最小：一个传感器可以经过三次很快的成功传播先被感染，另一个经过一次长时间等待的直接传播后被感染。

感染时间记录“何时”，传播树深度记录“经过了几次实际感染”，图最短路径记录“图中理论上最短能走几条边”。三者不能混写。

7.4 qₕ标定完整伪代码

输入：完整图G、传感器集合O、p、标定目标比例β_q、N_q、T_sim
输出：q数组
counts[h] ← 0
repeat N_q times:
    s ← 从V\O均匀抽取一个源
    在G上从s运行一次传播，记录每个感染节点的树深度
    depths ← 所有感染传感器的正深度
    if depths非空:
        h_min ← min(depths)
        counts[h_min] ← counts[h_min]+1
q[h] ← counts[h]/N_q
return q

当前参数的800次来自沿用作者发布代码中的Nr设置；不是PageRank要求的次数。HTML中的10次计数示例只是便于手算的示意。

8. 第二阶段：用候选模拟逐个排查

8.1 输入是什么

检测需要 Gδ、Iσ、O、已感染传感器的首次时间和发送者、qₕ，以及候选模拟使用的pᵢ、σ和时间步上限。

真实源s用于实验核对，不作为检测输入。真实传播树深度用于标定或统计，不直接作为检测时每个候选的已知真实距离。

8.2 没有传感器感染怎么办

先计算O₊。若为空，PR-SD不返回源估计。实验准确率把这类试验计为错误，不能只对有观测的试验计算主准确率。

在当前工作函数中，图副本在检查失败分支前已生成。因此“没有候选模拟”不意味着函数没有任何准备开销。

8.3 候选集合怎么确定

C=Iσ\O。候选必须感染过且不是传感器。感染条件缩小了需要模拟的范围；排除传感器与真实源从非传感器中抽取的实验设定一致。

例子：Iσ={0,1,3,4,7}，O={4,7}，则C={0,1,3}。需要检查三个候选，不是八个节点全部检查，也不是只检查传感器邻居。

8.4 哪些边能补回

对每个感染传感器o，它记录的发送者idₒ揭示了实际发生过的传播连接。将(o,idₒ)加入本次试验的Gδ副本。

已有边无需重复建立；缺失边被该条记录恢复。这只恢复局部已观察到的关系，不恢复整个完整图。

原图保持不变。下一次试验重新取副本，避免上一次传播揭示的边泄漏到下一次。

8.5 最早传感器的发送者为什么特殊

选出最早感染的传感器ô，令u=id_ô。它是直接把信息传给最早传感器的节点，因此作为特殊候选使用q₁。

u只是一个有额外发送者线索的候选，不必然是真实源。它也可能在此前已从别人那里接到信息。

在当前合法单源SI观测下，u已感染且不是传感器：如果它本身是传感器，它的感染时间会早于ô，与“ô最早”矛盾。这个关系解释了代码先评估u，再评估其余感染非传感器候选的做法。

8.6 其他候选为什么临时连接到u

对其他候选v，若(v,u)不存在，就暂时加入这条边，然后从v模拟传播。评估完v后仅删除这条本次新加的边。

这个操作为其他候选到已知发送者提供一条待检验连接，是当前检测规则的一部分。它不是已经观测到的真实边，不能把它画成已恢复的确定关系。

对u自身不加自环；若(v,u)已经存在，不在评估后删除它。传感器记录补入的边持续用于当前试验的所有候选。

8.7 每个候选模拟多少次

当前代码对每个候选运行一次异质SI模拟。节点pᵢ固定，但成功传播仍随机。不同候选得到一组模拟传感器首次时间，再进行评分。

它没有在单次检测内对每个候选重复800次模拟求均值；800次对应qₕ标定及相关蒙特卡洛部署设置。

主工作函数使用试验的随机数流，先生成真实传播，再按候选执行顺序消耗随机数。候选不是各自重新初始化为同一个随机种子。这个细节对严格复现结果有影响。

9. 从时间向量到评分：把公式拆开

9.1 顺序必须一致

假设本次感染的两个传感器按固定顺序是4和7，真实记录为[2,4]。每个候选也必须按[4,7]顺序排列模拟时间。

如果把一边顺序改成[7,4]，比较的就不再是同一传感器。当前实现按节点标识顺序组织感染传感器。

模拟中没有感染的传感器位置写为−1。它仍参与向量距离，没有跳过。

9.2 欧氏距离怎么计算

D_t(v) = √[(t₁−t′₁(v))² + … + (t_k−t′_k(v))²]
k = |O₊| ≤ m

真实[2,4]，模拟[1,3]时，D=√(1²+1²)=√2≈1.4142。模拟[2,4]时D=0。模拟[−1,4]时D=3。

当前比较使用原始首次时间，按实验中的同一时间原点记录；未先把各向量减去自己的最早时间，也没有为候选另行优化未知起始时间。

9.3 评分怎么计算

score(v) =
    q₁ / (1 + D_t(v))，如果v是最早传感器记录的发送者u；
    q₂ / (1 + D_t(v))，对其他候选。

分子是经验权重，分母是时间不匹配的惩罚。加1让D=0时分母不为零，此时分数达到所用权重q。

代码写成 q×(1−D/(D+1))。因为1−D/(D+1)=1/(D+1)，它与论文公式等价。

q₂用于所有其他候选。当前代码不会逐一确认这些候选在真实传播树中是否恰好位于第二跳，也没有为每个候选寻找一个真实h再选qₕ。

9.4 一个完整评分例子

教学例子：八个节点，ρ=25%，O={4,7}，Iσ={0,1,3,4,7}，实际记录[2,4]，最早传感器4的发送者是3。设q₁=0.6、q₂=0.3。

返回节点0。这个例子说明：特殊候选可以有较大权重，但其他候选若时间吻合明显更好，仍可胜出。

这些时间向量是为解释公式而给定的，不是声称本例已经复现了论文某次传播记录。交互工具允许修改向量，直接观察排名变化。

9.5 并列和零权重怎么处理

完全同分时选整数节点标识最小者。当前代码用长度n的分数数组：非候选保持−1，候选得到非负分数，再用argmax返回最小标识的最大分数节点。

若q₁与q₂均为0，合法候选分数都为0，仍按标识破同分。这与“没有传感器感染时不返回估计”是两种不同情况。

10. 第二阶段完整教学伪代码

输入：
    Gδ、Iσ、O、感染传感器的时间t与发送者id、
    经验权重q、节点转发概率p、目标比例σ、时间步上限T_sim
输出：估计源ŝ，或无估计

1. O₊ ← O∩Iσ
2. 若O₊为空：返回“无估计”
3. C ← Iσ\O
4. ô ← 按(首次感染时间, 节点标识)最小的感染传感器
5. u ← id[ô]
6. H ← Gδ的副本
7. 对每个o∈O₊：把记录的边(o,id[o])加入H
8. 按固定节点顺序构造真实时间向量t_obs
9. scores ← 所有节点初始分数−1

10. 先评估u，再按节点标识顺序评估C\{u}：
    a. added ← False
    b. 若v≠u且H中没有(v,u)：
       临时加入(v,u)；added ← True
    c. 将所有模拟状态重置，令候选v在时间0感染
    d. 在H上运行一次异质SI模拟
       固定p、目标规模σ、时间步上限T_sim
    e. 按t_obs相同顺序收集模拟首次时间；
       未感染的传感器时间保持−1
    f. D ← 两个时间向量的欧氏距离
    g. 若v=u：score[v] ← q₁/(1+D)
       否则：score[v] ← q₂/(1+D)
    h. 若added：移除本次临时加入的(v,u)

11. ŝ ← 最大分数节点；完全同分取最小整数标识
12. 返回ŝ

这份伪代码按功能把未检测分支放在图复制前，便于理解。当前工作函数在该分支前已复制图；这不改变检测输出，但复杂度核算保留图复制成本。

这里没有对候选进行并行竞争。当前并行主要分配独立试验或标定模拟批次；一个试验内部候选按顺序执行。

11. 把论文语言映射到当前代码

旧 source_detection/find_source.py 是保留的顺序入口，不能只读它就判断当前结果管线。当前论文方法的执行解释主要对照 runner → core.parallel。

代码仍有observer、prior、noise等历史变量名。observer_mask表示传感器标记，hops_test_reserve表示q数组，G_noise表示不完整图；它们不是新增的方法对象。

论文算法1显式列出迭代，而正式入口把迭代交给NetworkX执行。两者是数学步骤与库调用之间的对应关系，不是正文中又存在一套另行运行的PageRank。

12. 计算复杂度入门：到底在“数”什么

12.1 时间复杂度不是秒数

复杂度描述输入变大时主要工作量如何增长。实际秒数还受硬件、图结构、提前停止、实现细节和进程开销影响。

O(n)表示工作量至多按n的量级增长；O(n log n)常见于通用比较排序；O(n²)表示两重全规模工作。Big-O通常省略固定倍数和低阶项，不提供某次运行的准确秒数。

例如，5n+3n=8n属于O(n)。n²+n在n很大时由n²主导，因此属于O(n²)。

12.2 两个最重要的计数规则

顺序执行的工作量相加。例如“复制图，再排序”，成本是复制成本加排序成本。

循环重复的工作量相乘。例如“每个候选模拟一次”，成本是候选数乘单次模拟成本。

12.3 先缩短符号

后续用 eδ=|Eδ| 表示不完整图边数，e=|E|表示完整图边数。m≤n；感染传感器数k=|O₊|≤m；检测到传播时候选数c≤n−m。

T_PR与T_sim含义不同：前者是排名迭代轮数，后者是一次传播模拟时间步数。N_q是传播模拟的次数，不能与T_sim混为一谈。

本节沿用邻接表/稀疏图表示，并按整数节点与常用字典集合的平均常数时间查询估计基本操作。它是论文的算法工作量分析，不是逐条解释所有Python对象分配和操作系统开销。

13. 第一阶段复杂度怎样逐项得到

13.1 构造图与初始化

遍历节点需要O(n)，遍历边需要O(eδ)，因此准备稀疏转移表示和初始向量需要O(n+eδ)。

无向边会对应两个方向的邻接条目，数量为2eδ。常数2在Big-O中省略。

13.2 一轮PageRank

需要沿邻接关系分配分数，成本O(eδ)；计算每节点重启项、孤立质量处理、向量更新与收敛检查，成本O(n)。

所以一轮为O(n+eδ)，T_PR轮为O(T_PR(n+eδ))。

如果真的采用密集n×n矩阵，一轮可能是O(n²)。当前论文的边数形式依赖稀疏计算：孤立节点的均匀贡献汇总后广播，不把它展开成许多密集行。

13.3 排序与取前缀

通用比较排序n个节点，最坏成本O(n log n)。取前m个节点形成名单，成本O(m)。

完整相加：

部署成本
= O(n+eδ) + O(T_PR(n+eδ)) + O(n log n) + O(m)
= O(T_PR(n+eδ) + n log n)   （T_PR≥1，m≤n）

最后一行是论文公式。它没有把排序成本遗漏，也没有把传播模拟加进部署阶段。

13.4 为什么稀疏图是O(n log n)，稠密图是O(n²)

当迭代轮数在当前参数设置下有界时，可把T_PR作为相对于图规模的固定上限处理。

稀疏图eδ=O(n)，每轮成本是O(n)，与排序O(n log n)相加后由排序主导。

稠密图eδ=Θ(n²)，每轮成本是O(n²)，比排序增长更快，故由图迭代部分主导。

这不是说T_PR在任何可能的参数、精度要求下都绝对不变。若研究迭代次数随规模或参数变化，应保留完整公式。

14. 第二阶段复杂度怎样逐项得到

14.1 准备一张本次试验的工作图

复制不完整图：O(n+eδ)。检查和补入至多m条发送者边：O(m)。扫描感染状态形成候选：O(n)。整理时间向量：O(m)。

这些项合起来可写成O(n+eδ)，因为m≤n。当前实现分数数组初始化、最终argmax也各O(n)，同样可以吸收。

14.2 为什么一轮传播要按n+eδ+m算

补入发送者边后，工作图边数至多eδ+m。另有至多一条临时候选边，固定常数可省略。

一个SI时间步遍历当前感染节点及其邻接边。最坏情况下可涉及全部节点和全部工作图边，所以按O(n+eδ+m)给上界。

一次模拟最多T_sim步，故为O(T_sim(n+eδ+m))。

SI感染节点会在后续时间步继续尝试邻居，不能把整次模拟简单当成“每条边只看一遍”的O(n+eδ)。提前达到目标或感染节点较少时，实际工作量可低于该上界。

14.3 时间向量比较为何是O(m)

向量有k个感染传感器的位置。逐个相减、平方、求和，再开平方，成本O(k)≤O(m)。

图和数组状态重置另需O(n)。一次候选的较展开写法为：

单候选成本
= O(n) + O(T_sim(n+eδ+m)) + O(m) + O(1)

权重选择、一次加边/删边按平均常数时间估计。T_sim≥1时，O(n)与O(m)被模拟上界吸收。

14.4 为什么要乘c

当前每个候选模拟一次，共c个候选，所以把单候选成本乘c。加上一次工作图准备：

给定qₕ，一次检测成本
= O(n+eδ+m+n)
  + O(c[n + T_sim(n+eδ+m) + m])
  + O(n)
= O(n+eδ + c T_sim(n+eδ+m))

这就是论文第二阶段公式。c不是传感器数量m，而是感染非传感器候选数。m主要决定记录数量与补边规模，c决定模拟次数。

当没有传感器感染，定义c=0，没有候选模拟。当前实现仍复制工作图等，因此保留O(n+eδ)的准备项。

如果只讨论某一次已经完成准备的候选循环，可单独报告循环项；论文报告的是一次检测执行，不应漏掉准备。

15. qₕ标定与总成本怎样计算

15.1 标定一回模拟

标定用完整图G，所以一次模拟按O(T_sim(n+e))，不是O(T_sim(n+eδ))。

初始化感染状态和深度是O(n)，扫描传感器找最小正深度是O(m)，在T_sim≥1、m≤n下都可吸收入该上界。

15.2 N_q回模拟

qₕ准备成本
= O(N_q T_sim(n+e))

N_q次是顺序总工作量的计数。并行分配这些模拟可以改变墙钟时间，但不会让整个任务需要的总模拟数减少。

当前源从非传感器节点中抽样，代码通过拒绝传感器节点实现。在预算比例远离1的实验条件下，源抽样的期望尝试次数有界；其严格极端成本不作为上述图遍历公式的主项。

15.3 新部署的一次完整工作

如果传感器集合刚建立，还没有qₕ，则所需三项是：

新部署 + 准备 + 一次源检测
= O(T_PR(n+eδ) + n log n)
  + O(N_q T_sim(n+e))
  + O(n+eδ + c T_sim(n+eδ+m))

如果部署及qₕ已经存在，当前检测只承担第三项。真实传播生成是实验产生输入的过程，单独记为实验成本；不能将它与推断成本混称。

15.4 同一集合复用J次检测

总成本 = 部署一次 + qₕ准备一次 + Σⱼ 第j次检测成本
平均每次 = (部署成本 + 准备成本)/J + 平均检测成本

J越大，部署和标定摊到每次的份额越小。每次传播不同，c和实际模拟时间也可能不同，不必强行假设所有试验成本相同。

跨预算复用PageRank排名，并不允许跨不同传感器集合自动复用同一qₕ。图、节点传播参数、标定模型或传感器集合变化后，原标定的适用条件也要重新核对。

15.5 一个数字代入例子

教学设 n=1,000，eδ=4,000，e=5,000，m=50，c=100，T_PR=30，T_sim=20，N_q=800。

部署量级表达式为30×5,000+1,000×log₂1,000≈159,966。

检测量级表达式为5,000+100×20×5,050=10,105,000。

准备量级表达式为800×20×6,000=96,000,000。

这些只是把复杂度表达式代入得到的“工作量指数”，各项隐藏常数不同，不能当成真实CPU操作数、秒数或可信加速倍率。它们帮助理解c、T_sim和N_q增大时为什么相应项会变大。

16. 空间复杂度：哪些东西同时留在内存

稀疏图需要存节点和邻接关系，空间O(n+eδ)。PageRank分数和临时向量各长度n，仍是O(n)；排序与传感器名单也至多O(n)。

第二阶段保存一个工作图、感染状态、时间数组、候选分数以及时间向量，空间O(n+eδ+m)，因m≤n可化为O(n+eδ)。

候选依次处理，状态重置并复用，不需要为c个候选同时保留c张图。因此时间里乘c，单个执行进程的工作空间不一定也乘c。

qₕ标定使用完整图G，单个进程工作空间O(n+e)。N_q次模拟顺序处理或分批计数，不保存N_q棵完整传播树，因此不会自然变成O(N_q(n+e))空间。

使用W个进程时，各进程可能各持有图和数组，整体内存会随并行数上升。论文给出的工作空间与“整个操作系统、所有输出记录总内存”不是同一个口径；保留全部J次结果还会增加结果存储。

17. 从头到尾的执行清单

1. 准备可获得的不完整图Gδ和预算ρ，确定m。
2. 一次PageRank计算，确定节点排名。
3. 取前m个节点作为传感器，标记O。
4. 在当前实验完整图G上，针对O标定qₕ，保存权重。
5. 获得一次传播的Iσ和已感染传感器的首次时间、发送者记录。
6. 计算O₊；没有观测时不返回源估计。
7. 找到最早传感器及其发送者u，确定C=Iσ\O。
8. 复制Gδ，补入已记录发送者边。
9. 逐候选按规则临时补边，在工作图上模拟一次SI传播。
10. 按相同顺序比较观测和模拟时间，计算D_t。
11. u使用q₁，其余候选使用q₂，计算q/(1+D_t)。
12. 删除每个候选专用的临时边，返回最大分数节点，完全同分按标识。
13. 在实验中用真实源核对准确性，并单独统计部署、标定及试验时间。

这13条把算法工作、检测准备和实验评价放在同一时间线上；不是替代论文算法1的新算法编号。

18. 常见疑问与自测

18.1 为什么不直接返回最早传感器的发送者

发送者可能是中间传播节点。其他候选的时间模拟可能更吻合，所以仍逐候选比较。

18.2 PageRank最高的节点就是源吗

不是。它决定监测位置。源估计由第二阶段根据当次观测计算。

18.3 两个向量完全相同，源就一定正确吗

不一定。不同起点可能产生相似观测；随机模拟也可能偶然吻合。准确率要通过已知真实源的实验评价。

18.4 α增大，准确率一定变高吗

不一定。α改变拓扑排名，不直接等同于提高源检测准确率。论文针对所测网络和条件报告其影响。

18.5 为什么第二阶段还有完整图G出现在文档里

G用于实验观测生成和当前qₕ标定。候选推断工作图以Gδ加局部记录边为基础。对步骤分别读，就不会把检测误读为拥有完整拓扑。

18.6 为什么第二阶段没有写成O(m×模拟成本)

每个候选模拟一次，次数是c；m限制的是传感器记录和补边。c与m是不同集合的大小。

18.7 为什么模拟不是一次BFS

BFS按图距离访问节点，通常每条边处理有限次。当前SI反复进行随机感染尝试，同一感染节点在多个时间步可以再次遍历邻居，因此有T_sim因子。

18.8 16个进程就一定快16倍吗

不会自动如此。进程启动、复制与序列化、调度、负载差异会影响墙钟时间。复杂度中的总工作量不会凭并行消失。

18.9 可以不做qₕ标定吗

当前评分使用q₁和q₂，需要这些权重。去掉标定或改成固定权重属于改变方法，不是此次讲解已经实施的功能。

18.10 三个自测题

题1：n=198、ρ=0.05时m是多少？答案：⌈9.9⌉=10。

题2：O={2,5}、Iσ={0,1,2,4,5}时，O₊与候选C是什么？答案：O₊={2,5}，C={0,1,4}，c=3。

题3：q=0.3，实际时间[2,4]，模拟[2,5]时分数是多少？答案：D=1，score=0.3/(1+1)=0.15。

19. 核对来源与阅读边界

本材料直接依据当前文件，不用历史规格替代现稿。PR-SD第三节的式子、预算规则、算法1及两阶段说明来自当前双语主稿。代码行号是制作时的定位，后续源文件修改可能移动。

• 中文主稿第三节
• 英文主稿第三节
• 正式实验入口 runner.py
• 并行标定与检测实现 parallel.py
• 节点状态 Node
• 参数与取整规则 config.py
• 保留的顺序部署接口 strategies.py

PageRank是既有排名方法；当前发送者与时间匹配评分沿用稿件中注明的SDSA相关机制。本材料没有把这些机制改写为新的算法贡献。

HTML与本Markdown讲解共享正文。HTML的三个演示分别是七节点PageRank、给定时间向量的候选评分、复杂度表达式代入；不会读取或写入冻结实验结果，也不会启动论文实验。