摘要:相依网络鲁棒性研究多集中于满足无反馈条件的一对一依赖, 但现实网络节点往往依赖于多节点构成的依赖群, 即使群内部分节点失效也不会导致依赖节点失效. 针对此现象提出了一种相依网络的条件依赖群逾渗模型, 该模型允许依赖群内节点失效比例不超过容忍度$\gamma $时, 依赖节点仍可正常工作. 通过理论分析给出了基于生成函数方法的模型巨分量方程, 仿真结果表明方程理论解与相依网络模拟逾渗值相吻合, 增大$\gamma $值和依赖群规模可提高相依网络鲁棒性. 本文模型有助于更好地理解现实网络逾渗现象, 对如何增强相依网络鲁棒性有一定指导作用.
关键词: 相依网络/
级联失效/
逾渗/
相变

English Abstract

全文HTML

--> --> -->

现实世界中的许多复杂系统都可以用复杂网络描述, 例如生物神经系统、社交网络、交通系统、互联网等^[1-3]. 随着研究人员对复杂网络认识的逐渐深入, 相关研究成果已成为人们理解现实世界复杂系统的重要工具. 但现实生活中的复杂系统通常并不是孤立的, 往往多个系统之间存在相互依赖关系, 这种依赖性会导致网络鲁棒性的急剧下降. 2003年意大利大停电是典型的相依网络级联失效引起的重大生产事故, 最初电网和通信网中极少的节点失效使意大利接近半数的电力设施瘫痪, 数百万人失去电力供应^[4]. 在单个网络中, 随着初始删除节点比例增大, 网络巨分量(giant component)连续减小, 整个解体过程呈现出二阶相变, 但在多个相依网络, 巨分量减小的过程多为一阶相变, 表明相依网络的鲁棒性远不如单个网络. 近些年来, 相依网络的鲁棒性开始引起研究人员的重视^[3,5-13], 网络鲁棒性研究主要基于经典统计物理的逾渗模型^[14], 该模型能准确描述网络解体的相变过程.
以往关于相依网络鲁棒性的研究主要针对一对一相依节点^[12,15-19], 但在现实情况中, 一个节点往往会依赖于多个节点^[6], 这多个被依赖节点称为该节点的依赖群. 例如一个通信基站会有多个电厂为其供电, 食物链中一种生物会捕食多种生物. 近年来, 已有****对存在依赖群的网络展开了研究. Shao等^[6]提出了一种耦合网络中存在依赖群的模型, 该模型认为只有当某节点依赖群的全部节点失效后该节点才会失效, 这种依赖模式有效改善了相变点. Wang等^[20]研究了网络的群渗流现象, 网络节点的存活取决于其所在超级节点是否连向巨分量, 这种网络模型在一定程度上提高了网络的鲁棒性, 但逾渗类型仍然是一阶相变. Parshani等^[7]研究了单个网络中存在依赖群的情况, 发现随着依赖群规模增大网络会变得更加脆弱, 极少数节点失效会导致整个网络崩溃. Wang等^[9,21]提出了一种单个网络中存在条件依赖群的模型, 认为当某节点依赖的节点失效数量超过一定比例时该节点才失效, 研究发现随着失效比例阈值增大, 一阶相变甚至会变为二阶相变.
本文研究了具有多依赖节点的相依网络的逾渗现象, 提出相依网络的条件依赖群逾渗模型并给出巨分量相变方程. 仿真结果表明, 在确定依赖度分布的情况下, 相依网络逾渗模拟结果与方程数值解相吻合, 并且通过增大失效容忍度$\gamma $或依赖群规模可增强网络鲁棒性. 虽然模型对于任意依赖度分布的相依网络不存在二阶相变, 但本文所述逾渗模型对提高相依网络鲁棒性仍具有一定指导作用.
本文的内容主要包括: 第2部分阐述相依网络的条件依赖群逾渗模型的基本概念; 第3部分通过理论分析给出模型的巨分量相变方程; 第4部分仿真验证理论框架有效性; 第5部分讨论本文研究成果; 第6部分是结论.

传统相依网络逾渗模型多为一对一依赖, 一对一依赖可使网络满足无反馈条件, 便于理论分析^[3], 但严格的一对一依赖在现实网络中通常是不存在的, 一个网络节点可能会依赖于另一个网络的多个节点, 若节点依赖的所有节点中有任意一个节点失效, 按照传统模型的分析方法, 该节点也会失效, 如图1所示.
图 1 具有多依赖关系的相依网络逾渗示意图, 初始攻击导致红色节点失效, 随后发生级联失效过程, 最终相依网络仅有极少数节点存活
Figure1. The model of percolation of interdependent networks with multiple support-dependence relations. The red node fails after the initial attack. Then the cascading failure process leads to a catastrophiccollapse of the interdependent networks. Finally, only a small fraction of nodes survive.

这种严格的多依赖关系会大幅降低相依网络的鲁棒性, 少部分节点失效就会造成相依网络完全崩溃. 但现实中的网络却没有这么脆弱. 通过观察可以发现, 只要依赖群有部分节点存活则依赖节点仍有效, 例如在某产业链中, 存在生产同类型产品的工厂若干, 其中少部分同类工厂倒闭并不会导致有关产业链的瘫痪^[9]. 因此本文提出了一种允许部分相依节点失效的相依网络逾渗模型, 用以描述在部分被依赖节点失效情况下依赖节点仍正常工作的现象, 如图2所示.
图 2 相依网络的条件依赖群逾渗模型 A网络节点随机依赖于B网络的$\tilde k$个节点($\tilde k \geqslant 0$), 反之亦然; A网络的a节点依赖的3个节点有一个失效, 但失效比例未超过容忍度$\gamma = 0.5$, a节点继续工作; B网络的b节点依赖的节点失效比例超过$\gamma = 0.5$, 所以b节点失效
Figure2. The model of percolation in interdependent networks with conditional dependency clusters. Nodes in network A randomly depends on $\tilde k$ ($\tilde k \geqslant 0$) nodes in network B and vice versa. One of the three nodes which node a in network A depends on fails, but the failure proportion does not exceed $\gamma = 0.5$, node a still works. Two of the three nodes which node b in network B depends on fail, the failure proportion exceeds$\gamma = 0.5$, node bfails.

本文提出的相依网络逾渗模型级联失效过程如下.
Step 0: 随机删除A网络$1 - p$比例的节点, 与这些节点相连的边也被移除.
Step 1: A网络中依赖群节点失效比例超过$\gamma $的节点失效, 随后与巨分量失去连接的节点也相继失效.
Step 2: B网络中依赖群节点失效比例超过$\gamma $的节点失效, 随后与巨分量失去连接的节点也相继失效.
Step 3: 循环进行Step 2, Step 3直至相依网络中不再有新的节点失效.
根据生成函数理论^[22], 网络的度分布生成函数为${G_0}(x) = \displaystyle\sum\nolimits_k {P(k){x^k}} $, 余度分布生成函数为${G_1}(x) = \displaystyle\sum\nolimits_k {{{P(k)k{x^{k - 1}}}/{\left\langle k \right\rangle }}} $, 其中$P(k)$表示任取一个节点其度为$k$的概率, $\left\langle k \right\rangle $表示网络的平均度. 随机删除网络$1 - p$比例节点后, 令$f$为随机选择一条边连接的节点通向巨分量的概率, 则$f$满足自恰方程

$f = p\sum\limits_k {\frac{{P(k)k}}{{\left\langle k \right\rangle }}} [1 - {(1 - f)^{k - 1}}] = p\left[ {1 - {G_1}(1 - f)} \right],$

网络巨分量大小${\mu _\infty }$为

${\mu _\infty } = p\sum\limits_k {P(k)[1 - {{(1 - f)}^k}] = p[1 - {G_0}(1 - f)]} .$

对于单个网络, 联立上述两式可解出巨分量的大小. 传统的一对一相依网络求解与单网络相似, 这里直接给出^[23]

$\left\{ \begin{aligned}& \mu _\infty ^{\rm{A}} = p[1 - {G_{{\rm{A}}0}}(1 - {f_{\rm{A}}})][1 - {G_{{\rm{B0}}}}(1 - {f_{\rm{B}}})], \\& \mu _\infty ^{\rm{B}} = p[1 - {G_{{\rm{B0}}}}(1 - {f_{\rm{B}}})][1 - {G_{{\rm{A}}0}}(1 - {f_{\rm{A}}})], \\& {f_{\rm{A}}} = p[1 - {G_{{\rm{A}}1}}(1 - {f_{\rm{A}}})][1 - {G_{{\rm{B0}}}}(1 - {f_{\rm{B}}})], \\& {f_{\rm{B}}} = p[1 - {G_{{\rm{B}}1}}(1 - {f_{\rm{B}}})][1 - {G_{{\rm{A}}0}}(1 - {f_{\rm{A}}})], \end{aligned} \right.$

其中$\mu _\infty ^i$表示$i$网络巨分量, ${f_i}$表示在$i$网络中任取一边通向巨分量的概率.
与一对一相依网络情况不同, 本文提出的模型一个节点可依赖多个节点, 只有当某节点依赖的节点失效比例超过容忍度$\gamma $时, 该节点失效, 令${h_i}({\mu _\infty })$表示在$i$网络中随机选择节点的依赖群失效比例不超过$\gamma $的概率, 则本文模型关于巨分量的方程为

$\left\{ \begin{aligned} & \mu _\infty ^{\rm{A}} = p[1 - {G_{{\rm{A}}0}}(1 - {f_{\rm{A}}})]{h_{\rm{B}}}(\mu _\infty ^{\rm{B}}), \\& \mu _\infty ^{\rm{B}} = p[1 - {G_{{\rm{B}}0}}(1 - {f_{\rm{B}}})]{h_{\rm{A}}}(\mu _\infty ^{\rm{A}}), \\ & {f_{\rm{A}}} = p[1 - {G_{{\rm{A}}1}}(1 - {f_{\rm{A}}})]{h_{\rm{B}}}(\mu _\infty ^{\rm{B}}), \\ & {f_{\rm{B}}} = p[1 - {G_{{\rm{B1}}}}(1 - {f_{\rm{B}}})]{h_{\rm{A}}}(\mu _\infty ^{\rm{A}}), \end{aligned} \right.$

其中

${h_i}(x) = \sum\limits_{\tilde k} {{{\tilde P}_i}(\tilde k)} \sum\limits_{s = 0}^{\left\lfloor {\tilde k\gamma } \right\rfloor } {\left( \begin{gathered} {\tilde k} \\ s \\ \end{gathered} \right)} {(1 - x)^s}{x^{\tilde k - s}},$

式中$\left\lfloor {\tilde k\gamma } \right\rfloor $为小于等于$\tilde k\gamma $的最大整数, ${\tilde P_i}(\tilde k)$表示在网络$i$中任取一个节点, 并且该节点依赖于另一个网络$\tilde k$个节点的概率. 通过分析可知, 若取$\tilde P(1) = $1, $\gamma = 0$, 则本文模型与经典一对一相依网络模型^[3]一致; 若$\gamma \to 1$($\gamma \ne 1$)时, 意味着只要依赖群内有1个节点存活, 依赖节点仍可以正常工作, 此时(5)式可以改写为${h_i}(x) = \sum\nolimits_{\tilde k} {\tilde P}_i(\tilde k)$$\left[ 1 - {(1 - x)}^{\tilde k} \right] $, 把上式代入(4)式可以得到与文献[6]相同的结果.
理论上${f_{\rm{A}}}$,${f_{_{\rm{B}}}}$可分别表示为${f_{\rm{A}}} = {\varPsi_1}(p,{f_{\rm{B}}})$,${f_{\rm{B}}} = {\varPsi _1}(p,{f_{\rm{A}}})$, 如果相依网络存在一阶相变点, 则有

$\frac{{\partial {\varPsi _1}(p_{\rm{c}}^{\rm{I}},f_{\rm{B}}^{\rm{I}})}}{{\partial f_{\rm{B}}^{\rm{I}}}} \cdot \frac{{\partial {\varPsi _2}(p_{\rm{c}}^{\rm{I}},f_{\rm{A}}^{\rm{I}})}}{{\partial f_{\rm{A}}^{\rm{I}}}} = 1,$

即${f_{\rm{A}}} = {\varPsi _1}(p_{\rm{c}}^{\rm{I}},{f_{\rm{B}}})$与${f_{\rm{B}}} = {\varPsi _2}(p_{\rm{c}}^{\rm{I}},{f_{\rm{A}}})$在点$(f_{\rm{A}}^{\rm{I}},f_{\rm{B}}^{\rm{I}})$处相切. 因上式求解较为复杂, 大部分情况下不存在解析解, 为了方便计算, 本文仅考虑具有相同度分布的相依网络, 即A, B网络同分布, 则(4)式简化为

$\left\{ \begin{aligned} & {\mu _\infty } = p[1 - {G_0}(1 - f)]h({\mu _\infty }), \\& f = p[1 - {G_1}(1 - f)]h({\mu _\infty }). \end{aligned} \right.$

对上式第二个式子两边求$f$的导数,

$p[1 - {G_1}(1 - f)]\frac{{{\rm{d}}h({\mu _\infty })}}{{{\rm{d}}f}} + p\frac{{{\rm{d}}{G_1}(1 - f)}}{{{\rm{d}}f}}h({\mu _\infty }) = 1.$

通常情况下, 在存在相变点${p_{\rm{c}}}$的相依网络中, 上式在$p = {p_{\rm{c}}}$时存在${\mu _\infty } \geqslant 0$的解, 若只考虑二阶相变点, 则$p = p_{\rm{c}}^{{\rm{II}}}$时应有${f^{{\rm{II}}}} = 0$, $\mu _\infty ^{I{\rm{I}}} = 0$, 把两个值代入上式可得

$p_{\rm{c}}^{{\rm{II}}}{G'_1}(1)h(0) = 1.$

对于任意$\tilde P(\tilde k)$分布, 只有当$\gamma = 1$时, $h(0) \ne 0$, 二阶相变点为

$p_{\rm{c}}^{{\rm{II}}} = \frac{1}{{{{G'}_1}(1)}},$

这是单个网络的二阶相变点, $\gamma = 1$意味着两个网络之间不存在相依关系, 逾渗类型转变为单网络普遍存在的二阶相变. 上述关于相变点的理论分析表明, 对于任意依赖度分布, 本文提出的相依网络模型不存在二阶相变点($\gamma = 1$除外).

2

-->

4.1.RR-RR相依网络

随机规则(random regular, RR)网络的度分布生成函数为${G_0}(x) = {x^{\left\langle k \right\rangle }}$, 余度分布生成函数为${G_1}(x) = {x^{\left\langle k \right\rangle - 1}}$. 假设两个RR网络具有相同的分布, 那么将两个生成函数代入(7)式可得方程

$\left\{ \begin{aligned} &{\mu _\infty } = p[1 - {(1 - f)^{\left\langle k \right\rangle }}]h({\mu _\infty }), \\ & f = p[1 - {(1 - f)^{\left\langle k \right\rangle - 1}}]h({\mu _\infty }). \end{aligned} \right.$

对于任意$\tilde P(\tilde k)$分布求解逾渗方程较为复杂, 本文只考虑依赖群规模固定的情况. 图3是不同$\gamma $取值的RR-RR相依网络逾渗的仿真结果.
图 3 不同$\gamma $取值的RR-RR相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$与$p$对应关系; (b) 级联失效迭代次数(number of iterations, NOI)
Figure3. The results of the percolation of RR-RR interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$versus $p$; (b) number of iterations.

2 -->

4.2.ER-ER相依网络

Erd?s-Rényi (ER)网络^[24]的度分布与余度分布生成函数相同, 都为${G_0}(x) = {G_1}(x) = {{\rm{e}}^{ - \left\langle k \right\rangle (1 - x)}}$, 假设两个ER网络具有相同的分布, 那么将两个生成函数代入(7)式可得方程

$\left\{ \begin{aligned} & {\mu _\infty } = p[1 - {{\rm{e}}^{ - \left\langle k \right\rangle {\mu _\infty }}}]h({\mu _\infty }), \\& f = p[1 - {{\rm{e}}^{ - \left\langle k \right\rangle f}}]h({\mu _\infty }). \end{aligned} \right.$

因为ER网络度分布与余度分布生成函数相同, 所以${\mu _\infty } = f$, 则上式可进一步简化为

$f = p[1 - {G_0}(1 - f)]h(f),$

上式即为相同度分布的ER-ER相依网络巨分量方程. 定义$D(f)$如下:

$D(f) = p[1 - {G_0}(1 - f)]h(f) - f,$

随着$p$值发生变化, $D(f)$会与横轴相切, 相切时$p$的取值${p_{\rm{c}}}$为相变点. 图4为同分布ER-ER相依网络相变点数值解, 图5为不同$\gamma $取值的ER-ER相依网络逾渗的仿真结果.
图 4 不同$\gamma $值对应的ER-ER相依网络相变点, 网络平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$
Figure4. Graphical solutions of ER-ER interdependent networks transition for different $\gamma $. The average degree is 6, $\tilde P(10) = 1$.

图 5 不同$\gamma $取值的ER-ER相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$与$p$对应关系; (b) 级联失效迭代次数
Figure5. The results of the percolation of ER-ER interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

图6、图7分别对比了ER-ER相依网络不同${\tilde P_i}(\tilde k)$分布的逾渗结果和不同$\gamma $取值的相变点.
图 6 不同依赖度分布的ER-ER相依网络逾渗, $\tilde P(10) = 1$, $\tilde P(5) = 1$分别用实心和空心标记表示, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$ (a) 巨分量${\mu _\infty }$与$p$对应关系; (b) 级联失效迭代次数
Figure6. The results of the percolation of ER-ER interdependent networks for different dependency degrees, each network has 200000 nodes, average degree is 6. The dependency degrees are $\tilde P(10) = 1$ (solid symbols) and $\tilde P(5) = 1$ (empty symbols). (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

图 7 不同$\gamma $取值的ER-ER相依网络相变点, 空心标记为仿真结果, 实线是理论值
Figure7. The critical point ${p_{\rm{c}}}$ versus $\gamma $ of ER-ER interdependent networks, The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions.

2 -->

4.3.SF-SF相依网络

无标度网络(scale free network, SF)是指服从于$P(k) = c{k^{ - \lambda }}$分布的随机网络, 它的度分布生成函数和余度分布生成函数可以分别近似为^[12]:

${G_0}(x) = \sum\limits_{{k_{\min }}}^{{k_{\max }}} {\left[ {{{\left( {\frac{{{k_{\min }}}}{k}} \right)}^{\lambda - 1}} - {{\left( {\frac{{{k_{\min }}}}{{k + 1}}} \right)}^{\lambda - 1}}} \right]} {x^k},$

${G_1}(x) = {{\sum\limits_{{k_{\min }}}^{{k_{\max }}} {k\left[ {{{\left( {\frac{{{k_{\min }}}}{k}} \right)}^{\lambda - 1}} - {{\left( {\frac{{{k_{\min }}}}{{k + 1}}} \right)}^{\lambda - 1}}} \right]} {x^{k - 1}}}/{\left\langle k \right\rangle }},$

将两个生成函数代入(7)式可求出巨分量. 图8给出了不同$\gamma $取值的SF-SF相依网络逾渗仿真结果.
图 8 不同$\gamma $取值的SF-SF相依网络逾渗, 每个网络节点数$N = 200000$, 平均度$\left\langle k \right\rangle = 6$, $\lambda = 2.7$, $\tilde P(10) = 1$, 空心标记为仿真值, 实线为逾渗方程数值解 (a) 巨分量${\mu _\infty }$与$p$对应关系; (b) 级联失效迭代次数
Figure8. The results of the percolation of SF-SF interdependent networks for different $\gamma $, each network has 200000 nodes, average degree is 6, $\lambda = 2.7$, $\tilde P(10) = 1$. The symbols represent the simulation results, and the solid linesshow the corresponding analytical predictions. (a) The size ofthe giant component ${\mu _\infty }$ versus $p$; (b) number of iterations.

上一节中针对不同的$\gamma $值分别对RR-RR, ER-ER和SF-SF三种相依网络进行了逾渗仿真, 对仿真结果的分析如下.
1) 对于三种相依网络, 随着$\gamma $取值增大网络鲁棒性逐渐提高. $\gamma $值表示对相依节点失效的容忍程度, 较大$\gamma $意味着即使某节点的较多依赖节点失效, 该节点仍正常工作.
2) 通过观察图3, 图5以及图8的仿真结果可以看出, 在本文选取的$\gamma $值范围内, 三种相依网络皆不存在二阶相变, 这与理论分析的结果吻合.
3) 图4给出了不同$\gamma $值ER-ER相依网络的相变点的数值解, 其中$\gamma = 1$时网络的相变点与单个ER网络的相变点相同, 这说明$\gamma = 1$解耦合了两个相依网络, 节点之间不再存在相互依存关系.
4) 图6结果表明在相同$\gamma $值的情况下, 随着依赖群平均规模的增大网络鲁棒性整体呈上升趋势. 根据(5)式可知, 保持$\gamma $值不变, 增大某节点依赖群规模可以使失效组合增多从而降低该节点相依失效的概率.
5) 图7中相变点曲线呈阶梯状, 主要因为(5)式中对$\tilde k\gamma $进行了向下取整操作, 所以在$\gamma $的某取值区间内${p_{\rm{c}}}$值保持不变. 从图中还可以看出, 随着依赖群规模增大, ${p_{\rm{c}}}$呈整体下降趋势, 意味网络的鲁棒性得到提高.
根据本文理论分析与仿真结果可知, 可从两个方面提高多依赖相依网络鲁棒性:
1) 提高失效容忍度$\gamma $, 即增加被依赖节点的相互可替代性, 保证即使某节点的依赖节点只有少量存活, 仍可以支撑该节点的正常运行;
2) 增加依赖节点的数量, 若某节点存在更多的依赖节点, 则在相同$\gamma $值的情况下存活节点组合更多, 从而提高该节点存活的概率.

相依网络的鲁棒性正在逐渐引起人们的重视, 现实网络中节点往往会依赖于多个节点, 按照传统相依网络逾渗理论, 多依赖性通常会降低网络鲁棒性, 但现实网络并未因此变得更脆弱. 为了更好地描述现实网络中的这种现象, 提出了一种相依网络的条件依赖群逾渗模型, 该模型允许在部分被依赖节点失效情况下依赖节点仍正常工作. 本文在逾渗模型的基础上, 利用生成函数理论^[25]给出了上述具有任意度分布模型的巨分量方程, 通过对三种相依网络模拟仿真可看出方程的数值解与模拟值相吻合, 验证了理论的有效性. 虽然理论分析发现对于任意依赖度分布的相依网络模型, 无论$\gamma $取任何值($\gamma = 1$除外)都不存在二阶逾渗相变, 但仿真结果仍表明随着$\gamma $取值增大网络鲁棒性会逐渐提高. 此外, 对比不同依赖度分布的仿真, 在相同$\gamma $值的情况下, 随着依赖节点的增多, 网络鲁棒性也会相应地提升. 本文的研究结果对提高现实世界相依系统鲁棒性具有一定的科学指导意义, 同时也为后续具有多依赖关系的相依网络研究提供了借鉴.