李一剛，王向東

（沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽110870）

基于連邊補(bǔ)償?shù)臒o標(biāo)度網(wǎng)絡(luò)修復(fù)策略研究

李一剛，王向東

（沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽110870）

針對無標(biāo)度網(wǎng)絡(luò)中節(jié)點(diǎn)不可修復(fù)的情況，本文提出了一種連邊補(bǔ)償?shù)男迯?fù)策略，能夠在只針對少量節(jié)點(diǎn)修復(fù)的情況下，很好的恢復(fù)網(wǎng)絡(luò)中存活節(jié)點(diǎn)的連通性。通過仿真實(shí)驗(yàn)，驗(yàn)證這種修復(fù)策略，只對被攻擊節(jié)點(diǎn)的前百分之二十的節(jié)點(diǎn)進(jìn)行修復(fù)就可以使得網(wǎng)絡(luò)中存活節(jié)點(diǎn)的百分之八十的節(jié)點(diǎn)連通，當(dāng)修復(fù)個(gè)數(shù)達(dá)到一定值時(shí)可使存活節(jié)點(diǎn)全部連通。

復(fù)雜網(wǎng)路；無標(biāo)度網(wǎng)絡(luò)；攻擊策略；修復(fù)策略；最大連通圖

隨著復(fù)雜網(wǎng)絡(luò)的研究和發(fā)展，到了今天，復(fù)雜網(wǎng)絡(luò)幾乎隨處可見。比如：internet網(wǎng)絡(luò)[1]，電力系統(tǒng)網(wǎng)絡(luò)[2]，交通網(wǎng)絡(luò)[3]，軍事網(wǎng)絡(luò)[4]，自然網(wǎng)絡(luò)[5]，社會關(guān)系網(wǎng)絡(luò)[6]，生物網(wǎng)絡(luò)[7]等。這些網(wǎng)絡(luò)與我們的生活息息相關(guān)，因此用復(fù)雜網(wǎng)絡(luò)對這些網(wǎng)絡(luò)的特性進(jìn)行研究變得十分有必要。

現(xiàn)實(shí)中的網(wǎng)絡(luò)一般不會是完全隨機(jī)或者完全規(guī)則的網(wǎng)絡(luò)，大多都是無標(biāo)度網(wǎng)絡(luò)，即大多數(shù)的節(jié)點(diǎn)只有少量的連接度，而少數(shù)節(jié)點(diǎn)擁有大量的連接度。由于這種無標(biāo)度網(wǎng)絡(luò)的這種無標(biāo)度特性，使得其對于隨機(jī)的攻擊有一定的抗毀性，但是對于蓄意有針對性的攻擊十分脆弱[8]。國內(nèi)外對無標(biāo)度網(wǎng)絡(luò)的修復(fù)策略上已經(jīng)取得了一定的進(jìn)展。文獻(xiàn)[9]指出，池麗平等人最早提出了復(fù)雜網(wǎng)絡(luò)在遭到攻擊之后的修復(fù)策略研究[10]，建立了一種節(jié)點(diǎn)修復(fù)模型，分析了在不同攻擊下的修復(fù)效果。文獻(xiàn)[11-15]針對不同領(lǐng)域，將不同領(lǐng)域中的網(wǎng)絡(luò)抽象為復(fù)雜網(wǎng)絡(luò)，并用了類似的修復(fù)策略進(jìn)行修復(fù)。這種修復(fù)策略是在被攻擊節(jié)點(diǎn)有修復(fù)可能的前提下，將修復(fù)人員及資源抽象為網(wǎng)絡(luò)的修復(fù)因子，并且按照一定的策略分配，得出每個(gè)節(jié)點(diǎn)被修復(fù)的概率，從而按照這種概率對網(wǎng)絡(luò)進(jìn)行修復(fù)。其中的分配策略大致可分為平均分配策略和按照度進(jìn)行重點(diǎn)分配的策略，并且得到了不同的修復(fù)效果。

以上所介紹的國內(nèi)外研究的修復(fù)策略，都是針對網(wǎng)絡(luò)節(jié)點(diǎn)可以修復(fù)的情況。然而在現(xiàn)實(shí)中，很多情況是無法及時(shí)對故障節(jié)點(diǎn)進(jìn)行修復(fù)的，比如：攻擊強(qiáng)度大，使得被攻擊節(jié)點(diǎn)被摧毀；資源不冗余，無法調(diào)配多余的資源對故障節(jié)點(diǎn)進(jìn)行修復(fù)；節(jié)點(diǎn)的修復(fù)需要較長的修復(fù)時(shí)間周期等。在諸如此類的情況下，如果無法及時(shí)的恢復(fù)網(wǎng)絡(luò)的連通性或功能，將會造成極大的影響和危害。所以，研究被攻擊節(jié)點(diǎn)無法被修復(fù)的情況下的修復(fù)策略是十分有意義的。因此，本文研究的是針對無標(biāo)度網(wǎng)絡(luò)，在蓄意攻擊下，節(jié)點(diǎn)無法被修復(fù)時(shí)，恢復(fù)網(wǎng)絡(luò)連通性的修復(fù)策略。

1 修復(fù)策略

1.1 無標(biāo)度網(wǎng)絡(luò)模型1.1.1 初始網(wǎng)絡(luò)

整個(gè)網(wǎng)絡(luò)的初始網(wǎng)絡(luò)由n個(gè)初始節(jié)點(diǎn)構(gòu)成。任意兩個(gè)節(jié)點(diǎn)之間，按照0.5的概率連接，最后構(gòu)成一個(gè)隨機(jī)的初始網(wǎng)絡(luò)。

1.1.2 演化過程

在由n個(gè)節(jié)點(diǎn)構(gòu)成的初始網(wǎng)絡(luò)的基礎(chǔ)上，網(wǎng)絡(luò)每演化一次，即向網(wǎng)絡(luò)中增加一個(gè)新的節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中原有的節(jié)點(diǎn)新生成m條連接邊。當(dāng)新節(jié)點(diǎn)選擇與原網(wǎng)絡(luò)的節(jié)點(diǎn)相連接時(shí)，服從一定的擇優(yōu)原則。本文中的擇優(yōu)原則是按照節(jié)點(diǎn)的度來決定節(jié)點(diǎn)被選中的概率，如式（1）。最后演化為一個(gè)節(jié)點(diǎn)數(shù)為N的無標(biāo)度網(wǎng)絡(luò)。

其中，P（i）為第 i個(gè)節(jié)點(diǎn)被選中的概率；k（i）為網(wǎng)絡(luò)中第i個(gè)節(jié)點(diǎn)的度；K為網(wǎng)絡(luò)中所有節(jié)點(diǎn)度之和。

1.2 攻擊策略和修復(fù)策略

1.2.1 攻擊策略

本文中對網(wǎng)絡(luò)進(jìn)行的攻擊為，一次性打擊批量的節(jié)點(diǎn)。根據(jù)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度，對所有的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行重要度排序，即認(rèn)為度值越高，節(jié)點(diǎn)越重要。之后對網(wǎng)絡(luò)中最重要的一批節(jié)點(diǎn)進(jìn)行攻擊。被攻擊的節(jié)點(diǎn)將刪除其在網(wǎng)絡(luò)中的所有連接邊，并且不可被還原修復(fù)。是一種即時(shí)的，高強(qiáng)度的，蓄意的攻擊。

1.2.2 修復(fù)策略

由于本文中被攻擊的節(jié)點(diǎn)是不可修復(fù)的，所以本文提出了一種在剩余完好的節(jié)點(diǎn)中進(jìn)行連邊補(bǔ)償?shù)男迯?fù)辦法。本文的修復(fù)策略具體如下：

1）攻擊對象為演化完成之后的無標(biāo)度網(wǎng)絡(luò)，共有N個(gè)節(jié)點(diǎn)；

2）對這N個(gè)節(jié)點(diǎn)進(jìn)行按度值大小降序排列，得到（N1，N2，N3...NN）；

3）對度值最高的前 w 個(gè)節(jié)點(diǎn)（N1，N2...Nw）進(jìn)行攻擊，即刪除其所有連邊，并且不可修復(fù)。這里的不可修復(fù)指的是這w個(gè)節(jié)點(diǎn)被刪除所有連接邊之后，不可以再被連接；

5）再對下一個(gè)被攻擊節(jié)點(diǎn)N2按照上述修復(fù)策略進(jìn)行修復(fù)，一直修復(fù)到Nx，共修復(fù)x個(gè)。

2 仿真研究

文中以無標(biāo)度網(wǎng)絡(luò)為研究對象，對已有無標(biāo)度網(wǎng)絡(luò)進(jìn)行一次蓄意、批量的節(jié)點(diǎn)攻擊，利用對被攻擊節(jié)點(diǎn)的相鄰節(jié)點(diǎn)進(jìn)行連邊補(bǔ)償?shù)男迯?fù)策略。

初始網(wǎng)絡(luò)是由20個(gè)節(jié)點(diǎn)按照0.5的概率兩兩相連構(gòu)成的網(wǎng)絡(luò)。演化過程中，每演化一步網(wǎng)絡(luò)中加入一個(gè)新節(jié)點(diǎn)，在原網(wǎng)絡(luò)中擇優(yōu)選擇節(jié)點(diǎn)建立m=2條連邊。演化最后形成N=100個(gè)節(jié)點(diǎn)的無標(biāo)度網(wǎng)絡(luò)。

對這個(gè)演化后的網(wǎng)絡(luò)進(jìn)行一次蓄意的批量節(jié)點(diǎn)的攻擊，其中，攻擊節(jié)點(diǎn)的數(shù)目為w=10，20，30個(gè)分別進(jìn)行10次仿真。并從第一個(gè)被攻擊的節(jié)點(diǎn)到最后一個(gè)，依次按照修復(fù)策略進(jìn)行修復(fù)。用最大連通圖L來評價(jià)網(wǎng)絡(luò)的連通性。

其中，L為最大連通圖比值，Lmax為網(wǎng)絡(luò)中最大連通子網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)，N為整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)。針對每一個(gè)w，進(jìn)行十次仿真，對仿真結(jié)果數(shù)據(jù)取平均值，得到修復(fù)效果圖。

圖1、圖 2、圖 3分別為 w=10、20、30時(shí)的修復(fù)效果圖。其中橫軸為針對被攻擊節(jié)點(diǎn)的修復(fù)個(gè)數(shù)，縱軸為最大連通圖比值，即修復(fù)效果。

由于被攻擊節(jié)點(diǎn)不可修復(fù)，因此根據(jù)w的賦值不同，網(wǎng)絡(luò)的連通性即最大連通圖的最大值也不同。比如，w=10時(shí)，對于N=100，修復(fù)后網(wǎng)絡(luò)的最大連通圖值為0.9，w=20時(shí)，最大值為0.8，W=30時(shí)最大值為0.7。分析可知：w=10時(shí)，只對前3個(gè)被攻擊節(jié)點(diǎn)修復(fù)就能使連通率達(dá)到0.85以上；w=20時(shí)，針對前5個(gè)被攻擊節(jié)點(diǎn)進(jìn)行修復(fù)就能使連通率達(dá)到0.7以上；w=30時(shí)，針對前8個(gè)被攻擊節(jié)點(diǎn)進(jìn)行修復(fù)就能使連通率達(dá)到0.6以上。因此在這種一次性批量攻擊下，使用這種修復(fù)策略，只針對少量被攻擊節(jié)點(diǎn)進(jìn)行修復(fù)就能使網(wǎng)絡(luò)恢復(fù)較好的連通性。為了分析本文的修復(fù)策略的適用性，本文針對N=200和N=500的無標(biāo)度網(wǎng)絡(luò)也進(jìn)行了仿真分析，并且分別根據(jù)十次仿真結(jié)果的平均值得到了修復(fù)效果圖。其中，對于N=200的網(wǎng)絡(luò)，取攻擊節(jié)點(diǎn)個(gè)數(shù)w=30；對于N=500的網(wǎng)絡(luò)，取攻擊節(jié)點(diǎn)個(gè)數(shù)w=50。修復(fù)效果圖如圖4，5所示。

圖1 w=10時(shí)的修復(fù)效果圖

圖2 w=20時(shí)的修復(fù)效果圖

圖3 W=30時(shí)的修復(fù)效果圖

圖4 N=200，w=30時(shí)的修復(fù)效果圖

圖5 N=500，w=50時(shí)的修復(fù)效果圖

分析上述結(jié)果，可知本文這種修復(fù)策略，在被攻擊節(jié)點(diǎn)無法修復(fù)時(shí)，能夠較好的保證網(wǎng)絡(luò)的連通性

3 結(jié) 論

文中對被攻擊節(jié)點(diǎn)無法被修復(fù)的情況下，提出了一種新的連邊補(bǔ)償?shù)男迯?fù)策略，并針對一次性蓄意批量的節(jié)點(diǎn)攻擊進(jìn)行的仿真分析。結(jié)果證明，在本文中的修復(fù)策略下，攻擊發(fā)生后，只對被攻擊節(jié)點(diǎn)的前百分之二十的節(jié)點(diǎn)進(jìn)行修復(fù)就可以使得網(wǎng)絡(luò)百分之八十的節(jié)點(diǎn)連通，而當(dāng)修復(fù)節(jié)點(diǎn)數(shù)量達(dá)到一定值時(shí)，可以保證存活節(jié)點(diǎn)全部連通。并且對于小規(guī)模無標(biāo)度網(wǎng)絡(luò)和大規(guī)模的無標(biāo)度網(wǎng)絡(luò)，該修復(fù)策略都有較好的修復(fù)效果。

在現(xiàn)實(shí)中，有些網(wǎng)絡(luò)的節(jié)點(diǎn)修復(fù)困難或者成本高無法及時(shí)修復(fù)的情況下，這種修復(fù)策略對于及時(shí)的恢復(fù)網(wǎng)絡(luò)連通性具有一定的意義；在理論上，就目前復(fù)雜網(wǎng)絡(luò)的修復(fù)策略研究大多是對故障節(jié)點(diǎn)直接修復(fù)的情況而言，這種采用建立新的連邊的修復(fù)策略可以說是一種新的思路。

[1]CHEN Duan-bing，LU Lin-yuan，SHANG Ming-Sheng，et al.Identifying influential nodes in complex networks[J].2012，F(xiàn)uel 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]胡斌，黎放，多種攻擊策略下無標(biāo)度網(wǎng)絡(luò)修復(fù)策略[J].系統(tǒng)工程與電子技術(shù)，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]劉中華，胡兵，吳榮華.基于修復(fù)策略的艦艇編隊(duì)復(fù)雜網(wǎng)絡(luò)系統(tǒng)可靠性研究 [J].計(jì)算機(jī)科學(xué)，2012，39（6A）：139-141.

[12]狄鵬，黎放，胡斌，網(wǎng)絡(luò)中心戰(zhàn)模型修復(fù)策略研究[C]//Proceedings of International Conference on Broadcast Technology&Multimedia Communication，2010.

[13]王甲生，吳曉平，陳澤茂，等.修復(fù)策略下典型拓?fù)浣Y(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)抗毀性研究 [J].海 軍 工 程 大學(xué) 學(xué) 報(bào)，2015，27（4）：75-79.

[14]蔣勇，趙作鵬.多屬性加權(quán)模糊貝葉斯的復(fù)雜網(wǎng)絡(luò)故障自修復(fù)技術(shù)[J].計(jì)算機(jī)應(yīng)用研究，2015，32（8）:2378-2381.

[15]王正武，周振宇，胡靜.基于節(jié)點(diǎn)修復(fù)效果的故障路網(wǎng)修復(fù)策略[J].長沙理工大學(xué)學(xué)報(bào)自然科學(xué)版，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—），男，朝鮮族，朝鮮人，碩士研究生。研究方向：復(fù)雜網(wǎng)絡(luò)。