李一刚，王向东

（沈阳工业大学 信息科学与工程学院，辽宁 沈阳110870）

基于连边补偿的无标度网络修复策略研究

李一刚，王向东

（沈阳工业大学 信息科学与工程学院，辽宁 沈阳110870）

针对无标度网络中节点不可修复的情况，本文提出了一种连边补偿的修复策略，能够在只针对少量节点修复的情况下，很好的恢复网络中存活节点的连通性。通过仿真实验，验证这种修复策略，只对被攻击节点的前百分之二十的节点进行修复就可以使得网络中存活节点的百分之八十的节点连通，当修复个数达到一定值时可使存活节点全部连通。

复杂网路；无标度网络；攻击策略；修复策略；最大连通图

随着复杂网络的研究和发展，到了今天，复杂网络几乎随处可见。比如：internet网络[1]，电力系统网络[2]，交通网络[3]，军事网络[4]，自然网络[5]，社会关系网络[6]，生物网络[7]等。这些网络与我们的生活息息相关，因此用复杂网络对这些网络的特性进行研究变得十分有必要。

现实中的网络一般不会是完全随机或者完全规则的网络，大多都是无标度网络，即大多数的节点只有少量的连接度，而少数节点拥有大量的连接度。由于这种无标度网络的这种无标度特性，使得其对于随机的攻击有一定的抗毁性，但是对于蓄意有针对性的攻击十分脆弱[8]。国内外对无标度网络的修复策略上已经取得了一定的进展。文献[9]指出，池丽平等人最早提出了复杂网络在遭到攻击之后的修复策略研究[10]，建立了一种节点修复模型，分析了在不同攻击下的修复效果。文献[11-15]针对不同领域，将不同领域中的网络抽象为复杂网络，并用了类似的修复策略进行修复。这种修复策略是在被攻击节点有修复可能的前提下，将修复人员及资源抽象为网络的修复因子，并且按照一定的策略分配，得出每个节点被修复的概率，从而按照这种概率对网络进行修复。其中的分配策略大致可分为平均分配策略和按照度进行重点分配的策略，并且得到了不同的修复效果。

以上所介绍的国内外研究的修复策略，都是针对网络节点可以修复的情况。然而在现实中，很多情况是无法及时对故障节点进行修复的，比如：攻击强度大，使得被攻击节点被摧毁；资源不冗余，无法调配多余的资源对故障节点进行修复；节点的修复需要较长的修复时间周期等。在诸如此类的情况下，如果无法及时的恢复网络的连通性或功能，将会造成极大的影响和危害。所以，研究被攻击节点无法被修复的情况下的修复策略是十分有意义的。因此，本文研究的是针对无标度网络，在蓄意攻击下，节点无法被修复时，恢复网络连通性的修复策略。

1 修复策略

1.1 无标度网络模型1.1.1 初始网络

整个网络的初始网络由n个初始节点构成。任意两个节点之间，按照0.5的概率连接，最后构成一个随机的初始网络。

1.1.2 演化过程

在由n个节点构成的初始网络的基础上，网络每演化一次，即向网络中增加一个新的节点。这个节点与网络中原有的节点新生成m条连接边。当新节点选择与原网络的节点相连接时，服从一定的择优原则。本文中的择优原则是按照节点的度来决定节点被选中的概率，如式（1）。最后演化为一个节点数为N的无标度网络。

其中，P（i）为第 i个节点被选中的概率；k（i）为网络中第i个节点的度；K为网络中所有节点度之和。

1.2 攻击策略和修复策略

1.2.1 攻击策略

本文中对网络进行的攻击为，一次性打击批量的节点。根据网络中所有节点的度，对所有的网络节点进行重要度排序，即认为度值越高，节点越重要。之后对网络中最重要的一批节点进行攻击。被攻击的节点将删除其在网络中的所有连接边，并且不可被还原修复。是一种即时的，高强度的，蓄意的攻击。

1.2.2 修复策略

由于本文中被攻击的节点是不可修复的，所以本文提出了一种在剩余完好的节点中进行连边补偿的修复办法。本文的修复策略具体如下：

1）攻击对象为演化完成之后的无标度网络，共有N个节点；

2）对这N个节点进行按度值大小降序排列，得到（N1，N2，N3...NN）；

3）对度值最高的前 w 个节点（N1，N2...Nw）进行攻击，即删除其所有连边，并且不可修复。这里的不可修复指的是这w个节点被删除所有连接边之后，不可以再被连接；

5）再对下一个被攻击节点N2按照上述修复策略进行修复，一直修复到Nx，共修复x个。

2 仿真研究

文中以无标度网络为研究对象，对已有无标度网络进行一次蓄意、批量的节点攻击，利用对被攻击节点的相邻节点进行连边补偿的修复策略。

初始网络是由20个节点按照0.5的概率两两相连构成的网络。演化过程中，每演化一步网络中加入一个新节点，在原网络中择优选择节点建立m=2条连边。演化最后形成N=100个节点的无标度网络。

对这个演化后的网络进行一次蓄意的批量节点的攻击，其中，攻击节点的数目为w=10，20，30个分别进行10次仿真。并从第一个被攻击的节点到最后一个，依次按照修复策略进行修复。用最大连通图L来评价网络的连通性。

其中，L为最大连通图比值，Lmax为网络中最大连通子网络的节点个数，N为整个网络的节点个数。针对每一个w，进行十次仿真，对仿真结果数据取平均值，得到修复效果图。

图1、图 2、图 3分别为 w=10、20、30时的修复效果图。其中横轴为针对被攻击节点的修复个数，纵轴为最大连通图比值，即修复效果。

由于被攻击节点不可修复，因此根据w的赋值不同，网络的连通性即最大连通图的最大值也不同。比如，w=10时，对于N=100，修复后网络的最大连通图值为0.9，w=20时，最大值为0.8，W=30时最大值为0.7。分析可知：w=10时，只对前3个被攻击节点修复就能使连通率达到0.85以上；w=20时，针对前5个被攻击节点进行修复就能使连通率达到0.7以上；w=30时，针对前8个被攻击节点进行修复就能使连通率达到0.6以上。因此在这种一次性批量攻击下，使用这种修复策略，只针对少量被攻击节点进行修复就能使网络恢复较好的连通性。为了分析本文的修复策略的适用性，本文针对N=200和N=500的无标度网络也进行了仿真分析，并且分别根据十次仿真结果的平均值得到了修复效果图。其中，对于N=200的网络，取攻击节点个数w=30；对于N=500的网络，取攻击节点个数w=50。修复效果图如图4，5所示。

图1 w=10时的修复效果图

图2 w=20时的修复效果图

图3 W=30时的修复效果图

图4 N=200，w=30时的修复效果图

图5 N=500，w=50时的修复效果图

分析上述结果，可知本文这种修复策略，在被攻击节点无法修复时，能够较好的保证网络的连通性

3 结 论

文中对被攻击节点无法被修复的情况下，提出了一种新的连边补偿的修复策略，并针对一次性蓄意批量的节点攻击进行的仿真分析。结果证明，在本文中的修复策略下，攻击发生后，只对被攻击节点的前百分之二十的节点进行修复就可以使得网络百分之八十的节点连通，而当修复节点数量达到一定值时，可以保证存活节点全部连通。并且对于小规模无标度网络和大规模的无标度网络，该修复策略都有较好的修复效果。

在现实中，有些网络的节点修复困难或者成本高无法及时修复的情况下，这种修复策略对于及时的恢复网络连通性具有一定的意义；在理论上，就目前复杂网络的修复策略研究大多是对故障节点直接修复的情况而言，这种采用建立新的连边的修复策略可以说是一种新的思路。

[1]CHEN Duan-bing，LU Lin-yuan，SHANG Ming-Sheng，et al.Identifying influential nodes in complex networks[J].2012，Fuel and Energy Abstract，391（4）:1777-1787.

[2]Fenu G，Pau PL.Evaluating complex network indices for vulnerability analysis of a territorial power grid[J].Journal of Ambient Intelligence&Humanized Computing，2015，6（3）:297-306.

[3]Chen S，Huang W，Cattani C，et al.Traffic dynamics on complex networks:A Survey[J]，Mathematical Problemsin Engineering，2012，2012 （1024-123X）:256-267.

[4]Yang H W.Complex networks and review of research in military field [J].Chinese Journal of Systems Science，2013，21（1）:84-87.

[5]Shekatkar SM，Ambika G.Complex networks with scale-free nature and hierarchical modularity[J].European Physical Journal B，2015，88（9）:1-7

[6]Wang Z，Xia CY，Meloni S，et al.Impact of social punishment on cooperative behavior in complex networks [J].Scientific Reports，2013，3 （10）:3055-3055.

[7]Yeh，Trai-Ming，Chuang，et al，Multiobjective identification of controlling areas in neuronal networks[J].IEEE/ACM Transactions on Computational Biology&Bioinformatics，2013，10（3）:708-720.

[8]Nie T，Guo Z，Zhao K，et al.New attack strategies for complex networks [J].Physica A Statistical Mechanics&Its Applications，2015，424:248-253.

[9]胡斌，黎放，多种攻击策略下无标度网络修复策略[J].系统工程与电子技术，2010，32（1）:86-89.

[10]池丽平，杨纯斌，蔡勖，Stability of random networks under evolution of attack and repair[J].Chinese Physics Letters，2006，23（1）:263-266.

[11]刘中华，胡兵，吴荣华.基于修复策略的舰艇编队复杂网络系统可靠性研究 [J].计算机科学，2012，39（6A）：139-141.

[12]狄鹏，黎放，胡斌，网络中心战模型修复策略研究[C]//Proceedings of International Conference on Broadcast Technology&Multimedia Communication，2010.

[13]王甲生，吴晓平，陈泽茂，等.修复策略下典型拓扑结构复杂网络抗毁性研究 [J].海 军 工 程 大学 学 报，2015，27（4）：75-79.

[14]蒋勇，赵作鹏.多属性加权模糊贝叶斯的复杂网络故障自修复技术[J].计算机应用研究，2015，32（8）:2378-2381.

[15]王正武，周振宇，胡静.基于节点修复效果的故障路网修复策略[J].长沙理工大学学报自然科学版，2014，11（4）:25-31.

A repair strategy for scale-free network based on the link compensation method

LI Yi-gang，WANG Xiang-dong
（School of Information Science and Engineering，Shenyang University of Technology，Shenyang 110870，China）

To repair the scale-free networks in cases that the attacked nodes couldn't be repaired，in this paper we propose a repair strategy base on the link compensation method.Under this strategy，we compensate a preferential link to the nodes which were linked to the attacked nodes instead of repairing the attacked nodes directly.By simulation，we show that this kind of repair strategy could make 80%of the survival nodes be connected by using the strategy on only 20%of the attacked nodes.And when the quantity of the nodes with the repair strategy reaches a big enough value，the survival nodes could be fully connected.

complex networks； scale-free networks； attack strategies； repair strategies； maximum connected graph

TN91

：A

：1674－6236（2017）14-0111-04

2016-05-25稿件编号：201605239

李一刚（1992—），男，朝鲜族，朝鲜人，硕士研究生。研究方向：复杂网络。