基于密母算法的復雜網(wǎng)絡社團檢測.pdf

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

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

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

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

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