1、科技的高速發(fā)展使人類社會大步邁入了網(wǎng)絡時代，很多現(xiàn)實世界的復雜系統(tǒng)都可以表示為網(wǎng)絡，如協(xié)作網(wǎng)，萬維網(wǎng)，電力網(wǎng)，生物網(wǎng)和社會網(wǎng)絡等。網(wǎng)絡可以模型化為圖，其中節(jié)點表示對象，邊表示節(jié)點之間的連接。近年來，復雜網(wǎng)絡逐漸受到了來自各個領域研究者們越來越多的關注，例如物理學，數(shù)學，生物學，社會學等。除了小世界效應，無標度等網(wǎng)絡屬性外，社區(qū)結構是復雜網(wǎng)絡中另外一個重要的網(wǎng)絡屬性。社區(qū)可以定性的定義為網(wǎng)絡中節(jié)點的子集，其內部節(jié)點之間的鏈接比較緊密，而和

2、網(wǎng)絡中其它節(jié)點的鏈接相對稀疏。研究復雜網(wǎng)絡社區(qū)結構對于分析網(wǎng)絡的拓撲結構、理解網(wǎng)絡的功能、發(fā)現(xiàn)網(wǎng)絡中的隱藏規(guī)律以及預測網(wǎng)絡的行為不僅具有十分重要的理論意義，而且具有廣泛的應用前景。近年來，越來越多的社區(qū)檢測算法被提了出來，這些算法大致可以分為三類：基于圖分割的方法，基于層次聚類的方法和基于模塊度(modularity)優(yōu)化的方法，其中基于模塊度優(yōu)化的方法近年來得到了越來越多的關注。模塊度函數(shù)是Newman和Girvan提出的用來評價網(wǎng)絡

3、社區(qū)劃分質量的指標函數(shù)。一般來說，模塊度值越大，對應的社區(qū)結構越明顯。
　　 密母算法(Memetic algorithm)是近年來進化計算領域的一個研究熱點，它是一種基于種群的全局搜索和基于個體的局部啟發(fā)式搜索的結合體，這種結合機制使其搜索效率在某些問題領域比傳統(tǒng)遺傳算法快幾個數(shù)量級。本文所做的主要工作，就是利用進化算法這些優(yōu)點，將其應用于復雜網(wǎng)絡社區(qū)檢測問題。本文所做的主要工作如下：
　　 (1)研究了多目標優(yōu)化和進

4、化算法的基本理論，提出了一種基于分解多目標優(yōu)化進化算法(MOEA/D)的復雜網(wǎng)絡社區(qū)檢測方法。在該方法中，我們把社區(qū)檢測問題模型化為了一個兩個目標的多目標優(yōu)化問題，并利用多目標進化算法MOEA/D來優(yōu)化這兩個目標。
　　 (2)研究了社區(qū)檢測算法中傳統(tǒng)模塊度優(yōu)化具有的分辨率限制問題，為了解決這個問題，我們使用了一個新的目標函數(shù)：擴展模塊度密度(general modularitydensity)，該目標函數(shù)是ratio asso

5、ciation與ratio cut的凸組合，可以克服分辨率限制問題，也就是說通過調節(jié)里面的參數(shù)，我們可以從不同分辨率分析網(wǎng)絡，進而發(fā)現(xiàn)網(wǎng)絡社區(qū)的層次結構。研究了密母算法(memetic algorithm)的基本理論，在此基礎上提出了一種復雜網(wǎng)絡社區(qū)檢測密母算法。該密母算法引入了局部搜索策略，克服了傳統(tǒng)遺傳算法收斂速度慢，容易陷入局部最優(yōu)的缺點。同時，該算法將擴展模塊度密度作為目標函數(shù)，可以從不同分辨率分析網(wǎng)絡，克服了傳統(tǒng)模塊度優(yōu)化算法