网络连通性与攻击模拟研究

### 网络连通性与攻击模拟研究 #### 1. 网络连通性与兰伯特W函数 在网络研究中，随着 $\overline{\beta} \beta_k$ 的增加，会出现一种特殊的情况。可以证明，此时会趋近于 $S_{\alpha} \to \frac{\alpha}{\alpha + \beta} \left[1 - W\left(\frac{\beta}{\alpha} e^{-\frac{\beta}{\alpha}}\right)\right]$ （图3.12中的水平虚线），这里的 $W$ 是兰伯特W函数，也被称为乘积对数函数。这一函数在描述网络连通性的渐近行为时起到了关键作用，它帮助我们理解网络在不同参数变化下的极限状态。 #### 2. 对抗性网络 网络之间的相互依赖关系研究使研究人员意识到还存在其他类型的相互作用，其中与相互依赖密切相关的是对抗性相互作用。 ##### 2.1 对抗性相互作用的概念 在对抗性相互作用中，一个节点正常运行意味着其对抗节点（例如在另一个网络中）不能正常运行。这可能是因为两个节点在竞争某种有限资源。这种对抗性网络的概念后来被扩展到动态网络中的竞争研究，在那里观察到了高度复杂的现象。 ##### 2.2 基本模型 在最基本的对抗性网络模型中，构建了两个完全相互作用的网络，如图3.2(a)所示。一个节点 $i$ 属于网络 $A$ 的巨分量，需要满足两个条件：一是在网络 $A$ 的巨分量中有至少一个邻居 $j \in N_i(A)$；二是在网络 $B$ 的巨分量中没有邻居 $j \in N_i(B)$。同理，节点 $i$ 属于网络 $B$ 的巨分量也有类似条件。 可以使用消息传递算法来找到渗流稳态。每个节点 $i$ 向其相邻节点 $j$ 发送消息，从节点 $i$ 发送到网络 $A$（或 $B$）中节点 $j$ 的消息 $\overrightarrow{y_{i \to j}}^{A(B)}$ 表示沿着网络 $A$（或 $B$）中的链接 $(i, j)$ 从 $j$ 到 $i$ 到达一个在网络 $A$（或 $B$）中活跃节点的概率。节点 $i$ 在网络 $A$（或 $B$）中活跃的概率 $S_i^{A(B)}$ 取决于网络 $A$ 和 $B$ 中邻居 $k$ 发送给节点 $i$ 的消息 $\overrightarrow{y_{k \to i}}^{A(B)}$，具体公式为： \[ S_i^A = 1 - \prod_{k \in N_i(A)} \left(1 - \overrightarrow{y_{k \to i}}^A\right) \prod_{k \in N_i(B)} \left(1 - \overrightarrow{y_{k \to i}}^B\right) \] \[ S_i^B = 1 - \prod_{k \in N_i(B)} \left(1 - \overrightarrow{y_{k \to i}}^B\right) \prod_{k \in N_i(A)} \left(1 - \overrightarrow{y_{k \to i}}^A\right) \] 在局部树状网络中，消息 $\overrightarrow{y_{i \to j}}^{A(B)}$ 是以下迭代方程的不动点解： \[ \overrightarrow{y_{i \to j}}^A = 1 - \prod_{k \in N_i(A) \setminus j} \left(1 - \overrightarrow{y_{k \to i}}^{A(n - 1)}\right) \prod_{k \in N_i(B)} \left(1 - \overrightarrow{y_{k \to i}}^{B(n - 1)}\right) \] \[ \overrightarrow{y_{i \to j}}^B = 1 - \prod_{k \in N_i(B) \setminus j} \left(1 - \overrightarrow{y_{k \to i}}^{B(n - 1)}\right) \prod_{k \in N_i(A)} \left(1 - \overrightarrow{y_{k \to i}}^{A(n - 1)}\right) \] 为了找到这些消息，通常从给定的初始条件开始更新变量 $\overrightarrow{y_{i \to j}}^{A(B), n}$，直到找到迭代的不动点。在不动点处，消息满足以下关系： \[ \overrightarrow{y_{i \to j}}^A = 1 - \prod_{k \in N_i(A) \setminus j} \left(1 - \overrightarrow{y_{k \to i}}^A\right) \prod_{k \in N_i(B)} \left(1 - \overrightarrow{y_{k \to i}}^B\right) \] \[ \overrightarrow{y_{i \to j}}^B = 1 - \prod_{k \in N_i(B) \setminus j} \left(1 - \overrightarrow{y_{k \to i}}^B\right) \prod_{k \in N_i(A)} \left(1 - \overrightarrow{y_{k \to i}}^A\right) \] 如果对具有度分布 $p_k^A$ 和 $p_k^B$ 的网络集合平均上述方程，我们可以得到关于 $S^{A(B)} = \langle S_i^{A(B)} \rangle$ 和 $S'^{A(B)} = \langle \overrightarrow{y_{k \to i}}^{A(B)} \rangle$ 的方程，其中 $S^{A(B)}$ 是在网络 $A$（或 $B$）的渗流簇中找到一个节点的概率，$S'^{A(B)}$ 是沿着一条链接到达网络 $A$（或 $B$）的渗流簇中一个节点的概率。具体方程为： \[ S^A = \left[1 - G_0^A\left(1 - S'^A\right)\right] \left(1 - G_0^B\left(S'^B\right)\right) \] \[ S^B = \left[1 - G_0^B\left(1 - S'^B\right)\right] \left(1 - G_0^A\left(S'^A\right)\right) \] 这里 $G_0^{A(B)}(z)$ 和 $G_1^{A(B)}(z)$ 分别是网络 $A$ 和 $B$ 的生成函数，定义为： \[ G_0^{A(B)}(z) = \sum_{k} p_k^{A(B)} z^k \] \[ G_1^{A(B)}(z) = \sum_{k} k p_k^{A(B)} z^{k - 1} \] 并且 $S'^{A(B)}$ 在局部树状网络中满足以下递归方程： \[ S'^A = \left[1 - G_1^A\left(1 - S'^A\right)\right] \left(1 - G_0^B\left(S'^B\right)\right) = f^A\left(S'^A, S'^B\right) \] \[ S'^B = \left[1 - G_1^B\left(1 - S'^B\right)\right] \left(1 - G_0^A\left(S'^A\right)\right) = f^B\left(S'^B, S'^A\right) \] ##### 2.3 对抗性泊松网络的数值模拟 为了具体研究对抗性网络，我们分析两个平均度分别为 $\overline{k}_A = z_A$ 和 $\overline{k}_B = z_B$ 的对抗性泊松网络。对于泊松网络，有 $G_0(z) = G_1(z) = e^{\overline{k}(z - 1)}$，所以 $S'^A = S^A$，$S'^B = S^B$。递归方程变为： \[ S^A = \left(1 - e^{-z_A S^A}\right) \left(1 - e^{-z_B S^B}\right) \] \[ S^B = \left(1 - e^{-z_B S^B}\right) \left(1 - e^{-z_A S^A}\right) \] 我们可以刻画两个对抗性泊松网络的渗流相图（图3.13）。临界线由 $z_A = 1$，$z_B = 1$ 以及 $z_B = \frac{z_A}{\ln(z_A) / (1 - 1/z_A)}$ 或 $z_A = \frac{z_B}{\ln(z_B) / (1 - 1/z_B)}$ 给出。特别地，在 $z_A > 1$ 且 $z_B = \frac{z_A}{\ln(z_A) / (1 - 1/z_A)}$ 以及 $z_B > 1$ 且 $z_A = \frac{z_B}{\ln(z_B) / (1 - 1/z_B)}$ 的线上观察到一阶相变（图3.13中的实心红线），其他黑线虚线表示二阶相变的临界线。 需要注意的是，在这种情况下，两个网络都渗流的解 $S'^A > 0$，$S'^B > 0$ 总是不稳定的，这意味着在每次渗流过程的实现中，只有一个网络会渗流。为了证明相图区域III中渗流解的双稳态，我们对 $z_B = 1.5$ 和不同的 $z_A$ 值递归求解方程（3.36）。从 $z_A = 4$ 开始，我们递归求解方程，得到 $S'^A(z_A = 4) = 0$，$S'^B(z_A = 4) = 0$。然后稍微降低 $z_A$，并从初始条件 $S'^A = S'^A(z_A = 4) + \epsilon$，$S'^B = S'^B(z_A = 4) + \epsilon$ 开始再次递归求解方程（$\epsilon > 0$ 是为了避免得到平凡解 $S'^A = 0$，$S'^B = 0$）。通过这个过程，我们发现如果先降低 $z_A$ 然后再升高它，相图区域III中的解会显示出一个滞后环，如图3.14(a)和(b)所示。不同拓扑结构的两个对抗性无标度网络的渗流问题的滞后环如图3.14(c)和(d)所示。 #### 3. 部分相互依赖网络的有针对性攻击 为了研究有针对性攻击下的级联故障，我们采用一种通用技术，即将有针对性攻击问题映射为随机攻击问题。 ##### 3.1 节点失效概率分配 为每个节点分配一个值 $\alpha W(k_i)$，它表示具有 $k_i$ 条链接的节点 $i$ 通过有针对性攻击变得不活跃的概率。我们关注以下函数族： \[ \alp