基于自然連通度的復(fù)雜網(wǎng)絡(luò)抗毀性仿真優(yōu)化研究

田 田，吳 俊，譚躍進(jìn)

（1.中國(guó)人民解放軍總后勤部油料研究所，北京 102300；2.國(guó)防科技大學(xué)信息系統(tǒng)與管理學(xué)院，長(zhǎng)沙 410073）

基于自然連通度的復(fù)雜網(wǎng)絡(luò)抗毀性仿真優(yōu)化研究

田 田1，吳 俊2，譚躍進(jìn)2

（1.中國(guó)人民解放軍總后勤部油料研究所，北京 102300；2.國(guó)防科技大學(xué)信息系統(tǒng)與管理學(xué)院，長(zhǎng)沙 410073）

建立了以自然連通度為目標(biāo)函數(shù)的復(fù)雜網(wǎng)絡(luò)抗毀性組合優(yōu)化模型，進(jìn)而提出了基于禁忌搜索的復(fù)雜網(wǎng)絡(luò)抗毀性仿真優(yōu)化算法，設(shè)計(jì)了變量編碼、定義了移動(dòng)操作、給出了特赦準(zhǔn)則、設(shè)置了終止準(zhǔn)則，給出了算法流程，最后基于仿真優(yōu)化結(jié)果分析了最優(yōu)抗毀性網(wǎng)絡(luò)的結(jié)構(gòu)屬性，研究表明最優(yōu)抗毀性網(wǎng)絡(luò)呈現(xiàn)出明顯的同配度關(guān)聯(lián)模式，核心節(jié)點(diǎn)之間相互連接緊密形成“富人俱樂(lè)部”。

復(fù)雜網(wǎng)絡(luò)；抗毀性；自然連通度；禁忌搜索；仿真優(yōu)化

0 引言

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

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

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

復(fù)雜網(wǎng)絡(luò)抗毀性研究需要回答以下3個(gè)科學(xué)問(wèn)題：怎樣度量復(fù)雜網(wǎng)絡(luò)的抗毀性？什么樣的復(fù)雜網(wǎng)絡(luò)抗毀性好？怎樣得到抗毀性好的復(fù)雜網(wǎng)絡(luò)？其中，第1個(gè)問(wèn)題，即復(fù)雜網(wǎng)絡(luò)抗毀性的建模問(wèn)題是基礎(chǔ)；第2個(gè)問(wèn)題，即復(fù)雜網(wǎng)絡(luò)抗毀性的分析問(wèn)題，是關(guān)鍵；第3個(gè)問(wèn)題，即復(fù)雜網(wǎng)絡(luò)抗毀性的優(yōu)化問(wèn)題，是核心，這也正是本文關(guān)注的問(wèn)題。本文首先介紹復(fù)雜網(wǎng)絡(luò)的自然連通度，在此基礎(chǔ)上提出以自然連通度為目標(biāo)函數(shù)的復(fù)雜網(wǎng)絡(luò)抗毀性組合優(yōu)化模型，進(jìn)而提出基于禁忌搜索的復(fù)雜網(wǎng)絡(luò)抗毀性仿真優(yōu)化算法，最后分析最優(yōu)抗毀性復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)屬性。

1 復(fù)雜網(wǎng)絡(luò)的自然連通度

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

稱圖G= （V，E）中節(jié)點(diǎn)和邊的交替序列w=v0e1v1e2…ekvk為途徑，其中vi∈V，ei= （vi-1，vi）∈E，k為途徑w的長(zhǎng)度，簡(jiǎn)單圖中的途徑w可簡(jiǎn)寫為v0v1…vk。若途徑w中v0=vk則稱w為閉途徑。考慮圖1中節(jié)點(diǎn)v1和v6之間的途徑數(shù)目。在圖1a中，v1和v6之間長(zhǎng)度為1和2的途徑數(shù)目為零；長(zhǎng)度為3的途徑有4條：v1v2v4v6，v1v3v5v6，v1v2v5v6，v1v3v4v6；長(zhǎng) 度 為 4 的 途 徑 有 8 條：v1v2v3v5v6，v1v2v4v5v6，v1v3v5v4v6，v1v3v2v4v6，v1v2v5v4v6，v1v3v4v5v6，v1v2v3v4v6，v1v3v2v5v6。在圖1b中，v1和v6之間長(zhǎng)度為1，2和4的途徑數(shù)目為零；長(zhǎng)度為3的途徑有2條：v1v2v4v6，v1v3v5v6。顯然，圖1 a中v1和v6之間連接的抗毀性更強(qiáng)，因?yàn)閮蓚€(gè)節(jié)點(diǎn)之間存在更多的替代途徑，當(dāng)網(wǎng)絡(luò)中部分節(jié)點(diǎn)或者邊失效后，v1和v6之間還能繼續(xù)保持連通。

通過(guò)圖1的例子可以看出，節(jié)點(diǎn)之間連接的抗毀性來(lái)源于節(jié)點(diǎn)之間替代途徑的冗余性。由此可以認(rèn)為網(wǎng)絡(luò)的抗毀性來(lái)源于網(wǎng)絡(luò)中替代途徑的冗余性。那么，如何度量網(wǎng)絡(luò)中替代途徑的冗余性呢？直觀上來(lái)說(shuō)，可以統(tǒng)計(jì)任意節(jié)點(diǎn)對(duì)vi?vj之間長(zhǎng)度為k的途徑數(shù)目n，然后對(duì)i，j，k求和

圖1 網(wǎng)絡(luò)中的途徑數(shù)目示意圖Fig.1 Illustration of number of walks

其中，nk表示網(wǎng)絡(luò)中所有長(zhǎng)度為k的閉途徑數(shù)目。S越大，說(shuō)明網(wǎng)絡(luò)中替代路徑的冗余性越高，網(wǎng)絡(luò)的抗毀性就越強(qiáng)。注意到網(wǎng)絡(luò)中的途徑允許節(jié)點(diǎn)和邊重復(fù)，這意味著閉途徑的長(zhǎng)度可以為任意長(zhǎng)度，因此S→∞。為了克服這個(gè)問(wèn)題，考慮對(duì)nk進(jìn)行加權(quán)，即

選擇這樣加權(quán)有3方面原因：1）越長(zhǎng)的途徑被重復(fù)計(jì)算的次數(shù)越多，例如網(wǎng)絡(luò)中一條邊在計(jì)算長(zhǎng)度為2的閉途徑時(shí)被重復(fù)計(jì)算了2次，網(wǎng)絡(luò)中一個(gè)三角形在計(jì)算長(zhǎng)度為3的閉途徑時(shí)被重復(fù)計(jì)算了6次；2）越長(zhǎng)的途徑對(duì)網(wǎng)絡(luò)抗毀性貢獻(xiàn)越??；3）保證S收斂。為了化簡(jiǎn)式（3），先給出一個(gè)引理。

這表明閉途徑數(shù)目的加權(quán)和可通過(guò)特征譜直接得到。注意到當(dāng)N很大時(shí)S將是一個(gè)龐大的數(shù)字，考慮對(duì)S重新標(biāo)度，并記為

定義1 稱

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

2 基于自然連通度的復(fù)雜網(wǎng)絡(luò)抗毀性組合優(yōu)化模型

2.1 目標(biāo)函數(shù)

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

因此，本文選擇既精確又便于計(jì)算的自然連通度作為復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化的目標(biāo)函數(shù)。

2.2 約束條件

網(wǎng)絡(luò)的抗毀性受很多因素的影響，其中最主要的因素是網(wǎng)絡(luò)中邊的數(shù)目。由于自然連通度關(guān)于添加邊是嚴(yán)格單調(diào)遞增的，這意味著如果沒(méi)有邊的數(shù)量限制，完全圖將是抗毀性最優(yōu)的網(wǎng)絡(luò)。但是，構(gòu)造一個(gè)網(wǎng)絡(luò)總是有一定成本約束的，邊的數(shù)量越多網(wǎng)絡(luò)的成本越大。因此，本文將網(wǎng)絡(luò)中邊的數(shù)量作為約束條件，即研究邊的數(shù)量給定的條件下，如何使得網(wǎng)絡(luò)的抗毀性最優(yōu)。邊的數(shù)量約束可以通過(guò)鄰接矩陣表示

2.3 優(yōu)化模型

根據(jù)前面討論的目標(biāo)函數(shù)以及約束條件，可以得到復(fù)雜網(wǎng)絡(luò)抗毀性優(yōu)化模型為

顯然，這是一個(gè)典型的組合優(yōu)化問(wèn)題。

3 基于禁忌搜索的復(fù)雜網(wǎng)絡(luò)抗毀性仿真優(yōu)化算法

考慮到現(xiàn)代啟發(fā)式方法是解決復(fù)雜組合優(yōu)化問(wèn)題的有效工具，本文采用現(xiàn)代啟發(fā)式方法中的新成員——禁忌搜索（Tabu Search，TS）算法［26-27］來(lái)求解式（8）所描述的組合優(yōu)化模型。禁忌搜索是局部領(lǐng)域搜索的一種擴(kuò)展，通過(guò)局部鄰域搜索機(jī)制和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索，并通過(guò)特赦準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良解，進(jìn)而保證多樣化的有效探索以最終實(shí)現(xiàn)全局優(yōu)化。

3.1 變量編碼

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

3.2 移動(dòng)操作

禁忌搜索是局部鄰域搜索的一種擴(kuò)展，因此解的移動(dòng)操作設(shè)計(jì)非常關(guān)鍵，它決定了當(dāng)前解鄰域的產(chǎn)生形式和數(shù)目以及各個(gè)解之間的聯(lián)系。本文選擇邊隨機(jī)重連作為移動(dòng)操作，其算法為：

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

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

對(duì)于每一個(gè)當(dāng)前解，通過(guò)邊隨機(jī)重連產(chǎn)生ncandidate個(gè)新網(wǎng)絡(luò)作為當(dāng)前解的候選解集。

3.3 特赦準(zhǔn)則

特赦準(zhǔn)則設(shè)置是算法避免遺失優(yōu)良解，激勵(lì)對(duì)優(yōu)良解的局部搜索，進(jìn)而實(shí)現(xiàn)全局優(yōu)化的關(guān)鍵步驟。在禁忌搜索過(guò)程中，可能會(huì)出現(xiàn)一個(gè)被禁忌候選解的目標(biāo)函數(shù)優(yōu)于當(dāng)前解，此時(shí)解禁該禁忌候選解，以實(shí)現(xiàn)更高的優(yōu)化性能。

3.4 終止準(zhǔn)則

通常終止準(zhǔn)則選擇為是否達(dá)到預(yù)定的最大迭代次數(shù)，而這種預(yù)定的最大迭代次數(shù)一般是根據(jù)經(jīng)驗(yàn)確定。顯然，迭代次數(shù)的多少應(yīng)與尋優(yōu)問(wèn)題規(guī)模有關(guān)。憑經(jīng)驗(yàn)給定最大迭代次數(shù)可能會(huì)產(chǎn)生兩類問(wèn)題：1）優(yōu)化過(guò)程早己達(dá)到最優(yōu)解，但是沒(méi)有達(dá)到最大迭代次數(shù)，優(yōu)化過(guò)程還要做不必要的迭代計(jì)算；2）優(yōu)化過(guò)程己經(jīng)達(dá)到最大迭代次數(shù)，但尚未達(dá)到最優(yōu)解就退出優(yōu)化過(guò)程。為了克服上述問(wèn)題，采用最優(yōu)解連續(xù)保持不變是否達(dá)到最大持續(xù)迭代步數(shù)niteration作為終止準(zhǔn)則。

3.5 算法流程

具體的基于禁忌搜索的復(fù)雜網(wǎng)絡(luò)抗毀性仿真優(yōu)化算法：

Step 1初始化算法：設(shè)置禁忌表長(zhǎng)度L、候選解集規(guī)模ncandidate以及最大持續(xù)迭代步數(shù)niteration；置禁忌表為空。

Step 2產(chǎn)生初始解G0：先置xi：=0，然后從中隨機(jī)選取W 個(gè)變量置其等于1；置最優(yōu)解G＊：=G0，置當(dāng)前解Gnow：=G0；

Step 3判斷終止準(zhǔn)則是否滿足，若是，則結(jié)束算法并輸出優(yōu)化結(jié)果；否則，繼續(xù)以下步驟。

Step 4生成候選解集：通過(guò)邊隨機(jī)重連產(chǎn)生ncandidate個(gè)新網(wǎng)絡(luò)，若產(chǎn)生的新網(wǎng)絡(luò)不連通，則重新選擇；計(jì)算每個(gè)新網(wǎng)絡(luò)的自然連通度。

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

Step 6轉(zhuǎn)Step 3。

4 仿真分析結(jié)果

基于本文的禁忌搜索仿真優(yōu)化算法分析優(yōu)化過(guò)程以及最優(yōu)抗毀性網(wǎng)絡(luò)的各種結(jié)構(gòu)屬性。仿真優(yōu)化參數(shù)為：節(jié)點(diǎn)數(shù)量N=100，邊的數(shù)量W=300，禁忌表長(zhǎng)度L=10、候選解集規(guī)模以及最大持續(xù)迭代步數(shù)niteration=30。

4.1 自然連通度

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

由圖2可見(jiàn)，自然連通度隨著迭代次數(shù)的增加而快速增加，從初始值2.84經(jīng)過(guò)582次迭代后達(dá)到穩(wěn)定最優(yōu)值11.05。這說(shuō)明本文提出的基于禁忌搜索的復(fù)雜網(wǎng)絡(luò)抗毀性仿真優(yōu)化算法能有效地優(yōu)化復(fù)雜網(wǎng)絡(luò)的抗毀性。作為參考，在圖2中還給出了具有相同節(jié)點(diǎn)數(shù)量以及邊數(shù)量的BA無(wú)標(biāo)度網(wǎng)絡(luò)（實(shí)線）、規(guī)則環(huán)狀格子（虛線）、ER隨機(jī)網(wǎng)絡(luò)（點(diǎn)劃線）的自然連通度?？梢钥闯觯ㄟ^(guò)優(yōu)化得到的網(wǎng)絡(luò)抗毀性遠(yuǎn)遠(yuǎn)高于這些典型網(wǎng)絡(luò)。

4.2 度關(guān)聯(lián)性

度關(guān)聯(lián)性刻畫的是網(wǎng)絡(luò)中不同度節(jié)點(diǎn)之間的微觀連接模式。如果度大的節(jié)點(diǎn)傾向于連接度大的節(jié)點(diǎn)，則稱網(wǎng)絡(luò)是同配的；反之，如果度大的節(jié)點(diǎn)傾向于和度小的節(jié)點(diǎn)連接，則稱網(wǎng)絡(luò)是異配的。度關(guān)聯(lián)性可用節(jié)點(diǎn)度的Pearson相關(guān)系數(shù)描述［28］。

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

其中，uk、vk分別為連接第k條邊的兩個(gè)節(jié)點(diǎn)的度，W 為網(wǎng)絡(luò)的總邊數(shù)。r的取值范圍為-1≤r≤1，當(dāng)r＞0時(shí)，網(wǎng)絡(luò)是同配的；當(dāng)r＜0時(shí)，網(wǎng)絡(luò)是異配的；當(dāng)r=0時(shí)，網(wǎng)絡(luò)是不相關(guān)的。

圖3給出了度關(guān)聯(lián)系數(shù)隨迭代次數(shù)n的變化圖?？梢钥闯?，度關(guān)聯(lián)系數(shù)隨著迭代次數(shù)的增加呈震蕩上升趨勢(shì)，最優(yōu)網(wǎng)絡(luò)的度關(guān)聯(lián)系數(shù)達(dá)到0.25，呈現(xiàn)出明顯的同配關(guān)聯(lián)模式，即度大的核心節(jié)點(diǎn)傾向于和度大的核心節(jié)點(diǎn)相連接，度小的末梢節(jié)點(diǎn)傾向于和度小的末梢節(jié)點(diǎn)相連接。作為參考，在圖3中給出了具有相同節(jié)點(diǎn)數(shù)量以及邊數(shù)量的BA無(wú)標(biāo)度網(wǎng)絡(luò)（實(shí)線）、規(guī)則環(huán)狀格子（虛線）、ER隨機(jī)網(wǎng)絡(luò)（點(diǎn)劃線）的度關(guān)聯(lián)系數(shù)。可以看出，BA無(wú)標(biāo)度網(wǎng)絡(luò)呈現(xiàn)出明顯的異配關(guān)聯(lián)模式，規(guī)則環(huán)狀格子和隨機(jī)網(wǎng)絡(luò)的度關(guān)聯(lián)系數(shù)接近0，即不存在明顯的度關(guān)聯(lián)，通過(guò)優(yōu)化得到的度關(guān)聯(lián)系數(shù)明顯高于這些典型網(wǎng)絡(luò)。

4.3 拓?fù)浣Y(jié)構(gòu)圖

為了直觀展現(xiàn)最優(yōu)抗毀性網(wǎng)絡(luò)的結(jié)構(gòu)屬性，在圖4中給出了最優(yōu)抗毀性網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖（圖4a）。作為參考，在圖4中還給出了具有相同節(jié)點(diǎn)數(shù)量以及邊數(shù)量的BA無(wú)標(biāo)度網(wǎng)絡(luò)（圖4b）、規(guī)則環(huán)狀格子（圖4 c）、ER隨機(jī)網(wǎng)絡(luò)（圖4d）的拓?fù)浣Y(jié)構(gòu)圖?？梢钥闯?，最優(yōu)抗毀性網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖與其他幾個(gè)典型網(wǎng)絡(luò)有很大不同。在最優(yōu)抗毀性網(wǎng)絡(luò)中存在少量度非常大的核心節(jié)點(diǎn)，而且這些核心節(jié)點(diǎn)之間相互連接緊密形成“富人俱樂(lè)部”。除了這些核心節(jié)點(diǎn)以外，其他節(jié)點(diǎn)的度都很小，而且這些度很小的末梢節(jié)點(diǎn)傾向于在外圍互相連接。

圖3 度關(guān)聯(lián)系數(shù)隨迭代次數(shù)變化圖Fig.3 The change of degree correlation coefficient with the number of iterations

圖4 最優(yōu)抗毀性網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)Fig.4 The network topology with optimal invulaer-ability

5 結(jié)束語(yǔ)

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

值得指出的是，本文研究的是復(fù)雜網(wǎng)絡(luò)抗毀性的全局優(yōu)化問(wèn)題，即在一定費(fèi)用約束條件下如何構(gòu)造出抗毀性更好的網(wǎng)絡(luò)。但是，很多情況下面對(duì)的都是已經(jīng)存在的網(wǎng)絡(luò)。這意味著不可能全部“重新洗牌”，只能局部?jī)?yōu)化網(wǎng)絡(luò)結(jié)構(gòu)。在這種情況下，如何通過(guò)最少的優(yōu)化達(dá)到最大的抗毀性是我們下一步需要研究的問(wèn)題。

［1］方錦清，汪小帆，劉曾榮.略論復(fù)雜性問(wèn)題和非線性復(fù)雜網(wǎng)絡(luò)系統(tǒng)的研究［J］.科技導(dǎo)報(bào)，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］方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉科學(xué)：網(wǎng)絡(luò)科學(xué)（上）［J］.物理學(xué)進(jìn)展，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］方錦清，汪小帆，鄭志剛，等.一門嶄新的交叉科學(xué)：網(wǎng)絡(luò)科學(xué)（下）［J］.物理學(xué)進(jìn)展，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］陳禹.人類對(duì)于網(wǎng)絡(luò)的認(rèn)識(shí)的新發(fā)展［J］.系統(tǒng)辯證學(xué)報(bào)，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］史定華.網(wǎng)絡(luò)——探索復(fù)雜性的新途徑［J］.系統(tǒng)工程學(xué)報(bào)，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］汪秉宏，周濤，何大韌.統(tǒng)計(jì)物理學(xué)與復(fù)雜系統(tǒng)研究最新發(fā)展趨勢(shì)分析［J］.中國(guó)基礎(chǔ)科學(xué)，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］汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京：清華大學(xué)出版社，2006.

［8］譚躍進(jìn)，吳俊，鄧宏鐘.復(fù)雜網(wǎng)絡(luò)抗毀性研究綜述［J］.系統(tǒng)工程，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ìn).復(fù)雜網(wǎng)絡(luò)抗毀性測(cè)度研究［J］.系統(tǒng)工程學(xué)報(bào)，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ìn)，呂欣，吳俊，等.復(fù)雜網(wǎng)絡(luò)抗毀性研究若干問(wèn)題的思考［J］.系統(tǒng)工程理論與實(shí)踐，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，F(xiàn)risch 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ìn).系統(tǒng)的核與核度理論Ⅱ——優(yōu)化設(shè)計(jì)與可靠通訊網(wǎng)絡(luò)［J］.系統(tǒng)工程學(xué)報(bào)，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ìn)，席酉民.系統(tǒng)的核與核度［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，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

國(guó)家自然科學(xué)基金（60904065，71031007，71171195）；新世紀(jì)優(yōu)秀人才支持計(jì)劃（NCET-12-0141）

田田（1979-），男，黑龍江哈爾濱人，碩士，工程師，主要研究方向?yàn)橛?jì)算機(jī)工程。

（責(zé)任編輯 耿金花）