復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)的多目標(biāo)進(jìn)化算法研究.pdf

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

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

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

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

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