A 预备知识

联系

这一节给了出后面问题定义的模板。

原论文的 MinSCDS 是：

在节点状态未知的情况下，通过 probe 构造包含 root $r$ 的 CDS，目标是最小化 probing cost。

后续可以扩展成：

在节点状态未知的情况下，通过 probe 构造包含 root $r$ 的 2-connected CDS，目标是最小化 probing cost，同时保证一定容错性。

要注意的研究切口

原论文的探测目标是找普通 CDS，最终要求：
$$
N[C]=A_\varphi
$$
或者至少支配 root 所在 active 连通分量，并且：
$$
G[C]\text{ connected}
$$
但是容错版要求更强：
$$
G[C]\text{ 2-connected}
$$
这会导致一个新问题：

原算法每轮只在 2-hop 范围内贪心扩展，是否足以构造 2-connected CDS？

大概率不够。

因为 2 连通需要消除割点，需要考虑叶块、增强路径、备份连接。

这就是可以在后面提出改进算法的地方。

1
2
3
4
5
6
7
8
9
10
11
Preliminaries 中首先定义了普通 CDS 的基本符号。N_G(v) 表示节点 v 在原图 G 中的开邻居，N_G[v] 表示闭邻居；
对于节点集合 C，若 N_G[C]=V，则 C 为支配集。N_G^k[C] 表示距离 C 至多 k 跳的节点集合。
下文若省略下标 G，则默认是在删除已知 inactive 节点后的当前图中讨论邻域；带下标 G 时表示原始图 G。

在 stochastic setting 中，每个节点具有隐藏状态 active/inactive。partial realization φ∈{0,1,*}^{|V|} 表示当前已揭示的部分状态，
其中 1 表示已知 active，0 表示已知 inactive，* 表示未知。
full realization ϕ∈{0,1}^{|V|} 表示所有节点的真实状态。A_φ 表示当前已知 active 节点集合。

本文假设每个节点 v 以概率 p(v)>0 独立地处于 active 状态。算法通过 probe 节点来揭示状态，probing cost 为被 probe 节点数量。
本文采用 full feedback model：若被 probe 节点 v 为 active，则 N[v] 中所有节点状态均被揭示；若 v 为 inactive，则只揭示 v 自身状态。
由于 active 节点诱导子图 G[A_ϕ] 可能不连通，论文假设存在 active root r，并构造包含 root r 的 stochastic CDS，目标是最小化 probing cost。

符号

符号 含义
$N_G(v)$ 原图中 $v$ 的开邻居
$N_G[v]$ 原图中 $v$ 的闭邻居
$N_G[C]$ 集合 $C$ 的闭邻域
$N_G^k[C]$ 距离 $C$ 至多 $k$ 跳的节点集合
$\phi$ partial realization，当前已知状态
$\varphi$ full realization，全部真实状态
$A_\phi$ 当前已知 active 节点集合
$p(v)$ 节点 $v$ active 的概率
$v\succ u$ 探测 $v$ 揭示了 $u$ 的状态
$r$ 已知 active 的根节点
probing cost 主动探测的代价
$H_\varphi$ G[$A_\varphi$] 中含有根节点 $r$ 的连同分量

后面做容错算法，也可以沿用这个结构：

  • 当前已知 active 集合：$A_\phi$
  • 当前骨干集合：$C_\phi$
  • 当前是否 2-connected：判断 $G[C_\phi]$
  • 候选增强路径：在删除 inactive 后的当前图中找
  • 探测策略：根据概率和容错收益选择下一步 probe

B 自适应算法

算法概括

从根节点 r 开始，围绕当前已知 active 的黑色节点，在 2 跳范围内不断选择“最值得探测”的节点，直到当前 active 连通分量已经被支配并连通。

1.四种节点状态

颜色 / 状态 含义
白色 white 状态未知，还没有被揭示
黑色 black 已经被主动 probe，且确定 active
灰色 gray 没有被主动 probe，但被某个 active 节点揭示为 active
removed 已知 inactive，直接从当前图中删除

注意：黑色和灰色都是 active，但作用不同。

黑色节点：

已经被 probe，属于最终输出集合 $S$，可以看作当前 CDS 骨干节点。

灰色节点：

已经知道 active，但还没有被 probe，暂时不是骨干节点；后续如果被选中 probe，就会变黑。

这和你之前看 Wan CDS 里的 BLACK / GRAY 有点像，但这里的含义和随机探测绑定得更强。

2. 集合 $S$

文中说：$S$ 记录已经被探测过的节点。

但是从算法目标看，最终输出的 $S$ 实际上对应算法构造出的 CDS 骨干节点集合。

注意细节：如果某个节点被探测后发现 inactive，它会被从 $V$ 中移除，不会作为有效骨干节点。实际实现时，可以把：

  • probed_set：所有被 probe 的节点；
  • black_set：被 probe 且 active 的节点；
  • removed_set：已知 inactive 的节点；

分开维护。

3. $A_S$

原文说：
$$A_S$$是 $S$ 中的黑色节点，也就是已经探测并确认 active 的节点集合。

可以理解为：
$$
A_S = {v\in S: v \text{ is black}}
$$
算法每轮只在：
$$
N^2(A_S)\setminus S
$$
里选候选节点。

也就是：

距离当前黑色骨干节点至多 2 跳，且还没有被探测过的节点。

4. $NWS(v)$：白色邻域收益

$$
NWS(v)
$$

表示 $N[v]$ 里面白色节点的数量。

也就是：

如果探测 $v$，它可能揭示多少未知节点的信息。

为什么是 $N[v]$？

因为 full feedback model 下，如果 $v$ active，那么 $N[v]$ 中所有节点状态都会被揭示。

所以 $NWS(v)$ 越大，说明探测 $v$ 可能带来的信息收益越大。

5. $NCS(v)$：连接黑色分量收益

$$
NCS(v)
$$

表示与节点 $v$ 相邻的黑色连通分量数量。

比如当前黑色节点诱导出的图有多个连通分量：

1
2
3
4
黑色分量1   黑色分量2
   a         b
    \      /
        v

如果节点 $v$ 和两个黑色分量都相邻，那么：
$$
NCS(v)=2
$$
探测 $v$ 并让它变黑后，它可能把两个黑色分量连接起来。

所以 $NCS(v)$ 衡量的是：

探测 $v$ 对连通性的贡献。

6. $NWS(v)+NCS(v)>1$ why?

算法循环条件是：
$$
\exists v\in N^2(A_S)\setminus S
$$
使得：
$$
NWS(v)+NCS(v)>1
$$
等价于：
$$
NWS(v)+NCS(v)-1>0
$$
这说明探测 $v$ 还有正收益。

为什么要减 1？

可以把：
$$
NWS(v)+NCS(v)-1
$$
理解为探测节点 $v$ 的“有效收益”。

因为探测一个节点本身要付出代价 1，所以收益里面要扣掉一个基本成本。

粗略理解：

  • $NWS(v)$：能揭示多少未知节点；
  • $NCS(v)$：能连接多少黑色分量；
  • $-1$：扣掉自身探测成本或避免重复计数。

所以当它大于 0 时，说明探测还有意义。

7. 实时权重 $w_S(v)$

算法选择：
$$
v’=\arg\min w_S(v)
$$
也就是选择实时权重 最小的节点。

由于 $w_S(v)$ 是“收益”的倒数，所以：

权重越小，代表收益越大，越值得探测。

情况一：$v$ 是灰色节点

灰色节点已经知道是 active。

所以探测它不会失败。

它的权重是：
$$
w_S(v)=\frac{1}{NWS(v)+NCS(v)-1}
$$
这里没有概率 $p(v)$，因为它已经确定 active 了。

如果灰色节点能揭示很多白色节点，或者能连接多个黑色分量，那么分母大，权重小，优先级高。

情况二：$v$ 是白色节点

白色节点状态未知。

它的权重是：
$$
w_S(v)=\frac{1}{1-p(v)+p(v)(NWS(v)-1)}
$$
这里引入了节点 active 概率 $p(v)$。

为什么？

因为探测白色节点有两种结果：

如果 $v$ inactive

概率：
$$
1-p(v)
$$
探测后只能知道 $v$ 自己 inactive，相当于只排除一个未知节点。

如果 $v$ active

概率：
$$
p(v)
$$
那么它会揭示 $N[v]$ 中更多白色节点。

所以分母：
$$
1-p(v)+p(v)(NWS(v)-1)
$$
可以理解成某种“期望收益”。

活跃概率越高、白色邻居越多，分母越大，权重越小，越值得探测。

8. Lemma 1

Lemma 1 证明：
$$
w_S(v)\leq 1
$$
也就是说，只要一个节点的实时权重有定义，它的权重不会超过 1。

这个引理本身不是算法思想的重点，但它在后续近似比分析里会用到。

证明分三种情况：

情况 1：$v$ 是灰色

因为 $w_S(v)$ 有定义，所以：
$$
NWS(v)+NCS(v)-1>0
$$
所以分母至少是 1，于是：
$$
w_S(v)\leq 1
$$

情况 2：$v$ 是白色，且 $NWS(v)\geq 2$

此时：
$$
1-p(v)+p(v)(NWS(v)-1)
\geq
1-p(v)+p(v)
=1
$$
所以：
$$
w_S(v)\leq 1
$$

情况 3：$v$ 是白色，且 $NWS(v)=1$

这种情况其实不可能发生在 $w_S(v)$ 有定义的前提下。

因为白色节点没有黑色邻居，所以：
$$
NCS(v)=0
$$
于是：
$$
NWS(v)+NCS(v)=1
$$
与：
$$
NWS(v)+NCS(v)\geq 2
$$
矛盾。

所以该情况排除。

概括

Algorithm 1 从已知 active 的根节点出发，在当前黑色节点 2 跳范围内，根据节点能够揭示未知节点和连接黑色分量的能力，结合节点活跃概率，贪心选择实时权重最小的节点进行探测，直到没有节点能够带来正收益为止。

对容错的启发

原算法的收益主要来自两部分：
$$
NWS(v)
$$
表示信息揭示收益；
$$
NCS(v)
$$
表示普通连通性收益。

但是如果做容错版，比如 2-connected CDS，那么只考虑 $NCS(v)$ 可能不够。

因为普通连通只需要把黑色分量连起来，而 2 连通还要消除割点、连接叶块、增加备用路径。

所以后面可以引入新的收益项，例如：
$$
NBS(v)
$$
可以理解为 Node Biconnectivity Score，表示节点 $v$ 对减少割点或合并叶块的贡献。

或者路径版本：
$$
Score(P)=
\frac{
\text{FaultToleranceGain}(P)\cdot Pr(P)
}{
\text{ExpectedProbeCost}(P)
}
$$
其中：
$$
Pr(P)=\prod_{v\in P}p(v)
$$
也就是说，可以把原论文的：
$$
NWS(v)+NCS(v)-1
$$
扩展为：
$$
NWS(v)+NCS(v)+FTS(v)-1
$$
其中 $FTS(v)$ 表示容错增强收益。

当然这只是初步想法，后面要慢慢设计得合理。

3 项

第一：
$$
NWS(v)
$$
表示信息收益，也就是能揭示多少白色未知节点。

第二：
$$
NCS(v)
$$
表示连通收益，也就是能连接多少黑色连通分量。

第三：
$$
w_S(v)
$$
是实时权重，算法每轮选权重最小的节点，本质上是选“单位探测代价下最有价值”的节点。

后面做容错算法时，可以沿着这个思路：

对于容错 CDS，除了信息收益和普通连通收益之外，还应该增加什么“容错收益”？