發(fā)布時(shí)間：2021-01-24 01:21

　　近年來,隨著復(fù)雜網(wǎng)絡(luò)研究的興起,復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)備受關(guān)注。社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最重要的拓?fù)浣Y(jié)構(gòu)屬性之一,它揭示了復(fù)雜網(wǎng)絡(luò)的隱藏規(guī)律和行為特征。復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)對揭示網(wǎng)絡(luò)的結(jié)構(gòu)和功能之間的聯(lián)系有著重要的意義。社團(tuán)發(fā)現(xiàn)中常見的方法是優(yōu)化單個(gè)目標(biāo)函數(shù),例如模塊度Q。目前的大多數(shù)算法都采用了將模塊度作為優(yōu)化目標(biāo),進(jìn)而將社團(tuán)發(fā)現(xiàn)問題轉(zhuǎn)化為優(yōu)化模塊度的問題。然而,這些算法大部分都有很高的復(fù)雜度,并不適合解決大規(guī)模網(wǎng)絡(luò)問題。而另一方面,由于采用單個(gè)優(yōu)化目標(biāo),這些算法都不可避免地會存在解限制的問題。為解決上述第一個(gè)問題,本文首先提出了將遺傳算法引入社團(tuán)發(fā)現(xiàn),產(chǎn)生了一種新的算法,有效解決了目前的社團(tuán)發(fā)現(xiàn)算法效率低的問題,并通過四個(gè)實(shí)驗(yàn)證明了該算法的有效性。另一方面,為解決單目標(biāo)優(yōu)存在的解限制問題,本文又提出了將進(jìn)化多目標(biāo)算法應(yīng)用于社團(tuán)發(fā)現(xiàn)。該算法同時(shí)優(yōu)化兩個(gè)互補(bǔ)的目標(biāo)函數(shù),并返回一組在這兩個(gè)目標(biāo)函數(shù)之間進(jìn)行折中優(yōu)化的非占優(yōu)解。在返回的非占優(yōu)解集中需要選擇一個(gè)作為最優(yōu)解,本文進(jìn)一步提出了四個(gè)模型選擇標(biāo)準(zhǔn)。相關(guān)實(shí)驗(yàn)分為兩個(gè)部分：第一部分的實(shí)驗(yàn)結(jié)果表明進(jìn)化多目標(biāo)優(yōu)化算法運(yùn)行一次能夠找到多個(gè)從不同角度反映... 

【文章來源】：北京郵電大學(xué)北京市 211工程院校 教育部直屬院校

【文章頁數(shù)】：75 頁

【學(xué)位級別】：碩士

【部分圖文】：

一個(gè)簡單的遺傳算法流程圖

而圖中的社團(tuán)則由結(jié)點(diǎn)集合來表示。在為社團(tuán)劃分進(jìn)行編碼方面，我們使用了鄰接點(diǎn)表示法[36]，如圖3一1所示。每個(gè)基因型包含了91，92，…，g。n個(gè)基因(n為網(wǎng)絡(luò)中結(jié)點(diǎn)個(gè)數(shù))，每個(gè)基因gi表示了結(jié)點(diǎn)i的一個(gè)鄰居結(jié)點(diǎn)編號。因此，第i個(gè)基因的值j表示了結(jié)點(diǎn)i和j之間有邊相連，從社團(tuán)劃分結(jié)果來看，則表示結(jié)點(diǎn)i與j被劃分到了同一個(gè)社團(tuán)中。解碼過程需要對圖中每一個(gè)連通分量進(jìn)行識別。隸屬于同一個(gè)連通分量的所有結(jié)點(diǎn)被劃分到同一個(gè)社團(tuán)。因?yàn)榻獯a過程采用的是一種回溯的策略，解碼過程的時(shí)間復(fù)雜度呈線性。解碼過程的偽代碼在附錄1中說明。通過以上對編碼解碼過程的說明，不難看出采用鄰接點(diǎn)編碼策略解決社團(tuán)發(fā)現(xiàn)問題十分有益。其中最大的一個(gè)優(yōu)點(diǎn)就是決策者不用事先定義劃分社團(tuán)個(gè)數(shù)

圖3-2一個(gè)交叉操作的實(shí)例圖。源染色體A中的基因g:與目標(biāo)染色體B中的基因98位置交換。3.2實(shí)驗(yàn)本節(jié)將進(jìn)行四個(gè)實(shí)驗(yàn)，分別從四個(gè)方面來驗(yàn)證GACD的性能。實(shí)驗(yàn)環(huán)3GH主頻、IG內(nèi)存、運(yùn)行Linux.我們首先對已知其社團(tuán)結(jié)構(gòu)的人工網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)來驗(yàn)證算法的準(zhǔn)確性。對象是一個(gè)有128個(gè)結(jié)點(diǎn)，平均分成了四個(gè)各自包括犯個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)[371。中的平均結(jié)點(diǎn)度為16，kou，表示不同社團(tuán)之間結(jié)點(diǎn)連接的平均度，氣表示同團(tuán)的結(jié)點(diǎn)之間相連的平均度(*、+k0.，=16)。實(shí)驗(yàn)首先產(chǎn)生了一組這樣的網(wǎng)絡(luò)，的蠕值從0逐漸增加到10。隨著kou，值的增加，網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)也越來越

【參考文獻(xiàn)】：
期刊論文
[1]進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 公茂果,焦李成,楊咚咚,馬文萍.  軟件學(xué)報(bào). 2009(02)
[2]復(fù)雜網(wǎng)絡(luò)聚類方法[J]. 楊博,劉大有,金弟,馬海賓.  軟件學(xué)報(bào). 2009(01)
[3]基于信息瓶頸的社區(qū)發(fā)現(xiàn)[J]. 沈華偉,程學(xué)旗,陳海強(qiáng),劉悅.  計(jì)算機(jī)學(xué)報(bào). 2008(04)
[4]一種從馬爾可夫聚類簇發(fā)現(xiàn)潛在WEB社區(qū)特征的方法[J]. 楊楠,林松祥,高強(qiáng),孟小峰.  計(jì)算機(jī)學(xué)報(bào). 2007(07)
[5]一種快速的基于占優(yōu)樹的多目標(biāo)進(jìn)化算法[J]. 石川,李清勇,史忠植.  軟件學(xué)報(bào). 2007(03)



本文編號：2996290