Kempe et al. 2003 · beginner mechanism lab
先别背定理：让网络演示“影响力最大化”
核心问题只有一句：预算有限，只能主动激活少数人，选谁能让最终传播到的人最多？理解这句后，再看贪心、边际增益、live-edge 和子模性。
Kempe 选的是主动发起扩散的种子，PR-SD 选的是被动记录传播的传感器。这篇论文帮助你理解“传播评估型贪心为什么昂贵”，但不能替 PR-SD 证明子模性或近似保证。
同样是“选节点”，任务却完全不同
先切换两条流程。只要这一步分清，后面的概念就不会串线。
亲手运行一次独立级联
圆点是人，箭头是影响方向，数字是一次激活成功的概率。点击节点选择种子，再运行扩散。
7 节点教学网络
同一组种子每次结果可能不同，因为每条边的激活尝试带有随机性。
黄色：初始种子绿色：已激活红色粗圈：本轮新激活绿色边：成功红色虚线：失败
让贪心算法替你逐轮选节点
每一轮都问：在当前已选集合上，再加谁带来的新增期望传播规模最大？
当前贪心状态
先评估所有剩余候选，再把本轮最优者加入集合。预算与上面的选择一致。
已选集合 S∅
候选节点的边际增益 Δ(v|S)
等待先评估
昂贵发生在哪里？大图无法像本页一样枚举所有随机世界。每一轮要测试很多候选，每个候选又要通过多次扩散模拟估计集合效果；选满多个节点时，这个过程会重复很多轮。SDSA-MC 也具有“候选集合 + 重复传播评估 + 逐轮选择”的计算形态，但其传感器部署评分不是 Kempe 的影响函数。
两种扩散模型，只抓住各自的一条规则
Kempe 的理论覆盖 Independent Cascade 与 Linear Threshold。先理解触发方式，不必逐行读证明。
Independent Cascade：每条边只有一次机会
1. 新激活
节点刚变为 active 时，获得向尚未激活邻居尝试传播的资格。
2. 单次尝试
对每个邻居只尝试一次，是否成功由该边的概率决定。
3. 直到停止
如果某一轮没有新增 active 节点，级联结束。
和本项目的关系这里的 IC 是 Kempe 论文中的模型。PR-SD 正式实验使用项目定义的异质 SI 传播实现，二者不能只因为都出现“传播”就写成同一模型。
Linear Threshold：邻居影响累加过线
节点 D 有两个邻居。切换它们是否 active，再移动 D 的阈值。
子模性不是玄学：同一个新节点，越晚加入，新增覆盖通常越少
下面两幅图使用同一张抽签后的 live-edge 图。红色节点表示加入候选 x 后额外触达的节点。
选择例子：
定理边界检查：什么时候能说有近似保证？
点击不同对象。缺少任何关键证明时，都不能把 Kempe 的结论直接搬过去。
5 题读后自检
答完并能口头复述第 3、6 问，才把六问卡视为你真正掌握的材料。
0 / 5
请选择一个答案。