復(fù)雜網(wǎng)絡(luò)中修復(fù)策略研究

鄭力明，李曉冬，羅建祿，韓貴杰

（1.武警警官學(xué)院 電子技術(shù)系，四川 成都 610213；2.武警警官學(xué)院 科研部，四川 成都 610213）

現(xiàn)實世界中的各種復(fù)雜網(wǎng)絡(luò)，如社會網(wǎng)絡(luò)（朋友關(guān)系網(wǎng)絡(luò)、合作網(wǎng)絡(luò)）、技術(shù)網(wǎng)絡(luò)（Internet、電力網(wǎng)）、生物網(wǎng)絡(luò)（神經(jīng)網(wǎng)絡(luò)、食物鏈網(wǎng)絡(luò)）等[1-3]，已在人類社會生活中扮演著越來越重要的角色。然而復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)屬性的不同可能在網(wǎng)絡(luò)中節(jié)點(diǎn)出現(xiàn)故障后引起拓?fù)浣Y(jié)構(gòu)的極大變化，甚至是整個復(fù)雜網(wǎng)絡(luò)的癱瘓，因此如何提高復(fù)雜網(wǎng)絡(luò)抗毀性成為國內(nèi)外研究的重點(diǎn)。Albert等人[4]的研究表明，無標(biāo)度網(wǎng)絡(luò)相對于隨機(jī)網(wǎng)絡(luò)，在隨機(jī)打擊條件下，前者具有更好的抗毀性，在故意打擊條件下，后者具有更好的抗毀性。盡管可以通過優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以提高網(wǎng)絡(luò)抗毀性，但是采用此類被動防御的措施在面對頻繁密集的打擊時仍然會造成整個網(wǎng)絡(luò)的癱瘓，因此節(jié)點(diǎn)失效后需要盡快修復(fù)以保證網(wǎng)絡(luò)連通性。

池麗平等人[5]提出了在隨機(jī)網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)中節(jié)點(diǎn)受到故意攻擊后的修復(fù)模型，該模型分兩步，第一步找出網(wǎng)絡(luò)中度最大的節(jié)點(diǎn)并將該節(jié)點(diǎn)與其他所有節(jié)點(diǎn)的連接斷開，第二步該節(jié)點(diǎn)以固定的概率與網(wǎng)絡(luò)中其他節(jié)點(diǎn)重新建立連接。通過不斷重復(fù)上述步驟以研究網(wǎng)絡(luò)的穩(wěn)定性。池麗平等人的研究結(jié)果表明在隨機(jī)網(wǎng)絡(luò)中，網(wǎng)絡(luò)的穩(wěn)定性與隨機(jī)網(wǎng)絡(luò)的平均度呈冪律分布；在無標(biāo)度網(wǎng)絡(luò)中，網(wǎng)絡(luò)的穩(wěn)定性與修復(fù)概率呈指數(shù)分布。然而在實際網(wǎng)絡(luò)中，受資源限制，每個節(jié)點(diǎn)可被修復(fù)的概率是不同的，且總的修復(fù)能力也是有限的。

胡斌等人[6]考慮到了實際網(wǎng)絡(luò)中資源受限，并提供平均修復(fù)策略，重點(diǎn)修復(fù)策略和偏好修復(fù)策略以對比在不同網(wǎng)絡(luò)攻擊中的修復(fù)能力。其修復(fù)模型分兩步：第一步找出網(wǎng)絡(luò)中度最大的節(jié)點(diǎn)并將該節(jié)點(diǎn)與其他所有節(jié)點(diǎn)的連接斷開，第二步該節(jié)點(diǎn)根據(jù)修復(fù)策略所對應(yīng)的概率恢復(fù)原來的連接。對無標(biāo)度網(wǎng)絡(luò)的實驗結(jié)果表明，偏好修復(fù)的魯棒性較好。然而在實際網(wǎng)絡(luò)中，節(jié)點(diǎn)的修復(fù)需要一定的時間，這對網(wǎng)絡(luò)的打擊效果和修復(fù)效果都會產(chǎn)生影響。

本文提出一種延遲修復(fù)的復(fù)雜網(wǎng)絡(luò)修復(fù)模型，在此基礎(chǔ)上定義了多種修復(fù)策略，最后給出在隨機(jī)打擊和故意打擊情況下各種修復(fù)策略的修復(fù)能力。

1 修復(fù)模型和修復(fù)策略

1.1 修復(fù)模型

步驟1根據(jù)打擊策略，從網(wǎng)絡(luò)中選擇一個被打擊的節(jié)點(diǎn)，刪除該節(jié)點(diǎn)與其他節(jié)點(diǎn)的所有連接，并對該節(jié)點(diǎn)的修復(fù)時間開始計時。

步驟2遍歷所有被打擊的節(jié)點(diǎn)，如果節(jié)點(diǎn)的修復(fù)時間到達(dá)T，則根據(jù)該節(jié)點(diǎn)的修復(fù)概率進(jìn)行修復(fù)，節(jié)點(diǎn)修復(fù)后恢復(fù)原來的連接。

步驟3重復(fù)步驟1和步驟2。

1.2 修復(fù)策略

復(fù)雜網(wǎng)絡(luò)的修復(fù)策略事實上是指各個節(jié)點(diǎn)的修復(fù)因子的分配策略，由于網(wǎng)絡(luò)中的總修復(fù)因子受限，而各個節(jié)點(diǎn)的重要程度各不相同，在不同的打擊環(huán)境下受關(guān)注的程度也各不相同，因此通過分配有限的修復(fù)因子以提高網(wǎng)絡(luò)的抗毀性。其主要的修復(fù)策略包括：

1）平均修復(fù)（uniform strategy）：各個節(jié)點(diǎn)的修復(fù)因子P都相同，即P=M/N。

2 模擬測試

為了驗證各種修復(fù)策略在不同的網(wǎng)絡(luò)拓?fù)湎碌男迯?fù)能力，實驗中模擬實現(xiàn)了規(guī)模為1000的隨機(jī)網(wǎng)絡(luò)和BA網(wǎng)絡(luò)兩種網(wǎng)絡(luò)拓?fù)?，為了驗證各種修復(fù)策略應(yīng)對多種打擊情況下的修復(fù)能力，實驗中實現(xiàn)了隨機(jī)打擊和故意打擊兩種模式。另外，修復(fù)策略的修復(fù)能力以網(wǎng)絡(luò)的最大連通圖的大小為依據(jù)。實驗中，設(shè)置總的修復(fù)因子M=10，最大修復(fù)因子Pmax=1，修復(fù)時間T=10。

2.1 隨機(jī)網(wǎng)絡(luò)

圖1顯示了隨機(jī)網(wǎng)絡(luò)中對節(jié)點(diǎn)進(jìn)行連續(xù)隨機(jī)打擊后各種修復(fù)策略的修復(fù)效果，其修復(fù)效果由強(qiáng)到弱依次為：均勻修復(fù)、平方根修復(fù)、比例修復(fù)、平方修復(fù)。在隨機(jī)打擊中，由于節(jié)點(diǎn)是隨機(jī)選擇的，因此均勻修復(fù)能夠很好的照顧到每個節(jié)點(diǎn)，實驗顯示網(wǎng)絡(luò)的最大強(qiáng)連通圖的比例穩(wěn)定在91%以上；在隨機(jī)網(wǎng)絡(luò)中各個節(jié)點(diǎn)的度服從泊松分布，因此比例修復(fù)下各個節(jié)點(diǎn)的修復(fù)概率差別不大，實驗顯示網(wǎng)絡(luò)的最大強(qiáng)連通圖的比例穩(wěn)定在88%以上；而平方根修復(fù)則是對比例修復(fù)和均勻分布的折中效果，一方面考慮了節(jié)點(diǎn)度對修復(fù)概率的影響，另一方面也照顧到節(jié)點(diǎn)的公平性，其最大強(qiáng)連通圖的比例穩(wěn)定在90%以上；最后平方修復(fù)是在盡量擴(kuò)大節(jié)點(diǎn)度對修復(fù)概率的影響程度，因此在隨機(jī)選擇度較小的節(jié)點(diǎn)后，其修復(fù)的概率也較小，其最大強(qiáng)連通圖的比例穩(wěn)定在85%以上。

圖2顯示了隨機(jī)網(wǎng)絡(luò)中對節(jié)點(diǎn)進(jìn)行連續(xù)故意打擊后各種修復(fù)策略的修復(fù)效果，其修復(fù)效果由強(qiáng)到弱依次為：平方修復(fù)、比例修復(fù)、平方根修復(fù)、均勻修復(fù)。在故意打擊中，每次選擇系統(tǒng)中度最高的節(jié)點(diǎn)，這樣均勻修復(fù)中度高的節(jié)點(diǎn)被修復(fù)的概率就相對較小，實驗顯示網(wǎng)絡(luò)的最大強(qiáng)連通圖的比例穩(wěn)定在86%以上；比例修復(fù)考慮了節(jié)點(diǎn)度對修復(fù)概率的影響，因此度高的節(jié)點(diǎn)被修復(fù)的概率較大，網(wǎng)絡(luò)的最大強(qiáng)連通圖的比例穩(wěn)定在92%以上；而平方根修復(fù)則是對比例修復(fù)和均勻分布的折中效果，其最大強(qiáng)連通圖的比例穩(wěn)定在89%以上；最后平方修復(fù)是在盡量擴(kuò)大節(jié)點(diǎn)度對修復(fù)概率的影響程度，因此能夠重點(diǎn)保護(hù)度較高的節(jié)點(diǎn)，其最大強(qiáng)連通圖的比例穩(wěn)定在94%以上。

綜上可以看出，對于隨機(jī)網(wǎng)絡(luò)，在不確定對方的打擊模式的情況下，采用比例修復(fù)或者平方根修復(fù)能夠達(dá)到較好的修復(fù)效果，而均勻修復(fù)和平方修復(fù)則只能針對特定的一種打擊模式具有較好效果。

圖1 隨機(jī)網(wǎng)絡(luò)隨機(jī)打擊下的修復(fù)效果Fig.1 Random attack by random network repairing effect

圖2 隨機(jī)網(wǎng)絡(luò)故意打擊下的修復(fù)效果Fig.2 Intentional attack by random network repairing effect

2.2 無標(biāo)度網(wǎng)絡(luò)

圖3顯示了BA網(wǎng)絡(luò)中對節(jié)點(diǎn)進(jìn)行連續(xù)隨機(jī)打擊后各種修復(fù)策略的修復(fù)效果，其中均勻修復(fù)和平方根修復(fù)幾乎具有同樣好的修復(fù)效果，其次為比例修復(fù)，最差的是平方修復(fù)。在隨機(jī)打擊中，由于節(jié)點(diǎn)是隨機(jī)選擇的，因此均勻修復(fù)很好的照顧到每個節(jié)點(diǎn)，其最大強(qiáng)連通圖的比例穩(wěn)定在88%以上；在BA網(wǎng)絡(luò)中各個節(jié)點(diǎn)的度服從冪律分布，因此比例修復(fù)下各個節(jié)點(diǎn)的修復(fù)概率差別較大，實驗顯示網(wǎng)絡(luò)的最大強(qiáng)連通圖的比例穩(wěn)定在85%以上；而平方根修復(fù)則是對比例修復(fù)和均勻分布的折中效果，一方面考慮了節(jié)點(diǎn)度對修復(fù)概率的影響，另一方面也照顧到節(jié)點(diǎn)的公平性，其最大強(qiáng)連通圖的比例穩(wěn)定在87%以上；最后平方修復(fù)是在盡量擴(kuò)大節(jié)點(diǎn)度對修復(fù)概率的影響程度，因此在隨機(jī)選擇度較小的節(jié)點(diǎn)后，其修復(fù)的概率會非常小，其最大強(qiáng)連通圖的比例隨時間一直減小。

圖4顯示了BA網(wǎng)絡(luò)中對節(jié)點(diǎn)進(jìn)行連續(xù)故意打擊后各種修復(fù)策略的修復(fù)效果，其修復(fù)效果由強(qiáng)到弱依次為：平方修復(fù)、比例修復(fù)、平方根修復(fù)、均勻修復(fù)。在故意打擊中，每次選擇系統(tǒng)中度最高的節(jié)點(diǎn)，這樣均勻修復(fù)中度高的節(jié)點(diǎn)被修復(fù)的概率就相對較小，另外BA網(wǎng)絡(luò)中度高的節(jié)點(diǎn)對網(wǎng)絡(luò)的連通性影響很大，實驗顯示網(wǎng)絡(luò)的最大強(qiáng)連通圖的比例隨時間急劇減?。槐壤迯?fù)考慮了節(jié)點(diǎn)度對修復(fù)概率的影響，因此度高的節(jié)點(diǎn)被修復(fù)的概率較大，網(wǎng)絡(luò)的最大強(qiáng)連通圖的比例穩(wěn)定在88%以上；而平方根修復(fù)則是對比例修復(fù)和均勻分布的折中效果，其最大強(qiáng)連通圖的比例穩(wěn)定在92%以上；最后平方修復(fù)是在盡量擴(kuò)大節(jié)點(diǎn)度對修復(fù)概率的影響程度，因此能夠重點(diǎn)保護(hù)度較高的節(jié)點(diǎn)，其最大強(qiáng)連通圖的比例穩(wěn)定在94%以上。

綜上可以看出，對于BA網(wǎng)絡(luò)，在不確定對方的打擊模式的情況下，采用平方根修復(fù)能夠達(dá)到較好的修復(fù)效果，其次為比例修復(fù)，而均勻修復(fù)和平方修復(fù)則只能針對特定的一種打擊模式具有較好效果。

圖3 無標(biāo)度網(wǎng)絡(luò)隨機(jī)打擊下的修復(fù)效果Fig.3 Random attack by scale-free network repairing effect

圖4 無標(biāo)度網(wǎng)絡(luò)故意打擊下的修復(fù)效果Fig.4 Intentional attack by scale-free network repairing effect

3 結(jié)束語

文中針對復(fù)雜網(wǎng)絡(luò)修復(fù)問題，首先提出了一種延遲修復(fù)的網(wǎng)絡(luò)修復(fù)模型，并在不同復(fù)雜網(wǎng)絡(luò)拓?fù)湎箩槍﹄S機(jī)打擊和故意打擊提出了四種不同的修復(fù)策略，模擬實驗結(jié)果顯示在隨機(jī)網(wǎng)絡(luò)下，采用比例修復(fù)或者平方根修復(fù)能夠達(dá)到較好的修復(fù)效果；而在無標(biāo)度網(wǎng)絡(luò)下，采用平方根修復(fù)能夠達(dá)到較好的修復(fù)效果。

[1]Albert R，Barabasi A L.Statistical mechanics of complex network[J].Review of Modern Physics，2002，74（1）:47-97.

[2]S.Ratnasamy， P.Francis， M.Handley EA.A Scalable Content-Addressable Network [C]//In: Proc. of ACM SIGCOMM.New York，USA:2001.149-160.

[3]Watts D J，Strogatz S H.Collective dynamics of small-world networks[J].Nature，1998，393（4537）:440-448.

[4]Albert R，Jeong H，Barabasi A L.Error and attack tolerance of complex networks[J].Nature，2000，406（6794）:378-382.

[5]Chi L P，Yang C B，Cai X.Stability of random networks under evolution of attack and repair[J].Chinese Physics Letters，2006，23（1）:263-266.

[6]胡斌，黎放.多種攻擊策略下無標(biāo)度網(wǎng)絡(luò)修復(fù)策略[J].系統(tǒng)工程與電子技術(shù)，2010，32（1）:43-47.

HU Bin，LI Fang.Multiple attack strategy scale-free network repair strategy[J].Systems Engineering and Electronics，2010，32（1）:43-47.