基于連邊補償的無標度網絡修復策略研究

李一剛，王向東

（沈陽工業大學 信息科學與工程學院，遼寧 沈陽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—），男，朝鮮族，朝鮮人，碩士研究生。研究方向：復雜網絡。