基于密母算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測.pdf

1、現(xiàn)實(shí)世界中的很多復(fù)雜系統(tǒng)可以由網(wǎng)絡(luò)表示出來，如技術(shù)網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)絡(luò)及生物網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)經(jīng)過建模以后可抽象化為圖，其中節(jié)點(diǎn)表示對象，節(jié)點(diǎn)之間的連接可以表示對象之間具有某種關(guān)系。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特性，它可以定義為網(wǎng)絡(luò)中的一個(gè)由若干節(jié)點(diǎn)構(gòu)成的子集，其內(nèi)部節(jié)點(diǎn)之間連接緊密，而與網(wǎng)絡(luò)中其他節(jié)點(diǎn)之間的連接較為稀疏。研究社團(tuán)結(jié)構(gòu)對于分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)的功能、預(yù)測復(fù)雜網(wǎng)絡(luò)的行為具有重要的意義。近年來，社團(tuán)檢測

2、問題受到了各個(gè)領(lǐng)域的學(xué)者的廣泛關(guān)注，許多算法也相繼被提出來，如圖劃分方法、層次聚類法、譜聚類法、基于相似度的方法以及基于進(jìn)化的優(yōu)化算法等。
　　密母算法是計(jì)算機(jī)科學(xué)和社會(huì)生物學(xué)的交叉產(chǎn)物，它建立在模擬文化進(jìn)化基礎(chǔ)之上，實(shí)質(zhì)是一種基于種群的全局搜索和基于個(gè)體的局部啟發(fā)式搜索的結(jié)合體。經(jīng)過多年發(fā)展，密母算法已被越來越多的研究人員接受并廣泛應(yīng)用到組合優(yōu)化、模式識(shí)別、圖像處理等領(lǐng)域中。本文針對復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測進(jìn)行了系統(tǒng)地研究，所取得的主要

3、研究成果為：
　　1.研究進(jìn)化算法的基本理論，并深入理解密母算法及其改進(jìn)算法在復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測問題中的應(yīng)用。在此基礎(chǔ)上，提出了一種利用局部結(jié)構(gòu)信息的密母算法（Memetic algorithm using local structural information，MA-LSI）用于解決復(fù)雜網(wǎng)絡(luò)的社團(tuán)檢測問題。在該算法中，利用模塊度函數(shù) Q作為適應(yīng)度函數(shù)，并利用一個(gè)局部社團(tuán)的質(zhì)量評價(jià)函數(shù)來定義局部搜索算子，此外還采用了一種節(jié)點(diǎn)移動(dòng)策

4、略來改善劃分結(jié)果。與經(jīng)典的快速紐曼（Fast Newman，F(xiàn)N）聚類算法和其他密母算法相比，實(shí)驗(yàn)結(jié)果表明該算法可以產(chǎn)生更為精確的劃分結(jié)果。
　　2.研究了傳統(tǒng)的模塊度優(yōu)化所具有的分辨率限制問題，采用另外一個(gè)可以克服分辨率限制問題的目標(biāo)函數(shù)：擴(kuò)展模塊度密度函數(shù)。該函數(shù)中含有一個(gè)可調(diào)參數(shù)，通過改變參數(shù)的取值可以實(shí)現(xiàn)以不同分辨率分析網(wǎng)絡(luò)，從而檢測出網(wǎng)絡(luò)的多分辨結(jié)構(gòu)?；跀U(kuò)展模塊度密度函數(shù)的優(yōu)化，提出另外一種密母算法（Memetic a

5、lgorithm with simulated annealing strategy and tightness greedy optimization，MA-SAT）用于復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測。該算法中有兩個(gè)局部搜索算子，一個(gè)采用了模擬退火策略，另一個(gè)采用了局部社團(tuán)緊密度函數(shù)的貪心優(yōu)化。模擬退火策略可以加速算法的收斂且有助于算法跳出局部最優(yōu)，緊密度貪心優(yōu)化充分利用了網(wǎng)絡(luò)的結(jié)構(gòu)信息來產(chǎn)生鄰居劃分，計(jì)算代價(jià)小并且有助于提高種群的多樣性。與幾種經(jīng)