復雜網絡中修復策略研究

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

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

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

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

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

本文提出一種延遲修復的復雜網絡修復模型，在此基礎上定義了多種修復策略，最后給出在隨機打擊和故意打擊情況下各種修復策略的修復能力。

1 修復模型和修復策略

1.1 修復模型

步驟1根據打擊策略，從網絡中選擇一個被打擊的節點，刪除該節點與其他節點的所有連接，并對該節點的修復時間開始計時。

步驟2遍歷所有被打擊的節點，如果節點的修復時間到達T，則根據該節點的修復概率進行修復，節點修復后恢復原來的連接。

步驟3重復步驟1和步驟2。

1.2 修復策略

復雜網絡的修復策略事實上是指各個節點的修復因子的分配策略，由于網絡中的總修復因子受限，而各個節點的重要程度各不相同，在不同的打擊環境下受關注的程度也各不相同，因此通過分配有限的修復因子以提高網絡的抗毀性。其主要的修復策略包括：

1）平均修復（uniform strategy）：各個節點的修復因子P都相同，即P=M/N。

2 模擬測試

為了驗證各種修復策略在不同的網絡拓撲下的修復能力，實驗中模擬實現了規模為1000的隨機網絡和BA網絡兩種網絡拓撲，為了驗證各種修復策略應對多種打擊情況下的修復能力，實驗中實現了隨機打擊和故意打擊兩種模式。另外，修復策略的修復能力以網絡的最大連通圖的大小為依據。實驗中，設置總的修復因子M=10，最大修復因子Pmax=1，修復時間T=10。

2.1 隨機網絡

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

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

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

圖1 隨機網絡隨機打擊下的修復效果Fig.1 Random attack by random network repairing effect

圖2 隨機網絡故意打擊下的修復效果Fig.2 Intentional attack by random network repairing effect

2.2 無標度網絡

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

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

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

圖3 無標度網絡隨機打擊下的修復效果Fig.3 Random attack by scale-free network repairing effect

圖4 無標度網絡故意打擊下的修復效果Fig.4 Intentional attack by scale-free network repairing effect

3 結束語

文中針對復雜網絡修復問題，首先提出了一種延遲修復的網絡修復模型，并在不同復雜網絡拓撲下針對隨機打擊和故意打擊提出了四種不同的修復策略，模擬實驗結果顯示在隨機網絡下，采用比例修復或者平方根修復能夠達到較好的修復效果；而在無標度網絡下，采用平方根修復能夠達到較好的修復效果。

[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]胡斌，黎放.多種攻擊策略下無標度網絡修復策略[J].系統工程與電子技術，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.