復雜網(wǎng)絡(luò)社區(qū)檢測的多目標進化算法研究.pdf

1、現(xiàn)實世界中,很多系統(tǒng)都可以由復雜網(wǎng)絡(luò)來表示,如協(xié)作網(wǎng)、萬維網(wǎng)、生物網(wǎng)、通信網(wǎng)絡(luò)、運輸網(wǎng)絡(luò)、社會網(wǎng)絡(luò)等。在復雜網(wǎng)絡(luò)中被廣泛關(guān)注的一個拓撲屬性就是網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu),它的特點是在同一個社區(qū)內(nèi)節(jié)點間連接的比較緊密,而在不同社區(qū)間節(jié)點的連接比較稀疏。研究復雜網(wǎng)絡(luò)中社區(qū)的拓撲結(jié)構(gòu),對發(fā)現(xiàn)社區(qū)之間的相互關(guān)系、了解網(wǎng)絡(luò)的行為,具有非常重要的理論價值和現(xiàn)實意義。
　　近年來,越來越多的社區(qū)檢測算法被提了出來,包括基于圖分割的方法,基于層次聚類的方法,

2、基于模塊度優(yōu)化的方法等等。Pizzuti提出了一種基于多目標進化的方法,該方法采用一種多目標進化算法作為基本框架優(yōu)化兩個目標函數(shù),得到的不是單一解,而是一系列解,社區(qū)的劃分數(shù)可以自動分配,每個解都是一個隨機的網(wǎng)絡(luò)劃分結(jié)果。這是一個全新的方法,為復雜網(wǎng)絡(luò)社區(qū)檢測問題提供了一個新的方向和思路。隨著基于分解的多目標遺傳算法的提出,為我們提供了一個很好的算法框架,該算法分解一個多目標優(yōu)化問題為多個標量子問題,通過種群的進化來同時優(yōu)化他們,該算法

3、可以有效的解決多目標優(yōu)化問題。本文的主要研究工作闡述如下:
　　(1)針對基于分解的多目標遺傳算法具有局部搜索能力差的缺點,通過對密母模型的深入研究,提出了一種基于多目標密母算法的復雜網(wǎng)絡(luò)社區(qū)檢測算法。在該算法中,采用基于分解的多目標進化算法用作全局搜索,引入了模擬退火算法作為局部搜索算子,采用標簽法作為初始化方法,改進了交叉變異算子。該算法的初始種群具有一定的精確度和多樣性,局部搜索能力強,在人工網(wǎng)絡(luò)和真實網(wǎng)絡(luò)上得到了很好的效果

4、,證明了算法的有效性。該算法在一次運行中能夠得到一系列解,每個解對應(yīng)著網(wǎng)絡(luò)的不同劃分,也就是復雜網(wǎng)絡(luò)不同層次的社區(qū)結(jié)構(gòu),從而可以將該算法應(yīng)用在社區(qū)結(jié)構(gòu)檢測問題上,證明了該算法能夠很好的揭示網(wǎng)絡(luò)的層次結(jié)構(gòu)。
　　(2)針對基于分解的多目標遺傳算法的隨機式的進化過程,通過深入研究種群增量學習算法,提出了一種基于多目標種群增量學習的復雜網(wǎng)絡(luò)社區(qū)檢測算法。在該算法中,用十進制方法修改了種群增量學習的編碼方式,很好的融合了多目標進化算法和群

5、增量學習算子,修改了學習概率的初始化和更新方式,采用了隨機擾動算子作為突變算子。該算法使種群進化具有了方向性,加快了算法的收斂,在人工網(wǎng)絡(luò)和真實網(wǎng)絡(luò)上得到了很好的效果,證明了算法的有效性。該算法在一次運行中能夠得到一系列解,每個解對應(yīng)著網(wǎng)絡(luò)的不同劃分,也就是復雜網(wǎng)絡(luò)不同層次的社區(qū)結(jié)構(gòu),從而可以將該算法應(yīng)用在社區(qū)結(jié)構(gòu)檢測問題上,證明了該算法能夠很好的揭示網(wǎng)絡(luò)的層次結(jié)構(gòu)。
　　本文工作得到國家自然科學基金( No.61203303)、