阅读辅助工具 · 非论文正文 · 仅帮助理解，不替代原文阅读

Leskovec et al. 2007《Cost-effective Outbreak Detection in Networks》讲解室

这篇 KDD 2007 论文提出的 CELF 算法，是"用蒙特卡洛仿真评估传感器覆盖收益 + 贪心选择"这一整条研究脉络的经典起点——SDSA 的传感器部署模块（SDM）同样采用"模拟评估加贪心选点"的思路。理解这篇论文，能帮你在 Related Work 里把 PR-SD 和这条脉络的关系讲清楚：PR-SD 到底继承了什么、又抛弃了什么。

本页内容已逐页核对原文 PDF（docs/references/pdfs/10_leskovec2007_outbreak_detection.pdf（原编号 06，已重编号为 10）），并据此更正了项目里 [06]_leskovec2007.md 阅读卡中的两处错误（详见页面底部）。但这只是一个帮你更快建立直觉的工具，正文里怎么引用这篇文献、引用到什么程度，仍然需要你自己判断——工具不能替你决定这件事。

STEP 1 · 问题设定

同一个数学问题，两张完全不同的脸

论文用一句话把两个看起来毫不相关的问题绑在了一起：水网里该在哪装传感器才能尽快测到污染？该读哪些博客才能尽快追上正在传播的故事？

共同结构 选一个子集 A ⊆ V 在图 G=(V,E) 上选一批"监测点"（传感器位置 / 要读的博客），预算最多选 B 个（或花费不超过预算 B）。

奖励函数 R(A) 越大越好 R(A) 衡量选了 A 之后，"检测效果"有多好——具体怎么算效果，取决于你关心哪种代价。

目标 max R(A)，s.t. |A|或成本 ≤ B 这是一个组合优化问题，候选点可能有几千到几万个，穷举不可能，NP-hard。

论文定义了三种可以互相替换的目标函数 R(A)（原文 Sec. 2.2）：

DL 检测似然被选中节点检测到的级联/污染事件占全部事件的比例——"抓到了多少次"。

DT 检测时间从事件发生到被某个监测点发现之间的时间差——"多快发现"。

PA 受影响人口被检测之前已经波及的人口/博客数量——"发现前造成了多少损失"。

和相关论文对齐一下SDSA（Cheng 等 2025）把部署目标写成：至少一个传感器被感染时，估计点与源相距不超过 h 跳的概率不低于期望检测概率 χ，即 P(d(ô,s)≤h | O∩G₊≥1)≥χ。它与 DL（检测似然）同样关心能否检测到，但多了距离条件，二者并不相同。这个约束出自 SDSA 论文，不在当前 PR-SD 稿件中。

STEP 2 · 关键性质

子模性：多加一个监测点，收益只会越来越小

这是全篇论文能成立的地基。直觉：你已经装了很多传感器之后，再随便加一个，能带来的新信息大概率比你只装了一两个传感器时加的这个还要少——因为很多区域已经被别的传感器"顺带"覆盖到了。

形式化定义（原文 Theorem 1） 对所有 A ⊆ B ⊆ V 和任意新节点 s：R(A ∪ {s}) − R(A) ≥ R(B ∪ {s}) − R(B)。
翻译成人话：在"集合更小"的时候加一个新点，边际收益一定不小于在"集合更大"的时候加同一个点的边际收益。

为什么重要 正因为 R(A) 满足这条性质（且非负、单调、R(∅)=0），朴素贪心算法才被证明至少能拿到最优解的 (1−1/e) ≈ 63%（原文 Theorem 2，引用自 Nemhauser-Wolsey-Fisher 1978）——这是一个可以写进论文、有理论保证的下界，不是经验估计。

STEP 3 · 核心算法（可交互）

朴素贪心为什么慢？CELF 的"懒惰"技巧省在哪？

下面是一个 5 个候选点、7 个待覆盖故事的玩具例子，预算 B=2。点"下一步"，亲眼看贪心算法怎么选，以及 CELF 在第二轮里怎么"偷懒"少算了 3 次。

候选点与它们各自能覆盖的故事： A={1,2,3,4} · B={2,5} · C={3,6} · D={4,7} · E={5,6,7}

点击"下一步"开始演示。

STEP 4 · 两个真实案例的数字

玩具例子背后，真实规模长这样

以下数字均已逐页核对原文（Sec. 5、Sec. 6），可以直接放进你的 Related Work 作为具体引用依据，不是估算。

案例1：博客网络（Sec. 5）

博客数45,000

帖子数1050万

有效级联数17,589

CELF vs 朴素贪心加速最高700×

案例2：水网络（Sec. 6，来自 Battle of Water Sensor Networks 挑战）

BWSN1（小网络）129 节点

BWSN2（大网络）12,527 节点

NW3（最大网络）21,000 节点

CELF vs 朴素贪心加速10×（10个传感器）

对比基线（原文 Fig. 5(a)、Fig. 11(a) 明确列出的，不是全部方法都试过 Betweenness） 水网络：Degree、Random、按节点人口/水流量/管道直径排序。博客网络：按帖子数、入链数、出链数（全部/仅数据集内）排序、Random。原文全篇未使用 Betweenness 作为基线——这是这次核对时发现并更正的一处旧阅读卡错误。

STEP 5 · 和你的论文的关系

这篇文献在 Related Work 里应该扮演什么角色

可以主张	网络中的传感器/监测点部署问题可以形式化为受预算约束的子模函数最大化问题；朴素贪心有 (1−1/e) 的理论保证；CELF 利用边际收益的单调不增性质，把"每轮都要重算所有候选点收益"变成"大多数候选点可以偷懒不重算"，从而大幅加速——但加速的前提仍然是要用仿真/物理模型去算 R(A)，只是算得次数变少了。
不能主张	不能说 Leskovec et al. 解决了不完整网络下的源归因推断问题（这篇论文完全不涉及缺边网络、不涉及"事后从快照反推源头"，它是纯粹的"部署阶段"论文）；不能把 CELF 的 700× 加速直接等同于 PR-SD 的部署加速——CELF 依然要跑仿真评估 R(A)，只是跑得更聪明；PR-SD 在部署阶段不跑传播模拟，但其离线标定和第二阶段源检测仍然使用模拟。
关键对比句	SDSA 的传感器部署模块用 N_MC=800 次蒙特卡洛传播模拟、逐轮选出 m 个传感器，与 CELF 一样属于"用模拟评估、逐轮选点"的思路；但它按模拟中的近源频数选点，没有 CELF 意义下的子模边际增益，也未必使用懒惰求值。PR-SD 在部署阶段把这一流程替换成不完整图上一次性的 PageRank 排名，不需要对候选点做传播模拟或贪心迭代；这只描述部署阶段，PR-SD 的源检测阶段仍使用模拟。

写作提醒这段对比正好是审稿人最容易问的问题之一："你和经典的子模贪心部署方法比过吗？"——你现在至少可以在 Related Work 里用一句话说清楚二者的关系，而不是含糊带过。