基于啟發(fā)式進化計算的網(wǎng)絡(luò)結(jié)構(gòu)與行為分析.pdf

1、隨著互聯(lián)網(wǎng)和信息技術(shù)的迅速發(fā)展，不同領(lǐng)域的復(fù)雜系統(tǒng)（比如在線社交系統(tǒng)、社會媒體、信息預(yù)測與推薦系統(tǒng)、控制系統(tǒng)、傳播系統(tǒng)、電力系統(tǒng)、合作系統(tǒng)、運輸系統(tǒng)、勘探系統(tǒng)、調(diào)度系統(tǒng)等）可以通過一種復(fù)雜網(wǎng)絡(luò)化數(shù)據(jù)形式進行表達。其中，復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)中的節(jié)點和邊分別代表著復(fù)雜系統(tǒng)中的實體和實體之間的聯(lián)系。此外，信息存儲技術(shù)和信息在線傳輸技術(shù)的快速發(fā)展提供了大量可供研究的復(fù)雜系統(tǒng)網(wǎng)絡(luò)數(shù)據(jù)。通過對這些網(wǎng)絡(luò)數(shù)據(jù)定量化和定性特性的理論分析、算法設(shè)計、模擬實現(xiàn)以及應(yīng)

2、用驗證等多種科學(xué)分析方法來推動復(fù)雜性科學(xué)、系統(tǒng)動力學(xué)、社會行為學(xué)、經(jīng)濟學(xué)、管理學(xué)、心理學(xué)等多個學(xué)科的結(jié)合和發(fā)展。
　　近年來，學(xué)者們通過研究復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)上的模式結(jié)構(gòu)（比如社區(qū)結(jié)構(gòu)、小世界特性和無標度特性等）來理解復(fù)雜系統(tǒng)的功能；通過研究復(fù)雜網(wǎng)絡(luò)上的行為特性（比如網(wǎng)絡(luò)傳播性、網(wǎng)絡(luò)結(jié)構(gòu)平衡、網(wǎng)絡(luò)魯棒性、網(wǎng)絡(luò)控制性、網(wǎng)絡(luò)預(yù)測性、網(wǎng)絡(luò)競爭與合作、網(wǎng)絡(luò)耦合性、網(wǎng)絡(luò)級聯(lián)失效、網(wǎng)絡(luò)分布式）來理解、控制和預(yù)測復(fù)雜系統(tǒng)功能的變化和發(fā)展。模塊性或稱社

3、區(qū)結(jié)構(gòu)是復(fù)雜系統(tǒng)中一個最重要也是最基本的模式結(jié)構(gòu)。這種模式結(jié)構(gòu)在復(fù)雜網(wǎng)絡(luò)中表現(xiàn)為模塊內(nèi)部相互聯(lián)系緊密與模塊之間連接稀疏的節(jié)點集。復(fù)雜系統(tǒng)的模塊性分析能有效地反映系統(tǒng)潛在功能塊以及功能塊之間的聯(lián)系，并有助于理解、分析和預(yù)測復(fù)雜系統(tǒng)的行為特性。研究復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)平衡行為特性可以有效地預(yù)測和減少系統(tǒng)中功能模塊中存在的沖突，促進系統(tǒng)實體模塊的安全和諧發(fā)展。研究復(fù)雜系統(tǒng)的結(jié)構(gòu)魯棒性對系統(tǒng)功能模塊的安全性、穩(wěn)定性以及抗打擊性的分析有著重要的作用。<

4、br>　　本文主要針對復(fù)雜系統(tǒng)中的社區(qū)結(jié)構(gòu)模式挖掘、結(jié)構(gòu)平衡的計算與轉(zhuǎn)換以及結(jié)構(gòu)魯棒性的行為優(yōu)化展開研究。本文所采用的研究思路是將所關(guān)注的上述網(wǎng)絡(luò)問題模擬映射為網(wǎng)絡(luò)優(yōu)化問題，然后結(jié)合計算智能算法的啟發(fā)式特性以及網(wǎng)絡(luò)上的啟發(fā)性特定結(jié)構(gòu)知識來解決所模擬的優(yōu)化問題。具體而言，本文所展開的研究工作概括如下：
　　1）針對基于優(yōu)化的社區(qū)結(jié)構(gòu)檢測算法難以檢測網(wǎng)絡(luò)真實社區(qū)結(jié)構(gòu)和提取網(wǎng)絡(luò)多分辨社區(qū)結(jié)構(gòu)的問題，本文將復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)檢測問題建模為

5、一個多目標優(yōu)化問題，并結(jié)合網(wǎng)絡(luò)特定的啟發(fā)性拓撲結(jié)構(gòu)知識提出一種基于分解的多目標進化算法來求解該多目標優(yōu)化問題。在提出的多目標優(yōu)化問題中，優(yōu)化其中的一個目標傾向于得到高分辨下社區(qū)數(shù)比較多的網(wǎng)絡(luò)社區(qū)劃分，而優(yōu)化另外一個目標容易獲取低分辨下社區(qū)數(shù)比較少的網(wǎng)絡(luò)社區(qū)劃分。同時優(yōu)化這兩個具有相互沖突性的目標將會得到在多種分辨率下的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分。大量實驗證明與三個具有代表性的社區(qū)結(jié)構(gòu)算法相比，本文提出的多目標社區(qū)檢測優(yōu)化模型以及多目標優(yōu)化算法能較

6、好地在中小規(guī)模網(wǎng)絡(luò)上挖掘其真實社區(qū)結(jié)構(gòu)劃分以及提取其多分辨社區(qū)結(jié)構(gòu)。
　　2）快速、穩(wěn)定、有效地檢測大規(guī)模網(wǎng)絡(luò)中的真實社區(qū)結(jié)構(gòu)一直是近年來在網(wǎng)絡(luò)問題上研究的難點。傳統(tǒng)的基于貪婪的優(yōu)化算法能夠快速地檢測網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，但是它們很難找到網(wǎng)絡(luò)的真實社區(qū)結(jié)構(gòu)?；谶M化優(yōu)化的社區(qū)結(jié)構(gòu)檢測算法能夠有效地檢測出網(wǎng)絡(luò)的真實社區(qū)結(jié)構(gòu)，然而這類算法擁有較高的計算復(fù)雜度和不穩(wěn)定性。本文利用網(wǎng)絡(luò)的拓撲結(jié)構(gòu)知識，提出一種基于多層學(xué)習(xí)的Memetic算法來檢

7、測大規(guī)模網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。提出的Memetic算法由基于遺傳算法的全局搜索和基于多層學(xué)習(xí)優(yōu)化的局部搜索組成?；谶z傳算法的全局搜索能有效地探索解的感興趣區(qū)域；基于多層學(xué)習(xí)優(yōu)化的局部搜索能夠快速地找到特定解區(qū)域中的最優(yōu)解。本文提出的Memetic算法綜合局部搜索和全局搜索的優(yōu)點，能夠快速有效地找到基于模塊度優(yōu)化的最優(yōu)解和網(wǎng)絡(luò)的最優(yōu)社區(qū)結(jié)構(gòu)劃分。系統(tǒng)性的實驗證明了提出的算法在大規(guī)模網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測的有效性、快速性和穩(wěn)定性。
　　3）如何

8、反映社會網(wǎng)絡(luò)中的不平衡行為以及如何挖掘和消除社會網(wǎng)絡(luò)中的不平衡因素是當(dāng)前網(wǎng)絡(luò)社會行為學(xué)中的研究難點。本文利用結(jié)構(gòu)平衡理論將符號網(wǎng)絡(luò)的結(jié)構(gòu)平衡計算和轉(zhuǎn)化問題映射為基于優(yōu)化能量函數(shù)的社區(qū)結(jié)構(gòu)檢測問題，提出基于網(wǎng)絡(luò)啟發(fā)性結(jié)構(gòu)知識的Memetic算法來解決此優(yōu)化問題，通過挖掘社區(qū)內(nèi)部的敵對關(guān)系和社區(qū)間的友好關(guān)系計算出符號網(wǎng)絡(luò)中的不平衡因素，并通過轉(zhuǎn)換網(wǎng)絡(luò)中的不平衡因素實現(xiàn)網(wǎng)絡(luò)從不平衡性向平衡性的轉(zhuǎn)換。本文提出的Memetic算法充分利用網(wǎng)絡(luò)特定

9、的節(jié)點鄰域、社區(qū)鄰域和網(wǎng)絡(luò)劃分鄰域結(jié)構(gòu)知識。在大量真實社會網(wǎng)絡(luò)中的實驗證明了本文算法的有效性。
　　4）當(dāng)復(fù)雜網(wǎng)絡(luò)受到惡意的攻擊時，其網(wǎng)絡(luò)拓撲結(jié)構(gòu)和網(wǎng)絡(luò)功能將會受到由級聯(lián)破壞引發(fā)的傷害。研究網(wǎng)絡(luò)社區(qū)魯棒性有助于理解網(wǎng)絡(luò)社區(qū)功能對惡意攻擊的抵抗力，并有助于研究如何保護網(wǎng)絡(luò)的社區(qū)功能免受傷害。針對現(xiàn)有模型和優(yōu)化算法無法分析復(fù)雜網(wǎng)絡(luò)在遭受惡意攻擊時其社區(qū)功能完整性以及無法保護網(wǎng)絡(luò)的社區(qū)功能免受傷害的情況下，首先，本文將復(fù)雜系統(tǒng)中的攻擊模

10、擬成一個多層網(wǎng)絡(luò)攻擊模型。其次，提出社區(qū)魯棒性指標來測量網(wǎng)絡(luò)在受到攻擊時其社區(qū)功能抵抗攻擊的能力。最后，提出啟發(fā)式貪婪算法微調(diào)網(wǎng)絡(luò)的邊拓撲結(jié)構(gòu)來提高網(wǎng)絡(luò)社區(qū)功能抵抗外界攻擊的能力。
　　5）在現(xiàn)實世界中，一個復(fù)雜的真實系統(tǒng)不僅僅由一個獨立的子系統(tǒng)構(gòu)成，而是由多個相互耦合的或相互控制的子系統(tǒng)構(gòu)成。當(dāng)一個子系統(tǒng)中的某部分功能喪失時，將會觸發(fā)一系列多子系統(tǒng)間的級聯(lián)失效過程，最終可能會導(dǎo)致整個系統(tǒng)無法正常運行。快速恢復(fù)受損系統(tǒng)的功能與我們