基于社區(qū)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)魯棒性優(yōu)化策略

劉迪洋，張 震，張 進(jìn)

（1.解放軍戰(zhàn)略支援部隊信息工程大學(xué) 信息技術(shù)研究所，鄭州 450000；2.網(wǎng)絡(luò)通信與安全紫金山實(shí)驗(yàn)室，南京 210000）

0 概述

復(fù)雜網(wǎng)絡(luò)是指具有自組織、自相似、吸引子、小世界、無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)。現(xiàn)實(shí)世界中存在電力傳輸網(wǎng)絡(luò)［1］、金融信息網(wǎng)絡(luò)［2］、交通運(yùn)輸網(wǎng)絡(luò)［3］等各種各樣的復(fù)雜網(wǎng)絡(luò)。目前，以互聯(lián)網(wǎng)為代表的信息技術(shù)迅速發(fā)展，網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路隨機(jī)性失效、網(wǎng)元系統(tǒng)包含漏洞后門等不確定擾動事件頻發(fā)，使得網(wǎng)絡(luò)魯棒性［4］問題日趨突出。因此，研究復(fù)雜網(wǎng)絡(luò)魯棒性優(yōu)化策略以提高復(fù)雜網(wǎng)絡(luò)在遭受攻擊時維持其拓?fù)溥B接或服務(wù)功能的能力，具有重要的理論和現(xiàn)實(shí)意義。

近年來，研究人員對網(wǎng)絡(luò)魯棒性優(yōu)化策略進(jìn)行了大量研究并取得了一定的研究成果。DUAN 等［5］通過在保留網(wǎng)絡(luò)原始連接的基礎(chǔ)上創(chuàng)建冗余邊來提高網(wǎng)絡(luò)魯棒性，但在電力運(yùn)輸網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)中添加冗余邊的代價較高，實(shí)用性較差，因此HERRMANN 等［6］提出重連邊策略，將網(wǎng)絡(luò)魯棒性策略建模為一個優(yōu)化問題，研究如何通過最低成本的重連邊使網(wǎng)絡(luò)具有最優(yōu)魯棒性，該文作者將調(diào)整后的網(wǎng)絡(luò)拓?fù)浞Q為類“洋蔥狀”網(wǎng)絡(luò)，類“洋蔥狀”網(wǎng)絡(luò)相比其他拓?fù)渚哂懈鼜?qiáng)的抗攻擊能力。SCHNEIDER 等［7］基于保度重連邊提出一種隨機(jī)重連邊策略Random Rewiring。LOUZADA［8］提出一種適應(yīng)網(wǎng)絡(luò)拓?fù)溲莼闹悄苤剡B邊策略Smart Rewiring。BAI 等［9-10］分別采用爬山算法、模擬退火算法搜索最優(yōu)重連邊策略。ZHOU 等［11］針對無標(biāo)度網(wǎng)絡(luò)提出一種基于MA-RSFMA算法的魯棒性優(yōu)化策略MA。SAFAEI等［12］通過考慮邊緣長度、網(wǎng)絡(luò)直徑等網(wǎng)絡(luò)參數(shù)，為搜索最優(yōu)重連邊策略添加約束。ZHOU 等［13］提出一種基于多目標(biāo)進(jìn)化算法MOEA-RSFMMA的魯棒性優(yōu)化策略，提高了網(wǎng)絡(luò)應(yīng)對不同類型攻擊的魯棒性。GHEDINI［14］提出一種魯棒性度量指標(biāo)來評估網(wǎng)絡(luò)社區(qū)在節(jié)點(diǎn)級攻擊和社區(qū)級攻擊下的魯棒性。MA 等［15］利用網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)信息來提升網(wǎng)絡(luò)魯棒性。

從目前的研究進(jìn)展來看，大部分研究是在保留網(wǎng)絡(luò)度分布特性的基礎(chǔ)上，通過建立優(yōu)化模型搜索最優(yōu)重連邊，將網(wǎng)絡(luò)拓?fù)湔{(diào)整為具有較強(qiáng)魯棒性的類“洋蔥狀”網(wǎng)絡(luò)。社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)的一個重要特性，社區(qū)結(jié)構(gòu)反映的是一個復(fù)雜網(wǎng)絡(luò)中各小網(wǎng)絡(luò)的分布和相互聯(lián)系的狀況，網(wǎng)絡(luò)在遭受惡意攻擊的情況下，社區(qū)間關(guān)鍵連接的斷開會導(dǎo)致部分社區(qū)與整個網(wǎng)絡(luò)斷開連接。應(yīng)用不同的網(wǎng)絡(luò)魯棒性優(yōu)化策略會不同程度地改變網(wǎng)絡(luò)的初始社區(qū)結(jié)構(gòu)，而社區(qū)結(jié)構(gòu)的改變會導(dǎo)致網(wǎng)絡(luò)功能模塊的丟失［16］，例如在局域網(wǎng)中根據(jù)重連邊策略將某些主機(jī)連接至其他局域網(wǎng)，會破壞局域網(wǎng)預(yù)期的結(jié)構(gòu)與功能，因此在優(yōu)化網(wǎng)絡(luò)魯棒性的同時維護(hù)初始網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)顯得十分重要?；诖?，本文提出一種基于社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)魯棒性優(yōu)化策略Community Rewiring。

1 重連邊策略對網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的影響

1.1 網(wǎng)絡(luò)魯棒性評價標(biāo)準(zhǔn)

本文考慮高度攻擊（High-Degree Attack，HDA）和高介數(shù)攻擊（High-Betweenness Attack，HBA）［17］下的網(wǎng)絡(luò)魯棒性。這兩種攻擊分別根據(jù)節(jié)點(diǎn)的度中心性和介數(shù)中心性衡量節(jié)點(diǎn)的重要性，每次攻擊移除當(dāng)前網(wǎng)絡(luò)中最重要的節(jié)點(diǎn)及與該節(jié)點(diǎn)相連的邊。只要完成一次攻擊，就對當(dāng)前網(wǎng)絡(luò)的節(jié)點(diǎn)按重要性重新排序。

目標(biāo)網(wǎng)絡(luò)G初始時是連通的網(wǎng)絡(luò)，其最大連通子圖的規(guī)模為網(wǎng)絡(luò)的節(jié)點(diǎn)個數(shù)N。當(dāng)網(wǎng)絡(luò)遭受惡意攻擊時，網(wǎng)絡(luò)中的部分節(jié)點(diǎn)失效，最大連通子圖規(guī)模也隨之變小，這一過程如圖1 所示，灰色節(jié)點(diǎn)部分表示當(dāng)前網(wǎng)絡(luò)的最大連通子圖。

圖1 惡意攻擊下最大聯(lián)通子圖規(guī)模的變化Fig.1 Changes in the size of the maximum connected subgraph under malicious attacks

由此可見，網(wǎng)絡(luò)最大連通子圖的規(guī)?？梢苑从尘W(wǎng)絡(luò)的連通性能。因此，本文在惡意攻擊下采用魯棒性指數(shù)R來衡量網(wǎng)絡(luò)魯棒性［18］，R的計算公式如下：

其中：S(Q)為Q個節(jié)點(diǎn)失效后網(wǎng)絡(luò)最大連通子圖包含的節(jié)點(diǎn)數(shù)目；R的取值范圍為為網(wǎng)絡(luò)初始節(jié)點(diǎn)的個數(shù)，R越大網(wǎng)絡(luò)抵抗惡意攻擊的能力越強(qiáng)，R越小網(wǎng)絡(luò)抵抗惡意攻擊的能力越弱；Q可用于描述攻擊規(guī)模，Q=qN，q為被攻擊節(jié)點(diǎn)占初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的比例，s(q)是被攻擊節(jié)點(diǎn)比例為q時網(wǎng)絡(luò)最大連通子圖包含的節(jié)點(diǎn)數(shù)與初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的比例，初始時s(q)=1，隨著攻擊的進(jìn)行q不斷增加，與最大連通子圖斷開連接的節(jié)點(diǎn)數(shù)不斷增加，s(q)越來越小。若s(q)減小得越慢，則網(wǎng)絡(luò)抵抗惡意攻擊的能力越強(qiáng)；若s(q)減小得越快，則網(wǎng)絡(luò)抵抗惡意攻擊的能力越弱。

1.2 重連邊后網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)變化情況分析

網(wǎng)絡(luò)魯棒性和社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中兩個高度相關(guān)的問題，社區(qū)是網(wǎng)絡(luò)中存在的關(guān)系緊密的節(jié)點(diǎn)集合，社區(qū)內(nèi)部節(jié)點(diǎn)之間具有緊密的連接，而社區(qū)之間則為松散的連接。社區(qū)劃分很大程度上依賴于初始網(wǎng)絡(luò)的結(jié)構(gòu)，維持正確的社區(qū)劃分對于網(wǎng)絡(luò)發(fā)揮其功能和性能十分重要。

為達(dá)到網(wǎng)絡(luò)魯棒性優(yōu)化效果，需要對重連邊策略進(jìn)行多次迭代，隨機(jī)重連邊迭代過程中網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的變化如圖2 所示，彩色效果見《計算機(jī)工程》官網(wǎng)HTML 版。

圖2 魯棒性優(yōu)化過程中網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的變化Fig.2 Changes of network community structure in robustness optimization process

節(jié)點(diǎn)的不同顏色代表屬于不同的社區(qū)，初始網(wǎng)絡(luò)包含3 個社區(qū)，社區(qū)結(jié)構(gòu)劃分為［0，1，3，6，8，13，14，16，20，23，24，25，27］、［2，4，5，7，9，15，21，26，28，29］、［10，11，12，17，18，19，22］，網(wǎng)絡(luò)魯棒性指數(shù)為R=0.24。當(dāng)經(jīng)過500 次迭代優(yōu)化后，網(wǎng)絡(luò)包含5 個社區(qū)，社區(qū)結(jié)構(gòu)劃分變?yōu)椋?，4，7，10，15，17，18，22，28］，［1，3，8，23，29］、［2，9，11，14，21］、［5，6，12，13，16］、［19，20，24，25，26，27］，網(wǎng)絡(luò)魯棒性指數(shù)提升至R=0.31。當(dāng)經(jīng)過1 000次迭代優(yōu)化后，網(wǎng)絡(luò)包含5個社區(qū)，社區(qū)結(jié)構(gòu)劃分變?yōu)椋?，7，12，28］、［1，3，8，22，23，27，29］、［2，9，14，21，24，25］、［4，5，6，10，13，15，17，20］、［11，16，18，19，26］，網(wǎng)絡(luò)魯棒性指數(shù)提升至R=0.34。由此可見，在通過重連邊策略優(yōu)化網(wǎng)絡(luò)魯棒性的過程中，網(wǎng)絡(luò)魯棒性得到提升的同時初始網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)也發(fā)生了較大變化。

1.3 社區(qū)結(jié)構(gòu)保留程度評價標(biāo)準(zhǔn)

在網(wǎng)絡(luò)魯棒性優(yōu)化過程中，保留初始社區(qū)結(jié)構(gòu)是指保持優(yōu)化后網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)與初始網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)之間的相似性。標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI）常用于聚類中度量兩個聚類結(jié)果的相近程度，是社區(qū)發(fā)現(xiàn)的重要衡量指標(biāo)，可以較客觀地評價一個社區(qū)劃分相比標(biāo)準(zhǔn)社區(qū)劃分的準(zhǔn)確度［19］。因此，本文將初始網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分看作標(biāo)準(zhǔn)社區(qū)劃分，隨著魯棒性優(yōu)化過程的進(jìn)行，通過計算當(dāng)前網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)相比初始社區(qū)結(jié)構(gòu)的NMI來衡量優(yōu)化策略對初始社區(qū)結(jié)構(gòu)的保留程度。假設(shè)α為初始網(wǎng)絡(luò)，β為優(yōu)化后的網(wǎng)絡(luò)，NMI 的計算公式如下［20］：

其中：Cα和Cβ分別為優(yōu)化前后的網(wǎng)絡(luò)包含的社區(qū)數(shù)量；矩陣F中的任一元素Fij表示同時存在于網(wǎng)絡(luò)α中的社區(qū)i和網(wǎng)絡(luò)β中的社區(qū)j的節(jié)點(diǎn)數(shù)目；Fi.和Fj.分別為矩陣F的第i行元素之和與第j列元素之和。NMI 的取值范圍為［0，1］，如果優(yōu)化前后網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)完全不同，則NNMI(α，β)=0；如果優(yōu)化前后網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)完全相同，則NNMI(α，β)=1。NMI 越大，表明初始社區(qū)結(jié)構(gòu)保留越完整。

2 基于社區(qū)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)魯棒性優(yōu)化

本文提出一種基于社區(qū)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)魯棒性優(yōu)化策略，旨在提升網(wǎng)絡(luò)魯棒性的同時保留初始網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。該策略共分為3 個階段：1）采用Louvain 算法確定網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)；2）基于模擬退火（Simulated Annealing，SA）算法優(yōu)化網(wǎng)絡(luò)中單個社區(qū)的內(nèi)部魯棒性；3）基于改進(jìn)的Smart Rewiring 策略優(yōu)化社區(qū)間的連接魯棒性?；谏鐓^(qū)結(jié)構(gòu)的網(wǎng)絡(luò)魯棒性優(yōu)化流程如圖3 所示。

那個男裁縫正在忙著整理一天收到的衣服，每件衣服都井然有序地寫著編號。像當(dāng)年在編織袋車間的時候一模一樣。

圖3 基于社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)魯棒性優(yōu)化流程Fig.3 Procedure of network robustness optimization based on community structure

2.1 社區(qū)結(jié)構(gòu)檢測

社區(qū)結(jié)構(gòu)檢測的目的是確定目標(biāo)網(wǎng)絡(luò)G的初始社區(qū)結(jié)構(gòu)。本文采用Louvain 算法檢測網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。Louvain 算法是基于模塊度的社區(qū)發(fā)現(xiàn)算法，能夠發(fā)現(xiàn)層次性的社區(qū)結(jié)構(gòu)，優(yōu)化目標(biāo)是最大化整個社區(qū)網(wǎng)絡(luò)的模塊度，被認(rèn)為是目前性能最好的社區(qū)發(fā)現(xiàn)算法之一［21］。

2.2 社區(qū)內(nèi)魯棒性優(yōu)化

對于社區(qū)內(nèi)魯棒性優(yōu)化，采用保留節(jié)點(diǎn)度的重連邊方法，先在社區(qū)Gi中隨機(jī)選擇兩條邊eij和ekm，再刪除eij和ekm，之后添加eim和ekj。在此過程中，節(jié)點(diǎn)度保持不變，節(jié)點(diǎn)i，j，k，m必須是不同節(jié)點(diǎn)。社區(qū)內(nèi)的重連邊方法如圖4 所示。

圖4 社區(qū)內(nèi)的重連邊方法Fig.4 Rewiring method within in the community

在Random Rewiring 策略中，每次重連邊后比較網(wǎng)絡(luò)魯棒性，如果魯棒性增強(qiáng)則保留重連邊，否則重新選擇eij和ekm。這種啟發(fā)式算法對網(wǎng)絡(luò)魯棒性的優(yōu)化是有效的但不能避免陷入局部最優(yōu)。這是因?yàn)閱l(fā)式算法的實(shí)質(zhì)是一種貪心策略，客觀上決定了會錯過不符合貪心規(guī)則的更優(yōu)策略。通常為避免陷入局部最優(yōu)在算法中引入隨機(jī)性。模擬退火算法基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性，從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，能概率性地跳出局部最優(yōu)并最終趨于全局最優(yōu)。因此，本文選擇模擬退火算法優(yōu)化社區(qū)內(nèi)魯棒性。

對于社區(qū)Gi，輸入?yún)?shù)A表示不同的攻擊策略，計算社區(qū)在不同攻擊策略下的魯棒性Ri(A)，選擇社區(qū)中的兩條邊進(jìn)行重新連接，重連邊之后的社區(qū)記為社區(qū)魯棒性記為如果則接受如果則以一定概率接受被接受的概率取決于和初始溫度T0，ΔR越小，越容易接受重連邊而跳出局部最優(yōu)。在開始時T較高，易跳出局部最優(yōu)，隨著迭代進(jìn)行，T不斷減小，而在接近結(jié)束且當(dāng)T→0 時，跳出局部最優(yōu)變得更加困難。在模擬退火過程中，需要設(shè)置初始溫度T0和溫度進(jìn)度表，使溫度在算法運(yùn)行過程中逐漸降低，以便系統(tǒng)在每一步降低溫度時達(dá)到平衡。參數(shù)T的減小方式對優(yōu)化結(jié)果具有十分重要的影響，本文設(shè)置T(i)=0.8i×T0。

2.3 社區(qū)間魯棒性優(yōu)化

Smart Rewiring 是一種智能高效的魯棒性優(yōu)化策略。該策略首先在目標(biāo)網(wǎng)絡(luò)中隨機(jī)選擇一個節(jié)點(diǎn)i，節(jié)點(diǎn)i至少有2 個度大于1 的鄰居節(jié)點(diǎn)。先選擇節(jié)點(diǎn)i的度最小的節(jié)點(diǎn)j和度最大的節(jié)點(diǎn)m，隨機(jī)選擇節(jié)點(diǎn)j的1 個鄰居節(jié)點(diǎn)n和節(jié)點(diǎn)m的1 個鄰居節(jié)點(diǎn)k，再刪除emk和ejn，之后添加emj和ekn。多次迭代這一過程，每一次均比較重連邊前后的魯棒性，如果魯棒性提升則保留重連邊，否則再次尋找相關(guān)節(jié)點(diǎn)。Smart Rewiring 策略如圖5所示。

圖5 Smart Rewiring 策略Fig.5 Smart Rewiring strategy

為優(yōu)化社區(qū)間連邊的魯棒性，對Smart Rewiring策略進(jìn)行以下改進(jìn)：

1）節(jié)點(diǎn)i的選擇。計算網(wǎng)絡(luò)G的平均節(jié)點(diǎn)度隨機(jī)選擇1 個度大于的節(jié)點(diǎn)i，節(jié)點(diǎn)i至少有1 個不同社區(qū)的鄰居節(jié)點(diǎn)及有1 個度大于2 的同社區(qū)鄰居節(jié)點(diǎn)。

2）重連邊的選擇。選擇節(jié)點(diǎn)i的度最小的1 個同社區(qū)鄰居節(jié)點(diǎn)m，并隨機(jī)選擇m的1 個鄰居節(jié)點(diǎn)k。進(jìn)一步地，先隨機(jī)選擇節(jié)點(diǎn)i的1個不同社區(qū)的鄰居節(jié)點(diǎn)j，再刪除eij和ekm，之后添加eik和ejm。

通過多次迭代這一過程，最終達(dá)到優(yōu)化社區(qū)間連邊魯棒性的目的。社區(qū)間的重連邊方法如圖6所示。

圖6 社區(qū)間重連邊方法Fig.6 Rewiring method between communities

對于完成社區(qū)內(nèi)部魯棒性優(yōu)化的網(wǎng)絡(luò)G，計算網(wǎng)絡(luò)魯棒性R(A)，然后選擇網(wǎng)絡(luò)中的一組節(jié)點(diǎn)進(jìn)行重新連接。重連邊之后的網(wǎng)絡(luò)記為G*，魯棒性記為R*(A)。設(shè)置魯棒性優(yōu)化參數(shù)ΔR對優(yōu)化效果進(jìn)行判斷，如果R*(A)＞R(A)+ΔR，則保留此時的社區(qū)結(jié)構(gòu)，即G=G*，完成一輪優(yōu)化。此外，為優(yōu)化過程設(shè)置終止參數(shù)Nmax，當(dāng)達(dá)到迭代次數(shù)時，優(yōu)化終止。

3 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證本文Community Rewiring 策略能在優(yōu)化網(wǎng)絡(luò)魯棒性的同時保持網(wǎng)絡(luò)初始社區(qū)結(jié)構(gòu)，將其與Smart Rewiring 和MA 策略在BA、WS 和WU-PowerGrid 網(wǎng)絡(luò)中進(jìn)行對比實(shí)驗(yàn)。BA 網(wǎng)絡(luò)與WS 網(wǎng)絡(luò)為模擬網(wǎng)絡(luò)，其中，BA 網(wǎng)絡(luò)的度分布具有重尾分布特性，WS 網(wǎng)絡(luò)具有高聚類和平均路徑較短的特性。WU-PowerGrid 網(wǎng)絡(luò)為真實(shí)網(wǎng)絡(luò)，以真實(shí)的西歐電力網(wǎng)為模型，節(jié)點(diǎn)代表發(fā)電機(jī)，節(jié)點(diǎn)之間的鏈路代表高壓輸電線路。3 種網(wǎng)絡(luò)拓?fù)湫畔⑷绫? 所示。

表1 網(wǎng)絡(luò)拓?fù)湫畔able 1 Network topology information

3.1 魯棒性優(yōu)化的有效性驗(yàn)證

為對網(wǎng)絡(luò)魯棒性優(yōu)化的有效性進(jìn)行驗(yàn)證，本文模擬了3 種網(wǎng)絡(luò)遭受HDA 和HBA 兩種惡意攻擊的場景，分析隨著節(jié)點(diǎn)失效率q的增加，s(q)的下降趨勢的變化，并對3 種策略的網(wǎng)絡(luò)魯棒性優(yōu)化效果進(jìn)行對比分析。

BA 網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果如圖7 所示?？梢钥闯觯S著q值的增加，當(dāng)不采用優(yōu)化策略時，同等規(guī)模兩種攻擊下s(q)下降速度相近，這是由于在BA 網(wǎng)絡(luò)此類節(jié)點(diǎn)度分布接近冪律分布的網(wǎng)絡(luò)中，兩種攻擊策略都能較準(zhǔn)確地確定其重要節(jié)點(diǎn)，攻擊效果較接近。當(dāng)采用Smart Rewiring 與MA 策略優(yōu)化后，s(q)下降有所減緩；當(dāng)q為0.6 時，s(q)降至0.1 以下。當(dāng)采用Community Rewiring 策略后，s(q)下降速度介于Smart Rewiring 與MA 策略之間。

圖7 3 種優(yōu)化策略下BA 網(wǎng)絡(luò)的s(q)變化情況Fig.7 Changes of s(q)in BA network under three optimization strategies

WS 網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果如圖8 所示?？梢钥闯觯S著q值的增加，當(dāng)不采用優(yōu)化策略時，同等規(guī)模HBA 攻擊下s(q)下降比HDA更快，當(dāng)q=0.2時HBA攻擊下s(q)已接近0.1，而HDA 攻擊下q=0.4 時網(wǎng)絡(luò)基本崩潰，這是由于WS 網(wǎng)絡(luò)有顯著的小世界特征，高介數(shù)節(jié)點(diǎn)的移除會造成網(wǎng)絡(luò)迅速崩潰。當(dāng)采用Smart Rewiring 與MA 策略優(yōu)化后，s(q)下降有所減緩。在HDA 攻擊下，當(dāng)q=0.6 時，網(wǎng)絡(luò)完全崩潰。在HBA 攻擊下，當(dāng)q=0.4時，網(wǎng)絡(luò)也完全崩潰。在采用Community Rewiring 策略后，s(q)下降速度介于Smart Rewiring 與MA 策略之間，在HDA 攻擊和HBA 攻擊下，q分別為0.6 和0.4 時s(q)降至0.1 以下。

圖8 3 種優(yōu)化策略下WS 網(wǎng)絡(luò)的s(q)變化情況Fig.8 Changes of s(q)in WS network under three optimization strategies

WU-PowerGrid 網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果如圖9 所示?？梢钥闯?，隨著q值的增加，當(dāng)不采用優(yōu)化策略時，同等規(guī)模HBA 攻擊下s(q)下降比HDA 更快，當(dāng)q=0.2 時HBA 攻擊下s(q)已接近0.1，而HDA 攻擊下q=0.4 時，網(wǎng)絡(luò)基本崩潰，與WS 網(wǎng)絡(luò)相近。這是由于WU-PowerGrid 網(wǎng)絡(luò)與WS 網(wǎng)絡(luò)具有相似的小世界特性。當(dāng)采用Smart Rewiring 與MA 策略優(yōu)化后，s(q)下降有所減緩，在HDA 策略下，當(dāng)q=0.6 時，網(wǎng)絡(luò)完全崩潰。在HBA 策略下，當(dāng)q=0.4 時，網(wǎng)絡(luò)也完全崩潰。當(dāng)采用Community Rewiring 策略時，s(q)下降速度仍介于Smart Rewiring 與MA 策略之間，在HDA 攻擊和HBA 攻擊下，q分別為0.6 和0.4 時網(wǎng)絡(luò)完全崩潰。

圖9 3 種優(yōu)化策略下WU-PowerGrid 網(wǎng)絡(luò)的s(q)變化情況Fig.9 Changes of s(q)in WU-PowerGrid network under three optimization strategies

實(shí)驗(yàn)分別應(yīng)用3種策略對3種網(wǎng)絡(luò)進(jìn)行10次優(yōu)化，網(wǎng)絡(luò)魯棒性的優(yōu)化效果如表2、表3 所示，其中，Rorg為無優(yōu)化時的魯棒性指數(shù)，Ravg為10 次優(yōu)化后的平均魯棒性指數(shù)，ΔR為不同策略對網(wǎng)絡(luò)魯棒性優(yōu)化的提升指數(shù)。由表2、表3 可知，在HDA 攻擊下，Community Rewiring策略對網(wǎng)絡(luò)魯棒性的優(yōu)化率分別達(dá)到59.26%、45.10%和61.37%，在HBA 攻擊下，Community Rewiring 策略對網(wǎng)絡(luò)魯棒性的優(yōu)化率分別達(dá)到88.73%、76.71%和88.93%，優(yōu)化效果均優(yōu)于Smart Rewiring 策略，略劣于MA 策略。在兩種攻擊策略下，MA 策略對網(wǎng)絡(luò)魯棒性的優(yōu)化效果均是最優(yōu)的。

表2 HDA 攻擊下魯棒性優(yōu)化效果Table 2 Optimization effect of robustness under HDA attack

表3 HBA 攻擊下魯棒性優(yōu)化效果Table 3 Optimization effect of robustness under HBA attack

3.2 社區(qū)結(jié)構(gòu)保留的有效性驗(yàn)證

為對社區(qū)結(jié)構(gòu)保留的有效性進(jìn)行驗(yàn)證，在3.1 節(jié)實(shí)驗(yàn)的基礎(chǔ)上對應(yīng)用3 種魯棒性優(yōu)化策略前后的網(wǎng)絡(luò)通過Louvain 算法進(jìn)行社區(qū)結(jié)構(gòu)劃分，分析優(yōu)化過程中3 種魯棒性優(yōu)化策略下社區(qū)結(jié)構(gòu)保留程度評價指標(biāo)NMI 的變化情況，并基于3 種魯棒性優(yōu)化策略對初始網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)特征的保留程度進(jìn)行對比。

BA 網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果如圖10 所示?？梢钥闯觯寒?dāng)采用MA 策略時，在1 000 次迭代后，NMI 指數(shù)接近0.3；當(dāng)采用Smart Rewiring 策略時，在1 000 次迭代后，NMI 指數(shù)略低于0.4；當(dāng)采用Community Rewiring 策略時，在1 000 次迭代后，NMI 指數(shù)仍接近0.6。

圖10 3 種優(yōu)化策略下BA 網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)保留情況Fig.10 Reservation of BA network community structure under three optimization strategies

WS 網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果如圖11 所示?？梢钥闯觯寒?dāng)采用Smart Rewiring 和MA 策略時，在1 000 次迭代后，NMI 指數(shù)略低于0.6；當(dāng)采用Community Rewiring策略時，NMI 指數(shù)仍維持在0.7。WU-PowerGrid 網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果如圖12 所示。可以看出：當(dāng)采用Smart Rewiring 和MA 策略時，在1 000 次迭代后，NMI 指數(shù)略高于0.6；當(dāng)采用Community Rewiring 策略時，NMI指數(shù)仍維持在0.7 以上。

圖11 3 種優(yōu)化策略下WS 網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)保留情況Fig.11 Reservation of WS network community structure under three optimization strategies

圖12 3 種優(yōu)化策略下WU-PowerGrid 網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)保留情況Fig.12 Reservation of WU-PowerGrid network community structure under three optimization strategies

應(yīng)用3 種策略對3 種網(wǎng)絡(luò)進(jìn)行10 次優(yōu)化，網(wǎng)絡(luò)初始社區(qū)結(jié)構(gòu)的保留效果如表4 所示，其中，NMIavg為每種策略優(yōu)化10 次后網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)保留程度的平均指數(shù)，ΔNMI 為Community Rewiring 策略對網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)保留程度的優(yōu)化相比Smart Rewiring 和MA 兩種策略的提升指數(shù)。

表4 社區(qū)結(jié)構(gòu)保留效果Table 4 Retention effect of community structure

由表4 可知：相比Smart Rewiring 策略，Community Rewiring 策略對社區(qū)結(jié)構(gòu)保留的提升率分別達(dá)到了51.11%、21.34%和23.41%；相比MA 策略，Community Rewiring 策略對社區(qū)結(jié)構(gòu)保留的提升率分別達(dá)到了79.15%、25.93%和29.03%。在3 種策略中，Community Rewiring 策略對網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)保留程度最高，而Smart Rewiring策略下社區(qū)結(jié)構(gòu)的保留程度優(yōu)于MA策略，MA策略對網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)破壞程度最大。

3.3 結(jié)論與分析

由以上實(shí)驗(yàn)結(jié)果可看出：在3 種魯棒性優(yōu)化策略中，Community Rewiring 策略對網(wǎng)絡(luò)魯棒性的優(yōu)化效果優(yōu)于Smart Rewiring 策略，略劣于MA 策略；Community Rewiring 策略對初始網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)保留效果優(yōu)于Smart Rewiring 和MA 策略。

在3 種策略下，s（q）下降趨勢不同，即魯棒性優(yōu)化效果不同的原因在于：Smart Rewiring 策略基于節(jié)點(diǎn)的鄰居信息與簡單的貪心策略選擇重連邊組合，MA 策略基于MA-RSFMA算法設(shè)計全局搜索算子，在無約束條件下搜索最優(yōu)的重連邊組合，而Community Rewiring策略在單個社區(qū)中采用了類似全局搜索的模擬退火算法，在社區(qū)間優(yōu)化時采用了改進(jìn)的Smart Rewiring策略。因此，MA 策略下s（q）下降最慢，對網(wǎng)絡(luò)魯棒性優(yōu)化效果最好，Smart Rewiring 策略下s（q）下降最快，Community Rewiring 策略居中。同時，在3 種策略下初始社區(qū)結(jié)構(gòu)保留程度不同的原因在于：在相同的迭代次數(shù)下，MA 策略相比Smart Rewiring 策略優(yōu)化效果更好，可搜索到更多使網(wǎng)絡(luò)魯棒性提升的重連邊組合，網(wǎng)絡(luò)拓?fù)涞母淖兇螖?shù)更多，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)變化更大，而Community Rewiring 策略將優(yōu)化過程分為社區(qū)內(nèi)優(yōu)化與社區(qū)間優(yōu)化，有效地減少了重連邊對網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的改變。因此，MA 策略下初始社區(qū)結(jié)構(gòu)被破壞最嚴(yán)重，Smart Rewiring 策略居中，Community Rewiring 策略下初始社區(qū)結(jié)構(gòu)保留最完整?；谝陨辖Y(jié)論與分析得出，本文所提Community Rewiring 策略在達(dá)到接近MA 策略的魯棒性優(yōu)化效果的同時能更好地保持網(wǎng)絡(luò)初始社區(qū)結(jié)構(gòu)。

4 結(jié)束語

針對傳統(tǒng)復(fù)雜網(wǎng)絡(luò)魯棒性優(yōu)化策略中重連邊破壞網(wǎng)絡(luò)初始社區(qū)結(jié)構(gòu)的問題，本文提出一種結(jié)合社區(qū)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)魯棒性優(yōu)化策略。該策略基于模擬退火算法優(yōu)化單個社區(qū)的內(nèi)部魯棒性，利用改進(jìn)的Smart Rewiring 策略優(yōu)化社區(qū)間的連接魯棒性。在模擬網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果表明，該策略能在優(yōu)化網(wǎng)絡(luò)魯棒性的同時有效地保持網(wǎng)絡(luò)初始社區(qū)結(jié)構(gòu)。下一步將在優(yōu)化網(wǎng)絡(luò)魯棒性的同時考慮更多的真實(shí)網(wǎng)絡(luò)特性，使復(fù)雜網(wǎng)絡(luò)魯棒性優(yōu)化策略在真實(shí)網(wǎng)絡(luò)中更具普適性。