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

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

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

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

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

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

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

7、測(cè)大規(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)點(diǎn)，能夠快速有效地找到基于模塊度優(yōu)化的最優(yōu)解和網(wǎng)絡(luò)的最優(yōu)社區(qū)結(jié)構(gòu)劃分。系統(tǒng)性的實(shí)驗(yàn)證明了提出的算法在大規(guī)模網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測(cè)的有效性、快速性和穩(wěn)定性。
　　3）如何

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

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

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