先给结论：

Claim 1 是把算法探测次数 转化为 所有节点的总 charge。
Claim 2 是把这些 charge 和最优策略 $O$ 联系起来，证明每个最优节点 $v$ 的闭邻域里，charge 总量不会太大。

1. Claim 2 要证明什么？

Claim 2 的结论是：

$$
\sum_{u\in N_G[v]}E[cw(u)]
\leq
\frac{1}{p(v)}H(\Delta-1)+1+\frac{1}{\delta}
$$

其中：

  • $v\in O$：$v$ 是最优策略 probe 的节点；
  • $N_G[v]$：节点 $v$ 在原图中的闭邻域，包括 $v$ 自己和它的邻居；
  • $cw(u)$：节点 $u$ 收到的 charge；
  • $p(v)$：节点 $v$ active 的概率；
  • $\delta$：全图节点最小 active 概率；
  • $\Delta$：图最大度；
  • $H(\Delta-1)$：调和数。

这句话翻译后就是：

对最优策略中的任意一个节点 $v$，算法在 $v$ 的闭邻域里产生的总 charge 是有上界的，最多大约是
$$
\frac{1}{p(v)}H(\Delta-1)+1+\frac{1}{\delta}
$$

2. Claim 2 为什么重要？

因为 Claim 1 已经告诉我们：

$$
E[|S|]=\sum_{u\in V}E[cw(u)]
$$

也就是：

算法期望 probe 次数 = 所有节点收到的期望 charge 总和。

所以现在要证明算法不比最优差太多，就需要上界：

$$
\sum_{u\in V}E[cw(u)]
$$

但是直接对所有节点 $u$ 分析很难。

于是作者转而按最优策略 $O$ 来分组。

因为最优策略 $O$ 最终需要覆盖 / 揭示 root 所在 active 连通分量相关的节点，所以相关节点可以被 $O$ 中节点的闭邻域覆盖。

于是作者想证明：

每个 $v\in O$ 的闭邻域 $N_G[v]$ 里 charge 不会太多。
然后对所有 $v\in O$ 求和，就能控制总 charge。

这就是 Claim 2 的作用。

3. 为什么看 $N_G[v]$？

因为在 full feedback model 下，如果 probe 一个 active 节点 $v$，会揭示：

$$
N_G[v]
$$

中的节点状态。

所以对于最优策略中的节点 $v$，它的闭邻域天然是一个“信息揭示范围”。

另外，CDS 的支配关系也是基于闭邻域：

$$
N_G[C]
$$

所以用 $N_G[v]$ 作为分析单位很自然。

可以理解为：

最优策略中的每个节点 $v$ 负责它闭邻域里那些节点的 charge。

4. Claim 2 的证明开头：给 $N_G[v]$ 排序

固定一个：

$$
v\in O
$$

令：

$$
N_G[v]={u_1,u_2,\ldots,u_t}
$$

这里的顺序不是编号顺序，而是：

按照这些节点被 charge 的时间排序。

也就是说：

  • $u_1$：最早被 charge；
  • $u_2$：第二个被 charge；
  • …
  • $u_t$：最晚被 charge。

由于 $v$ 的闭邻域最多包含自己加上 $\Delta$ 个邻居，所以：

$$
t\leq \Delta+1
$$

5. 两个关键位置：$l_1$ 和 $l_2$

Claim 2 里面定义了两个位置。

5.1 $l_1$：第一个 active 节点出现的位置

$$
u_{l_1}
$$

表示在 $N_G[v]$ 中，第一个被揭示为 active 的节点。

也就是说：
$$
u_1,u_2,\ldots,u_{l_1-1}
$$
可能都不是 active，直到 $u_{l_1}$ 第一次出现 active。

由 Lemma 3 / Corollary 4 可以得到：
$$
E[l_1]\leq \frac{1}{\delta}
$$
这说明：

平均来看，在 $v$ 的闭邻域中，等到第一个 active 节点出现，不会超过 $\frac{1}{\delta}$ 个位置。 或者说 探测的次数 不会超过 $\frac{1}{\delta}$

这就是 Claim 2 里最后那个：

$$
\frac{1}{\delta}
$$

的来源。

5.2 $l_2$：节点 $v$ 自己的位置

论文设：

$$
u_{l_2}=v
$$

也就是 $v$ 自己在这个 charge 顺序中的位置。

因为前面假设 $O$ 中所有节点都是 active，所以 $v$ 一定 active。

所以第一个 active 节点出现的位置不会晚于 $v$ 自己：

$$
l_1\leq l_2
$$

论文为了简化，只讨论典型情况：

$$
l_1<l_2
$$

也就是在 $v$ 自己被揭示之前，它的闭邻域中已经有别的 active 节点先出现了。

6. Claim 2 的核心想法

Claim 2 想估计：

$$
\sum_{i=1}^{t}E[cw(u_i)]
$$

作者把它分成两部分：

$$
\sum_{i=1}^{t}E[cw(u_i)]=\sum_{i=1}^{l_1}E[cw(u_i)]+\sum_{i=l_1+1}^{t}E[cw(u_i)]
$$

也就是：

  1. 第一个 active 节点出现之前及当时的 charge；
  2. 第一个 active 节点出现之后的 charge。

7. 第一部分：$1$ 到 $l_1$

前面有结论：
$$
cw(u)\leq 1
$$
所以前 $l_1$ 个节点，每个最多收到 1 的 charge。

因此：

$$
\sum_{i=1}^{l_1}E[cw(u_i)]
\leq l_1
$$

再对 $l_1$ 取期望：

$$
E[l_1]\leq \frac{1}{\delta}
$$

所以第一部分贡献最多：

$$
\frac{1}{\delta}
$$

这就是 Claim 2 里的第一项。

8. 第二部分：$l_1+1$ 到 $t$

这部分是 Claim 2 的难点，也是调和数出现的地方。

先看一个关键事实：

当 $u_{l_1}$ 被揭示为 active 后，节点 $v$ 会成为算法的候选节点。

why？

因为：
$$
u_{l_1}\in N_G[v]
$$
所以 $u_{l_1}$ 和 $v$ 距离最多 1 跳。

而 $u_{l_1}$ 被揭示为 active，说明它要么自己被 probe，要么它的 active 邻居被 probe。

不管哪种情况，$u_{l_1}$ 距离当前黑色节点集合 $A_S$ 至多 1 跳。

那么 $v$ 距离 $A_S$ 至多 2 跳。

所以：
$$
v\in N^2(A_S)
$$
也就是 $v$ 成为候选节点。

9. 为什么 $v$ 成为候选节点后很有用？

Algorithm 1 每轮选择权重最小的候选节点：
$$
v’=\arg\min w_S(v)
$$
既然 $v$ 是候选节点，那么算法实际选中的节点权重一定不超过 $v$ 的权重：
$$
w_S(v’)\leq w_S(v)
$$
而某个节点 $u_i$ 收到的 charge，正是由当轮被选节点的实时权重决定的。

所以：

在 $u_{l_1}$ 被揭示之后，后续任何被 charge 的节点 $u_i$，它收到的 charge 都可以用 $w_S(v)$ 来上界。

这就是 Claim 2 的核心技巧。

它不是直接分析算法到底选了谁，而是说：

算法选的一定不比候选节点 $v$ 差，所以用 $v$ 的权重作为上界。

10. 为什么要分成 $v$ 被揭示前和揭示后？

因为 $v$ 在被揭示前后颜色不同，权重公式不同。

阶段一：$u_{l_1}$ 之后，$v$ 被揭示之前

这时 $v$ 还是白色节点。

白色节点权重是：

$$
w_S(v)=
\frac{1}
{1-p(v)+p(v)(NWS(v)-1)}
$$

考虑这个阶段里某个被 charge 的节点 $u_i$。

在 $u_i$ 被揭示之前，$N_G[v]$ 中从 $u_i$ 到 $u_t$ 这些节点还没被 charge / 揭示，所以 $v$ 的闭邻域里至少还剩：

$$
t-i+1
$$

个白色节点。

因此：

$$
NWS(v)\geq t-i+1
$$

于是：

$$
NWS(v)-1\geq t-i
$$

代入白色权重公式：

$$
w_S(v)
\leq
\frac{1}{1-p(v)+p(v)(t-i)}
$$

进一步放松为：

$$
w_S(v)
\leq
\frac{1}{p(v)(t-i)}

\frac{1}{p(v)}\cdot\frac{1}{t-i}
$$

所以这一阶段中：

$$
cw(u_i)\leq
\frac{1}{p(v)}\cdot\frac{1}{t-i}
$$

阶段二：$v$ 被揭示之后

因为 $v\in O$，且假设 $O$ 中节点都是 active，所以 $v$ 被揭示后是 active。

但它还没有被主动 probe，所以会变成灰色。

灰色节点权重是：
$$
w_S(v)=
\frac{1}
{NWS(v)+NCS(v)-1}
$$
类似地，后续还剩多少未处理节点，就能给 $w_S(v)$ 一个倒数形式上界：

$$
w_S(v)\leq \frac{1}{t-i}
$$

由于：

$$
p(v)\leq 1
$$

所以：

$$
\frac{1}{t-i}
\leq
\frac{1}{p(v)}\cdot\frac{1}{t-i}
$$

为了统一两段估计，最后都用：

$$
\frac{1}{p(v)}\cdot\frac{1}{t-i}
$$

来上界。

11. 为什么最后一个节点 $u_t$ 单独处理？

因为当 $i=t$ 时：

$$
t-i=0
$$

公式：

$$
\frac{1}{t-i}
$$

没法用了。

所以作者单独用：

$$
cw(u_t)\leq 1
$$

这是由前面的公式 (10) 得到的。

所以最后加了一个：

$$
+1
$$

这就是 Claim 2 里的 $+1$。

12. 为什么出现调和数？

第二部分的估计最后变成：

$$
\sum_{i=l_1+1}^{t-1}
\frac{1}{p(v)}\cdot\frac{1}{t-i}
+1
$$

把：

$$
\frac{1}{p(v)}
$$

提出来：

$$
\frac{1}{p(v)}
\sum_{i=l_1+1}^{t-1}
\frac{1}{t-i}
+1
$$

令：

$$
k=t-i
$$

当 $i=l_1+1$ 时：

$$
k=t-l_1-1
$$

当 $i=t-1$ 时：

$$
k=1
$$

所以求和变成：

$$
1+\frac12+\cdots+\frac{1}{t-l_1-1}
$$

也就是：

$$
H(t-l_1-1)
$$

因为：

$$
t\leq \Delta+1
$$

所以：

$$
H(t-l_1-1)\leq H(\Delta-1)
$$

于是第二部分得到：

$$
\frac{1}{p(v)}H(\Delta-1)+1
$$

13. 合并两部分

第一部分：

$$
\frac{1}{\delta}
$$

第二部分：

$$
\frac{1}{p(v)}H(\Delta-1)+1
$$

所以：

$$
\sum_{u\in N_G[v]}E[cw(u)]
\leq
\frac{1}{\delta}
+
\frac{1}{p(v)}H(\Delta-1)
+
1
$$

这就是 Claim 2。

14. 一句话总结 Claim 2

Claim 2 对每个最优节点 $v\in O$ 的闭邻域进行 charge 上界分析：
第一个 active 节点出现前的 charge 用 $1/\delta$ 控制；
第一个 active 节点出现后，$v$ 成为算法候选节点，因此算法后续选择的节点权重不超过 $w_S(v)$，由此形成调和级数 $H(\Delta-1)$；
最后一个节点用 $cw(u)\leq 1$ 控制，于是得到闭邻域总 charge 的上界。