近年來,隨著復(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)化單個目標(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ò)問題。而另一方面,由于采用單個優(yōu)化目標(biāo),這些算法都不可避免地會存在解限制的問題。為解決上述第一個問題,本文首先提出了將遺傳算法引入社團(tuán)發(fā)現(xiàn),產(chǎn)生了一種新的算法,有效解決了目前的社團(tuán)發(fā)現(xiàn)算法效率低的問題,并通過四個實驗證明了該算法的有效性。另一方面,為解決單目標(biāo)優(yōu)存在的解限制問題,本文又提出了將進(jìn)化多目標(biāo)算法應(yīng)用于社團(tuán)發(fā)現(xiàn)。該算法同時優(yōu)化兩個互補(bǔ)的目標(biāo)函數(shù),并返回一組在這兩個目標(biāo)函數(shù)之間進(jìn)行折中優(yōu)化的非占優(yōu)解。在返回的非占優(yōu)解集中需要選擇一個作為最優(yōu)解,本文進(jìn)一步提出了四個模型選擇標(biāo)準(zhǔn)。相關(guān)實驗分為兩個部分：第一部分的實驗結(jié)果表明進(jìn)化多目標(biāo)優(yōu)化算法運行一次能夠找到多個從不同角度反映... 

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

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

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

【部分圖文】：

一個簡單的遺傳算法流程圖

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

圖3-2一個交叉操作的實例圖。源染色體A中的基因g:與目標(biāo)染色體B中的基因98位置交換。3.2實驗本節(jié)將進(jìn)行四個實驗，分別從四個方面來驗證GACD的性能。實驗環(huán)3GH主頻、IG內(nèi)存、運行Linux.我們首先對已知其社團(tuán)結(jié)構(gòu)的人工網(wǎng)絡(luò)進(jìn)行實驗來驗證算法的準(zhǔn)確性。對象是一個有128個結(jié)點，平均分成了四個各自包括犯個結(jié)點的網(wǎng)絡(luò)[371。中的平均結(jié)點度為16，kou，表示不同社團(tuán)之間結(jié)點連接的平均度，氣表示同團(tuán)的結(jié)點之間相連的平均度(*、+k0.，=16)。實驗首先產(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é)報. 2009(02)
[2]復(fù)雜網(wǎng)絡(luò)聚類方法[J]. 楊博,劉大有,金弟,馬海賓.  軟件學(xué)報. 2009(01)
[3]基于信息瓶頸的社區(qū)發(fā)現(xiàn)[J]. 沈華偉,程學(xué)旗,陳海強(qiáng),劉悅.  計算機(jī)學(xué)報. 2008(04)
[4]一種從馬爾可夫聚類簇發(fā)現(xiàn)潛在WEB社區(qū)特征的方法[J]. 楊楠,林松祥,高強(qiáng),孟小峰.  計算機(jī)學(xué)報. 2007(07)
[5]一種快速的基于占優(yōu)樹的多目標(biāo)進(jìn)化算法[J]. 石川,李清勇,史忠植.  軟件學(xué)報. 2007(03)



本文編號：2996290