基于自然連通度的復雜網絡抗毀性仿真優化研究

田 田，吳 俊，譚躍進

（1.中國人民解放軍總后勤部油料研究所，北京 102300；2.國防科技大學信息系統與管理學院，長沙 410073）

基于自然連通度的復雜網絡抗毀性仿真優化研究

田 田1，吳 俊2，譚躍進2

（1.中國人民解放軍總后勤部油料研究所，北京 102300；2.國防科技大學信息系統與管理學院，長沙 410073）

建立了以自然連通度為目標函數的復雜網絡抗毀性組合優化模型，進而提出了基于禁忌搜索的復雜網絡抗毀性仿真優化算法，設計了變量編碼、定義了移動操作、給出了特赦準則、設置了終止準則，給出了算法流程，最后基于仿真優化結果分析了最優抗毀性網絡的結構屬性，研究表明最優抗毀性網絡呈現出明顯的同配度關聯模式，核心節點之間相互連接緊密形成“富人俱樂部”。

復雜網絡；抗毀性；自然連通度；禁忌搜索；仿真優化

0 引言

因特網、交通網、電力網、通信網、物流網……，可以說，我們生活在一個網絡的世界，這些我們賴以生存的網絡越來越龐大，越來越復雜［1-7］。但面對越來越頻繁發生的事故，我們不得不開始關注：這些復雜的網絡系統到底有多可靠？一些微不足道的故障是否會導致整個網絡系統的崩潰？在發生嚴重自然災害或者敵對勢力蓄意破壞的情況下，這些網絡是否還能正常發揮作用？這一系列嚴峻的問題擺在我們面前，使得復雜網絡系統的抗毀性研究刻不容緩、意義重大［8-10］。

網絡抗毀性研究最早源于圖論，早期主要應用于通信網絡領域。點（邊）連通度是最早被用來刻畫網絡抗毀性的測度指標［11］，它被定義為使得圖變成不連通或平凡圖所需去掉的最少節點（邊）數。顯然，點（邊）連通度存在明顯缺陷，它僅僅考慮了網絡被破壞的難易程度，卻未考慮網絡遭受破壞的嚴重程度，之后很多測度被提出來彌補這個不足。例如，堅韌度［12］、完整度［13］、粘連度［14］、離散數［15］、膨脹系數［16］、核度［17-18］等等。這些改進的抗毀性測度不僅刻畫了網絡被破壞的難易程度還刻畫了網絡遭受破壞的嚴重程度。但是，由于這些測度指標追求對抗毀性的精確刻畫而導致絕大多數指標的計算都是NP問題［19］。這意味著從計算復雜性角度來看，基于傳統圖論的抗毀性測度很難適用大規模復雜網絡系統。

為了解決復雜網絡抗毀性測度的計算復雜性以及度量精確性問題，吳俊等［20-21］最近提出建立了復雜網絡抗毀性的譜測度理論與方法，所提出的自然連通度從復雜網絡的內部結構屬性出發，通過計算網絡中不同長度閉環數目的加權和，刻畫了網絡中替代途徑的冗余性，在數學形式上表示為一種特殊形式的平均特征根，可以從網絡鄰接矩陣特征譜直接導出，因此具有明確的物理意義和簡潔的數學形式。相關成果發表不到一年立即得到學術界同行的關注，例如：復雜性研究領域知名學者Estrada教授對自然連通度作了詳細介紹［22］，美國德克薩斯大學學者Shang跟蹤研究了加權網絡的自然連通度［23］以及局域自然連通度［24］。

復雜網絡抗毀性研究需要回答以下3個科學問題：怎樣度量復雜網絡的抗毀性？什么樣的復雜網絡抗毀性好？怎樣得到抗毀性好的復雜網絡？其中，第1個問題，即復雜網絡抗毀性的建模問題是基礎；第2個問題，即復雜網絡抗毀性的分析問題，是關鍵；第3個問題，即復雜網絡抗毀性的優化問題，是核心，這也正是本文關注的問題。本文首先介紹復雜網絡的自然連通度，在此基礎上提出以自然連通度為目標函數的復雜網絡抗毀性組合優化模型，進而提出基于禁忌搜索的復雜網絡抗毀性仿真優化算法，最后分析最優抗毀性復雜網絡的結構屬性。

1 復雜網絡的自然連通度

復雜網絡在數學上可以描述成一個圖G= （V，E），其中V= ｛v1，v2，v3…，vN｝表示節點集合，E= ｛e1，e2，e3，…，eW｝?V×V表示邊的集合，N=｜V｜表示節點數量，W=｜E｜表示邊數量。簡單無權圖G可以用鄰接矩陣A（G）=（aij）M×N表示，其中aii=0，若vi與vj之間存在邊則aij=1，否則aij=0。假設G為無向圖，則A（G）為對稱矩陣，即aij=aij。令λ1≥λN≥…≥λN為A（G）的特征根，稱集合｛λi｝為圖G的鄰接矩陣特征譜。

稱圖G= （V，E）中節點和邊的交替序列w=v0e1v1e2…ekvk為途徑，其中vi∈V，ei= （vi-1，vi）∈E，k為途徑w的長度，簡單圖中的途徑w可簡寫為v0v1…vk。若途徑w中v0=vk則稱w為閉途徑。考慮圖1中節點v1和v6之間的途徑數目。在圖1a中，v1和v6之間長度為1和2的途徑數目為零；長度為3的途徑有4條：v1v2v4v6，v1v3v5v6，v1v2v5v6，v1v3v4v6；長 度 為 4 的 途 徑 有 8 條：v1v2v3v5v6，v1v2v4v5v6，v1v3v5v4v6，v1v3v2v4v6，v1v2v5v4v6，v1v3v4v5v6，v1v2v3v4v6，v1v3v2v5v6。在圖1b中，v1和v6之間長度為1，2和4的途徑數目為零；長度為3的途徑有2條：v1v2v4v6，v1v3v5v6。顯然，圖1 a中v1和v6之間連接的抗毀性更強，因為兩個節點之間存在更多的替代途徑，當網絡中部分節點或者邊失效后，v1和v6之間還能繼續保持連通。

通過圖1的例子可以看出，節點之間連接的抗毀性來源于節點之間替代途徑的冗余性。由此可以認為網絡的抗毀性來源于網絡中替代途徑的冗余性。那么，如何度量網絡中替代途徑的冗余性呢？直觀上來說，可以統計任意節點對vi?vj之間長度為k的途徑數目n，然后對i，j，k求和

圖1 網絡中的途徑數目示意圖Fig.1 Illustration of number of walks

其中，nk表示網絡中所有長度為k的閉途徑數目。S越大，說明網絡中替代路徑的冗余性越高，網絡的抗毀性就越強。注意到網絡中的途徑允許節點和邊重復，這意味著閉途徑的長度可以為任意長度，因此S→∞。為了克服這個問題，考慮對nk進行加權，即

選擇這樣加權有3方面原因：1）越長的途徑被重復計算的次數越多，例如網絡中一條邊在計算長度為2的閉途徑時被重復計算了2次，網絡中一個三角形在計算長度為3的閉途徑時被重復計算了6次；2）越長的途徑對網絡抗毀性貢獻越小；3）保證S收斂。為了化簡式（3），先給出一個引理。

這表明閉途徑數目的加權和可通過特征譜直接得到。注意到當N很大時S將是一個龐大的數字，考慮對S重新標度，并記為

定義1 稱

為圖G的自然連通度，其中λi為圖G鄰接矩陣A（G）的特征根。

2 基于自然連通度的復雜網絡抗毀性組合優化模型

2.1 目標函數

目標函數是優化問題的關鍵，不同的目標函數將得到不同的優化結果。此外，目標函數也決定了優化的效率。對于大規模復雜網絡，如果選擇基于圖論的抗毀性指標將很難執行優化過程。從定義1可知，自然連通度可以直接從網絡鄰接矩陣的特征譜導出，在數學形式上表示為一種特殊形式的平均特征根，具有明確的物理意義和簡潔的數學形式并且計算簡單。此外，自然連通度關于添加邊或移除邊是嚴格單調的［20-21］，這意味著自然連通度能夠精確刻畫網絡抗毀性的細微差別。通過與其他抗毀性測度比較，發現自然連通度能夠準確、清晰地刻畫出復雜網絡抗毀性的演化，得到的結果與直觀判斷相符，而且對于不連通圖仍然有效［20-21］。

因此，本文選擇既精確又便于計算的自然連通度作為復雜網絡抗毀性優化的目標函數。

2.2 約束條件

網絡的抗毀性受很多因素的影響，其中最主要的因素是網絡中邊的數目。由于自然連通度關于添加邊是嚴格單調遞增的，這意味著如果沒有邊的數量限制，完全圖將是抗毀性最優的網絡。但是，構造一個網絡總是有一定成本約束的，邊的數量越多網絡的成本越大。因此，本文將網絡中邊的數量作為約束條件，即研究邊的數量給定的條件下，如何使得網絡的抗毀性最優。邊的數量約束可以通過鄰接矩陣表示

2.3 優化模型

根據前面討論的目標函數以及約束條件，可以得到復雜網絡抗毀性優化模型為

顯然，這是一個典型的組合優化問題。

3 基于禁忌搜索的復雜網絡抗毀性仿真優化算法

考慮到現代啟發式方法是解決復雜組合優化問題的有效工具，本文采用現代啟發式方法中的新成員——禁忌搜索（Tabu Search，TS）算法［26-27］來求解式（8）所描述的組合優化模型。禁忌搜索是局部領域搜索的一種擴展，通過局部鄰域搜索機制和相應的禁忌準則來避免迂回搜索，并通過特赦準則來赦免一些被禁忌的優良解，進而保證多樣化的有效探索以最終實現全局優化。

3.1 變量編碼

由式（8）中的約束條件可知，只需要優化鄰接矩陣中對角線以上的N（N-1）/2個元素aij（i＜j）。把這N（N-1）/2個元素重新排列，記為xi，其中xi=0或xi=1，∑ixi=W。將xi作為禁忌搜索算法的優化變量，即解的編碼。

3.2 移動操作

禁忌搜索是局部鄰域搜索的一種擴展，因此解的移動操作設計非常關鍵，它決定了當前解鄰域的產生形式和數目以及各個解之間的聯系。本文選擇邊隨機重連作為移動操作，其算法為：

Step 1隨機移除一條邊，即在xi中隨機選擇一個等于1的變量令其等于0；

Step 2隨機添加一條邊，即在xi中隨機選擇一個等于0的變量令其等于1。

對于每一個當前解，通過邊隨機重連產生ncandidate個新網絡作為當前解的候選解集。

3.3 特赦準則

特赦準則設置是算法避免遺失優良解，激勵對優良解的局部搜索，進而實現全局優化的關鍵步驟。在禁忌搜索過程中，可能會出現一個被禁忌候選解的目標函數優于當前解，此時解禁該禁忌候選解，以實現更高的優化性能。

3.4 終止準則

通常終止準則選擇為是否達到預定的最大迭代次數，而這種預定的最大迭代次數一般是根據經驗確定。顯然，迭代次數的多少應與尋優問題規模有關。憑經驗給定最大迭代次數可能會產生兩類問題：1）優化過程早己達到最優解，但是沒有達到最大迭代次數，優化過程還要做不必要的迭代計算；2）優化過程己經達到最大迭代次數，但尚未達到最優解就退出優化過程。為了克服上述問題，采用最優解連續保持不變是否達到最大持續迭代步數niteration作為終止準則。

3.5 算法流程

具體的基于禁忌搜索的復雜網絡抗毀性仿真優化算法：

Step 1初始化算法：設置禁忌表長度L、候選解集規模ncandidate以及最大持續迭代步數niteration；置禁忌表為空。

Step 2產生初始解G0：先置xi：=0，然后從中隨機選取W 個變量置其等于1；置最優解G＊：=G0，置當前解Gnow：=G0；

Step 3判斷終止準則是否滿足，若是，則結束算法并輸出優化結果；否則，繼續以下步驟。

Step 4生成候選解集：通過邊隨機重連產生ncandidate個新網絡，若產生的新網絡不連通，則重新選擇；計算每個新網絡的自然連通度。

Step 5如果自然連通度最大的候選解不是被禁忌的，或者被禁忌的但滿足特ncandidate=10赦準則，那么就把該候選解作為新的當前解Gnow；否則，選擇不被禁忌的最好移動所對應的候選解作為當前解Gnow，并將該候選解加入禁忌表；如果當前解Gnow的自然連通度大于最優解，則置最優解G＊：=Gnow。

Step 6轉Step 3。

4 仿真分析結果

基于本文的禁忌搜索仿真優化算法分析優化過程以及最優抗毀性網絡的各種結構屬性。仿真優化參數為：節點數量N=100，邊的數量W=300，禁忌表長度L=10、候選解集規模以及最大持續迭代步數niteration=30。

4.1 自然連通度

圖2給出了自然連通度隨迭代次數n的變化圖。

由圖2可見，自然連通度隨著迭代次數的增加而快速增加，從初始值2.84經過582次迭代后達到穩定最優值11.05。這說明本文提出的基于禁忌搜索的復雜網絡抗毀性仿真優化算法能有效地優化復雜網絡的抗毀性。作為參考，在圖2中還給出了具有相同節點數量以及邊數量的BA無標度網絡（實線）、規則環狀格子（虛線）、ER隨機網絡（點劃線）的自然連通度。可以看出，通過優化得到的網絡抗毀性遠遠高于這些典型網絡。

4.2 度關聯性

度關聯性刻畫的是網絡中不同度節點之間的微觀連接模式。如果度大的節點傾向于連接度大的節點，則稱網絡是同配的；反之，如果度大的節點傾向于和度小的節點連接，則稱網絡是異配的。度關聯性可用節點度的Pearson相關系數描述［28］。

圖2 自然連通度隨迭代次數變化圖Fig.2 The change of natural connectivity with the number of iterations

其中，uk、vk分別為連接第k條邊的兩個節點的度，W 為網絡的總邊數。r的取值范圍為-1≤r≤1，當r＞0時，網絡是同配的；當r＜0時，網絡是異配的；當r=0時，網絡是不相關的。

圖3給出了度關聯系數隨迭代次數n的變化圖。可以看出，度關聯系數隨著迭代次數的增加呈震蕩上升趨勢，最優網絡的度關聯系數達到0.25，呈現出明顯的同配關聯模式，即度大的核心節點傾向于和度大的核心節點相連接，度小的末梢節點傾向于和度小的末梢節點相連接。作為參考，在圖3中給出了具有相同節點數量以及邊數量的BA無標度網絡（實線）、規則環狀格子（虛線）、ER隨機網絡（點劃線）的度關聯系數。可以看出，BA無標度網絡呈現出明顯的異配關聯模式，規則環狀格子和隨機網絡的度關聯系數接近0，即不存在明顯的度關聯，通過優化得到的度關聯系數明顯高于這些典型網絡。

4.3 拓撲結構圖

為了直觀展現最優抗毀性網絡的結構屬性，在圖4中給出了最優抗毀性網絡的拓撲結構圖（圖4a）。作為參考，在圖4中還給出了具有相同節點數量以及邊數量的BA無標度網絡（圖4b）、規則環狀格子（圖4 c）、ER隨機網絡（圖4d）的拓撲結構圖。可以看出，最優抗毀性網絡的拓撲結構圖與其他幾個典型網絡有很大不同。在最優抗毀性網絡中存在少量度非常大的核心節點，而且這些核心節點之間相互連接緊密形成“富人俱樂部”。除了這些核心節點以外，其他節點的度都很小，而且這些度很小的末梢節點傾向于在外圍互相連接。

圖3 度關聯系數隨迭代次數變化圖Fig.3 The change of degree correlation coefficient with the number of iterations

圖4 最優抗毀性網絡的拓撲結構Fig.4 The network topology with optimal invulaer-ability

5 結束語

本文圍繞“怎樣得到抗毀性好的復雜網絡”研究了復雜網絡抗毀性的仿真優化問題，主要工作包括：1）建立了以自然連通度為目標函數，以邊的數量為約束條件的復雜網絡抗毀性組合優化模型；2）提出了基于禁忌搜索的復雜網絡抗毀性仿真優化算法，設計了變量編碼、定義了移動操作、給出了特赦準則、設置了終止準則，給出了算法流程；3）分析了最優抗毀性網絡的若干結構屬性，研究表明最優抗毀性網絡呈現出明顯的同配度關聯模式，核心節點之間相互連接緊密形成“富人俱樂部”，度很小的末梢節點傾向于在外圍互相連接。

值得指出的是，本文研究的是復雜網絡抗毀性的全局優化問題，即在一定費用約束條件下如何構造出抗毀性更好的網絡。但是，很多情況下面對的都是已經存在的網絡。這意味著不可能全部“重新洗牌”，只能局部優化網絡結構。在這種情況下，如何通過最少的優化達到最大的抗毀性是我們下一步需要研究的問題。

［1］方錦清，汪小帆，劉曾榮.略論復雜性問題和非線性復雜網絡系統的研究［J］.科技導報，2004，22（2）：9-12，64.

Fang Jinqing，Wang Xiaofan，Liu Zengrong.On the study of complexity and nonlinear complex networks［J］.Science &Technology Review，2004，22（2）：9-12，64.

［2］方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉科學：網絡科學（上）［J］.物理學進展，2007，27（3）：239-343.

Fang Jinqing，Wang Xiaofan，Zheng Zhigang，et al.New interdisciplinary science：networks science（I）［J］.Progress in Physics，2007，27（3）：239-343.

［3］方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉科學：網絡科學（下）［J］.物理學進展，2007，27（4）：361-448.

Fang Jinqing，Wang Xiaofan，Zheng Zhigang，et al.New interdisciplinary science：networks science（I）［J］.Progress in Physics，2007，27（4）：361-448.

［4］陳禹.人類對于網絡的認識的新發展［J］.系統辯證學報，2005，13（4）：18-22.

Chen Yu.New progress on the network for the human being［J］.Journal of systemic dialectics，13（4）：18-22.

［5］史定華.網絡——探索復雜性的新途徑［J］.系統工程學報，2005，20（2）：115-119.

Shi Dinghua.Networks—a new approach for exploring complexity［J］.Journal of System Engineering，2005，20（2）：115-119.

［6］汪秉宏，周濤，何大韌.統計物理學與復雜系統研究最新發展趨勢分析［J］.中國基礎科學，2005，7（3）：37-43

Wang Binghong，Zhou Tao，He Daren.The trend of recent research on statistical physics and complex systems［J］.China Basic Science，2005，7（3）：37-43.

［7］汪小帆，李翔，陳關榮.復雜網絡理論及其應用［M］.北京：清華大學出版社，2006.

［8］譚躍進，吳俊，鄧宏鐘.復雜網絡抗毀性研究綜述［J］.系統工程，2006，24（11）：1-5.

Tan Yuejin，Wu Jun，Deng Hongzhong.Invulnerability of complex networks：a survey［J］.System Engineering，2006，24（11）：1-5.

［9］吳俊，譚躍進.復雜網絡抗毀性測度研究［J］.系統工程學報，2005，20（2）：128-131.

Wu Jun，Tan Yuejin.Study on measure of complex network invulnerability［J］.Journal of System Engineering，2005，20（2）：128-131.

［10］譚躍進，呂欣，吳俊，等.復雜網絡抗毀性研究若干問題的思考［J］.系統工程理論與實踐，2008，28（Suppl）：116-120.

Tan Yuejin，LüXin，Wu Jun，et al.On the invulnerability research of complex networks［J］.Systems Engineering-Theory &Practice，2008，28（Suppl）：116-120.

［11］Frank H，Frisch I T.Analysis and design of survivable network［J］.IEEE Transaction on Communication Technology，1970，COM-18（5）：567-662.

［12］Chvatal V.Tough graphs and hamiltonian circuits［J］.Discrete Mathematics，1973，5（3）：215-228.

［13］Barefoot C A，Entringer R，Swart H.Vulnerability in graphs-a comparative survey［J］.J Combin Math Combin Comput，1987，1（2）：13-22.

［14］Cozzens M，Moazzami D，Stueckle S.The tonaeity of a graph［C］//Seventh International Conference on the Theory and Applications of Graphs.New York：Wiley，1995：1111-1122.

［15］Jung H A.On a class of posets and the corresponding comparability graphs［J］.J Combin Theory B，1978，24（2）：125-133.

［16］Bassalygo L A，Pinsker M S.The complexity of an optimal non-blocking commutation scheme without reorganization［J］.Problemy Peredaci Informacii，1973，9（1）：84-87.

［17］許進.系統的核與核度理論Ⅱ——優化設計與可靠通訊網絡［J］.系統工程學報，1994，9（1）：1-11.

Xu Jin.The core and coritivity of a system Ⅱ—optimization design and reliable communication network［J］.Journal of System Engineering，1994，9（1）：1-11.

［18］許進，席酉民.系統的核與核度［J］.系統科學與數學，1993，13（2）：102-110.

Xu Jin，Xi YouMin.The core and coritivity of a system［J］.System and Mathematics，1993，13（2）：102-110.

［19］Kratsch D.Measuring the vulnerability for classes of intersection graphs［J］.Discr App Math，1997，77（3）：259-270.

［20］Wu J，Barahona M，Tan Y J，Deng H Z.Natural connectivity of complex networks［J］.Chinese Physics Letters，2010，27（7）：078902.

［21］Wu J，Barahona M，Tan Y J，et al.Spectral measure of structural robustness in complex networks［J］.Ieee Transactions on Systems Man and Cybernetics Part A-Systems and Humans，2011，41（6）：1244-1252.

［22］Estrada E，Hatano N，Benzi M.The physics of communicability in complex networks［J］.Phys Rep，2012，514（3）：89-119.

［23］Shang Y L.Perturbation results for the Estrada index in weighted networks［J］.Journal of Physics，2011，44（7）：075003.

［24］Shang Y L.Local natural connectivity in complex networks［J］.Chinese Physics Letters，2011，28（6）：068903.

［25］Cvetkovic′D M，Doob M，Sachs H.Spectra of Graphs［M］.New York：Academic Press，1979.

［26］Glover F.Tabu Search-Part II［J］.ORSA Journal on Computing，1990，2（1）：4-32.

［27］Glover F.Tabu Search-Part I［J］.ORSA Journal on Computing，1989，1（3）：190-206.

［28］Newman M E J.Assortative mixing in networks［J］.Physical Review Letters，2002，89（20）：20871.

Simulation Optimization for Invulnerability of Complex Networks Based on Natural Connectivity

TIAN Tian1，WU Jun2，TAN Yue-jin2
（1.POL Research Institute of General Logistics Pepartment，PLA，Beijing 102300，China；2.College of Information Systems and Management，National University of Defense Technology，Changsha 410073，China）

A combinatorial optimization model for invulnerability of complex networks is established，in which the natural connectivity is the objective function and the number of edges is the constraint condition.Following the combinatorial optimization model，a simulation optimization method for invulnerability of complex network topologies based on tabu search is proposed and variables coding，moving operation，aspiration criterion，stopping criterion，algorithm procedures are provided.Lastly，the structural properties of the optimal network topology are investigated based on the simulation results.The results show that the optimal networks with invulnerability have obvious homogenous correlation.Tight connection exists among hub nodes and forms“rich club”.

complex networks；invulnerability；natural connectivity；tabu search；simulation optimization

N949

A

1672-3813（2013）02-0088-07

2013-03-14

國家自然科學基金（60904065，71031007，71171195）；新世紀優秀人才支持計劃（NCET-12-0141）

田田（1979-），男，黑龍江哈爾濱人，碩士，工程師，主要研究方向為計算機工程。

（責任編輯 耿金花）