目的边攻击和防御下的相互依存网络相继故障

李稳国，崔宪普，邓曙光，肖卫初

LI Wen-guo,CUI Xian-pu ,DENG Shu-guang, XIAO Wei-chu

湖南城市学院 通信与电子工程学院，湖南 益阳 413000

Department of Communication and Electronic Engineering, Hunan City University, Yiyang 413000, China

1 引言

过去十年，复杂网络的大部分研究集中于单一网络的结构及功能分析；然现实的网络和系统都不是孤立的，它们通过彼此间相互作用组成大型复杂的相互依存网络或系统[1]。由于不同网络节点间相互依存的关系，这些由不同的网络构成的相互依存复杂网络存在巨大的脆弱性；一个或几个网络的部分节点或网络间的相互依存边失效，会导致与之依存的其他网络节点或边失效，继而引发网络间的故障相继，最终导致这些相互依存网络整体失效[2]。

相互依存网络的相继故障的相关研究始于《Nature》的文献[3]，该研究分析基于节点的随机攻击导致的网络间相继故障，为后来相关研究提供了基本的理论框架。此后，相互依存网络的故障渗流及鲁棒性问题逐渐成为了研究热点[1-10]。文献[4]研究了目的攻击节点造成的相互依存网络故障渗流；文献[5]研究了相互依存网络间节点同度相连情况下，网络故障渗流问题；及节点攻击下的相互依存网络的相变[6]、故障渗流[7-10]。然现实情况中，相互依存网络的故障起因和发展并不仅局限于节点的随机攻击及目的攻击，节点因地域范围小易受到保护。网络间的相互依存边，因地域范围跨度广更易受到攻击，然这方面的研究甚少。

本文主要研究相互依存网络在其相互依存边受到目的攻击时的相继故障。提出针对相互依存边的目的攻击和防御策略，构建相互依存网络的故障渗流模型及算法，分析相互依存边受到目的攻击和防御时相互依存网络的相继故障渗流和鲁棒性，并分别以相互依存的随机（Erdos Renyi ER）网络和无标度（Scale-Free SF）网络为实例进行验证。

2 相互依存边的目的攻击和防御策略

参照文献[3,4]，本文中的相互依存网络也由两个单独网络(A、B网络)通过彼此结点连接组成。假设A网络中节点i与B网络中节点j存在一相互依存边，则此相互依存边的边权定义如下：

其中Aiv∈，Bjv∈；ki为A网络节点i的度，kj为B网络节点j的度；α为攻击指数(-∞＜α＜+∞)。

假设A、B网络间共有N条相互依存边，设每次只攻击其中的一条相互依存边，则定义这条相互依存边被攻击的概率为：

联合(1)式有：

假设攻击 (1-p) (0＜p＜1)比例部分相互依存边使其失效，首先可按照公式(3)式对每条没失效的相互依存边循环遍历攻击，直到其中的一条边失效；接着采用同样的方法使得第二条、第三条失效，以此类推直到N(1-p)边失效为止。所以，当α＞0时，权重大的一些相互依存边易受攻击，称为相互依存边的目的攻击；当α＜0时，权重大的一些相互依存边得到保护而受攻击的概率小，故称目的防御；当α=0时，表示对相互依存边的随机攻击，因相互依存边两端的结点是随机选择的，故这种情况与文献[3, 4]对节点随机攻击等效。

3 故障渗流模型及算法描述

本文在文献[3]基础上，构建基于相互依存边目的攻击下的相互依存网络相继故障模型。为简化而不失一般性，本模型中设定为两个网络即A、B网络，这两个网络具有同样的节点数N，A网络的度分布为PA(k)，B网络的度分布为 PB(k)，且一个网络的节点只通过一条相互依存边连接另一个网络的节点，即一一对应。整个相继故障模型如图1所示，图 1.(a)、1.(b)、1.(c)、1.(d)分布代表连锁故障过程中的不同阶段，其相应的算法如下：

（0）初始阶段(图1.(a))：按照公式(3)式，攻击(1-p)比例部分相互依存边使其失效（见 2部分），同时其两端节点也失效。

（1）第一阶段(图 1.(b))：利用广度优先算法（BSF）搜索A网络中的最大连通子图并判断该最大连通子图是否属于极大簇：是，则不属于最大连通子图（极大簇）的节点失效，转第二阶段；否，则意味着整个相互依存网络失效，转结束。

（2）第二阶段(图1.(c))：由于相互依存的关系，B网络中与A网络失效节点相连的节点相继失效。同理，对B网络运用第一阶段方法。

（3）第三阶段(图1.(d))：不断重复第一、二阶段，直到A、B网络不再有新的碎片簇出现，整个网络稳定转结束。

图1 相互依存网络相继故障模型

按照上述模型与算法，相互依存网络故障渗流最终出现两个中之一的结果：相互依存网络整体失效，或整个相互依存网络不再发生故障渗流而稳定。相互依存网络的鲁棒性可以用pc和p∞两个参数来衡量[3]：渗流阈值pc是指相互依存网络整体失效和不失效临界状态时p的临界值；p∞是指整个相互依存相继故障不再发生稳定时，剩余有效的相互依存边p的最终值（剩余相互依存网络的相互依存边占总相互依存边的比例，也可指A或B剩余网络中节点数占总节点的比例）。pc越小（（1-pc）越大）表示需攻击大比例的相互依存边才能破坏整个网络系统，即意味整个相互依存网络的鲁棒性越强。在攻击相同比例的相互依存边p条件下，p∞越大表示整个相互依存网络不再发生故障渗流而稳定时剩下的相互依存网络规模越大，意味着相互依存网络鲁棒性越强。

4 障渗流过程的理论分析

近年来，度分布的生成函数与渗流理论，成为相互依存网络连锁故障的一种很有效的方法与工具[3-11]，下面运用生成函数和渗流理论分析相互依存网络的相继故障及鲁棒性，基本思路是：先把对相互依存边的目的攻击问题转化为对网络节点的随机攻击问题，然后运用文献[3]的理论求解。

设A网络中节点i与B网络中节点j之间存在相互依存边L1，L1依据公式(3)的概率受到目的攻击等价于 A网络中节点 i 依据公式(3)的概率受到目的攻击。本模型的等价的节点目的攻击与文献[4]对节点的目的攻击不同之处在于；文献[4]对节点的目的攻击只包含一个网络的局部信息，而本模型的等价的节点目的攻击包含的全局信息。对于整个网络而言，算法初始阶段按照等式(3)移去(1-p)部分的相互依存边等价于在 A网络中按等式(3)移去(1-p)部分节点。保留被移去节点的所有边时，A网络中剩余的p部分节点的度分布为[12-14]：

其中Ap(k) 为度为k的的节点数，当N→∞时，对等式(4)求导，

Pp(k)这个度分布的生成函数为：

把对节点的目的攻击转化为对节点随机攻击问题，则有：

对等式(10)进行微分，可以得到最终整个网络系统失效的临界条件为：

与文献[3,4,5]一样，等式(11)对于 pc和 xc不能得到精确的数学表达式，只可数值求解，因此以下部分的理论解均指其数值解。

5 仿真实验

依据相互依存网络相继故障模型，以实际最常见的ER和SF分别构成的两个相互依存网络作为实例作进一步分析，理论分析中的ER和SF网络[15]，其初始的度分布及相应的生成函数的表达式见文献[3,4,11,12]；仿真实验中，ER、SF网络的节点个数均为N=104，SF网络均有幂律指数r=3。以下非特别说明，标志点均为仿真值，在图2和图3中，SF网络和ER网络均有平均度＜k＞=4。。

首先分析攻击指数α对相互依存网络相继故障的影响。图2为不同攻击指数下，p∞与p之间关系，从图2可以得知，无论是相互依存的SF网络还是ER网络，攻击指数越大网络表现出的鲁棒性越差。同等条件下，相互依存的SF网络和ER网络比较，SF网络的在攻击指数 α＞0时更脆弱，而攻击指数α＜0时鲁棒性更好。为对比分析基于相互依存边的目的攻击和基于节点的目的攻击[4]，本文设计了关于攻击指数的第二个实验，（见图 3），无论是相互依存的SF网络还是ER网络，基于相互依存边的目的攻击(α＞0)效果好于节点的目的攻击（相应的 pc稍大），且相互依存边的目的防御(α＜0)效果也较好（相应的 pc稍小）。故从攻击指数分析可得：在攻防两端，基于相互依存边的目的攻防效果均好于基于节点的攻防效果。

图2 不同攻击指数下， p∞与p之间关系，其中(a) SF网络，(b)ER网络，实线为相应的理论值。

图3 目的相互依存边的攻击与目的节点的攻击，不同攻击指数下的临界值pc比较。

网络的平均度是网络中所有节点的连接边数的平均，反映一个网络的连接密度，接下来分析相互依存网络的平均度对相继故障的影响。图4为基于相互依存边目的的攻击与基于目的节点的攻击，在不同平均度参数下的临界阈值pc的比较，其中B、D、F、H代表基于节点目的攻击的临界阈值pc，C、E、G、I代表基于相互依存边目的攻击的临界阈值pc。图5为相互依存边目的攻击下不同平均度时，p∞与p之间关系，其中(a) SF网络，(b) ER网络。从图4可知：相互依存的SF网络和ER网络，基于相互依存边的目的攻防效果均好于基于节点的目的攻防效果（α＜0时，相应的pc稍大；α＜0相应的pc稍小）。从图 5可得：平均度越大，相互依存网络的鲁棒性越强。

图4 目的相互依存边的攻击与目的节点的攻击，不同平均度下的临界值pc比较，其中实线ER网络随机攻击的理论值。

图5 不同平均度下，p∞与p之间关系，其中(a) SF网络，(b) ER网络，实线为相应的理论值。

接下来对上述结论作进一步的讨论。相互依存边的目的攻击(α＞0)和目的防御(α＜0)效果均好于节点的目的攻击和防御[4]是因为本文采用了全局最优策略（见（3）式）；而节点的目的攻击和防御针对的是相互依存网络中某一个网络的节点，采用的是局部最优策略（见文献[4]）。都是基于相互依存边的攻防且相同条件下的相互依存的SF和ER网络对比， SF网络的攻防效果好于ER网络；SF网络在演化过程中的择优原则导致出现的少数的核心节点（较小的节点集中了网络大部分的边），是出现这一结果的原因。

6 结论

本文提出了针对相互依存边的目的攻击和防御的全局最优的策略，并以相互依存的 SF网络和相互依存的ER网络为例，分析了在此策略下的相互依存网络的相继故障。理论分析和仿真结果表明，相比于节点的目的攻击和防御，相互依存边的目的攻击和防御下的相互依存网络的攻击和防御效果均较优，并对这些结论进行了合理的分析和解释。这一结论将为设计鲁棒性强的相互依存网络提供理论基础，相互依存网络的拓扑结构对相互依存网络的鲁棒性影响，将是下一步工作的重点。

[1]Yanqing H, Baruch K, Reuven C,et al. Percolation in interdependent and interconnected networks: Abrupt change from second- to first-order transitions[J]. Phys. Rev. E.2011(6) 84: 066116-1-6.

[2]Parshani R, Buldyrev S V, Havlin S. Interdependent networks: reducing the coupling strength leads to change from a first to second order percalation transition[J]. Phys. Rev.Lett. 2010, 4(105) : 048701-1-4.

[3]Buldyrev S V, Parshani R, Paul G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature(London), 2010, 464 (7291): 1025-1028.

[4]Huang X, Gao J, Buldyrev S V, et al. Robustness of interdependent networks under targeted attack[J]. Phys. Rev. E,2011,6(83): 065101-1-4.

[5]Buldyrev S V, Nathaniel S, Gabriel A C. Interdependent networks with identical degrees of mutually dependent nodes[J]. Phys. Rev. E, 2011, 1(83): 016112-1-8.

[6]Parshani R, Buldyrev S V, Havlin S. Interdependent networks: reducing the coupling strength leads to change from a first to second order percolation transition[J]. Phys. Rev.Lett, 2010, 4(105): 048701-1-4.

[7]Dong G, Gao J, Tian L. Percolation of partially interdependent networks under targeted attack[J]. Phys. Rev. E,2012,1(85): 016112-1-7.

[8]Baxter G J, Dorogovtsev S N, Goltsev A V, et al. Avalanche collapse of interdependent networks[J]. Phys. Rev. Lett,2012, 24(109): 248701-1-5

[9]Morris R G, Barthelemy M. Transport on coupled spatial networks[J]. Phys. Rev. Lett., 2012, 12(109: 128703-1-4.

[10]Li W, Bashan A, Buldyrev S V , et al. Cascading failures in interdependent lattice networks: the critical role of the length of dependency links[J]. Phys. Rev. Lett. 2012,22(108): 228702-1-5

[11]Newman M E J. Spread of epidemic disease on networks[J]. Phys. Rev. E, 2002, 1(66): 016128-1-11

[12]Shao J, Buldyrev S V , Cohen B,et al. Fractal boundaries of complex networks[J]. Europhys. Lett. 2008,4(84):04-06.

[13]Shao J, Buldyrev S V, Braunstein L A, Havlin S, et al.Structure of shells in complex networks[J]. Phys. Rev. E,2009, 3(80): 0369105-1-13.

[14]王艳, 李应兴, 勒二辉. 复杂网络健壮性社团挖掘算法[J]. 计算机工程与应用, 2012, 48(31): 36-39.

[15]Dorogovtsev S N, Mends J F F, Samukhin A N. Structure of growth networks with preferential linking [J]. Phy. Rev.Lett. 2000, 5(85), 4633-1-4.