基于密度和進(jìn)化的社區(qū)結(jié)構(gòu)檢測(cè)方法.pdf

1、近年來網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測(cè)受到越來越多的關(guān)注。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要屬性。網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)就是網(wǎng)絡(luò)中某些特定節(jié)點(diǎn)的子集,其內(nèi)部節(jié)點(diǎn)之間的聯(lián)系比較緊密,而和網(wǎng)絡(luò)中其它節(jié)點(diǎn)的聯(lián)系相對(duì)稀疏。網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)分析對(duì)于理解網(wǎng)絡(luò)子結(jié)構(gòu)的功能、發(fā)現(xiàn)網(wǎng)絡(luò)中的隱藏規(guī)律以及預(yù)測(cè)網(wǎng)絡(luò)的行為不僅有十分重要的理論意義,而且有廣泛的應(yīng)用前景。
　　基于密度的方法在社區(qū)結(jié)構(gòu)檢測(cè)領(lǐng)域的研究熱度越來越高。這類方法依賴于兩個(gè)參數(shù),因此對(duì)輸入的參數(shù)極為敏感,導(dǎo)致難以選擇合適

2、的全局參數(shù)。正因?yàn)檫@些參數(shù)非常敏感而且具有全局作用,我們并沒有采用常規(guī)的選擇參數(shù)的做法,而是利用了參數(shù)的上述特性,提出了一種全新的從社區(qū)層面對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行深入分析的思路,同時(shí)提出了一種啟發(fā)式的基于密度的社區(qū)結(jié)構(gòu)檢測(cè)方法。在所提出的方法中,首先,利用參數(shù)的閾值作用本質(zhì),找出所有可能的輸入?yún)?shù)情況。這些參數(shù)按照經(jīng)典方法將產(chǎn)生多種多樣的網(wǎng)絡(luò)結(jié)構(gòu)劃分。其次,我們提出了包括劃分、融合、分解、重組的策略對(duì)這些劃分進(jìn)行社區(qū)層面的處理。尤其在重組步驟中

3、,我們用到了進(jìn)化算法的思想,利用模塊度搜索出了最好的結(jié)果。當(dāng)這些策略處理完畢之后,我們將可以獲得一個(gè)高質(zhì)量的社區(qū)劃分。在虛擬網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)上的實(shí)驗(yàn)證明了我們方法的有效性。
　　網(wǎng)絡(luò)的動(dòng)態(tài)特征是另一個(gè)持續(xù)受到關(guān)注的網(wǎng)絡(luò)屬性?，F(xiàn)實(shí)世界中的網(wǎng)絡(luò)多數(shù)都是動(dòng)態(tài)網(wǎng)絡(luò),動(dòng)態(tài)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)會(huì)隨著時(shí)間不斷演化,因此它比靜態(tài)網(wǎng)絡(luò)社區(qū)檢測(cè)更富有挑戰(zhàn)性。在動(dòng)態(tài)網(wǎng)絡(luò)中,我們?nèi)匀恍枰紤]每個(gè)時(shí)間點(diǎn)的靜態(tài)網(wǎng)絡(luò)劃分質(zhì)量,同時(shí)也要兼顧各時(shí)間點(diǎn)之間的動(dòng)態(tài)聯(lián)系。在時(shí)間

4、光滑的假設(shè)下,這種動(dòng)態(tài)聯(lián)系被數(shù)學(xué)化為相鄰兩時(shí)間節(jié)點(diǎn)間結(jié)構(gòu)的相似性,與多目標(biāo)進(jìn)化算法的框架不謀而合。在先前的工作中,一種基于分解的多目標(biāo)社區(qū)結(jié)構(gòu)檢測(cè)進(jìn)化算法已經(jīng)被提出。在此基礎(chǔ)上,為了進(jìn)一步提高算法性能,我們?cè)囼?yàn)了一種局部搜索策略。這種局部搜索策略利用標(biāo)簽傳播的思想,對(duì)每個(gè)時(shí)間點(diǎn)的結(jié)構(gòu)都起著微調(diào)的作用。在動(dòng)態(tài)網(wǎng)絡(luò)上進(jìn)行的一系列實(shí)驗(yàn)體現(xiàn)了該局部算子對(duì)算法性能的提高。
　　總結(jié)本文貢獻(xiàn)如下:
　　(1)解決了基于密度的社區(qū)結(jié)構(gòu)檢測(cè)

5、方法中參數(shù)的選擇問題。我們的方法不僅克服了參數(shù)敏感以及難以選擇的問題,而且找到了所有可能的參數(shù),以參數(shù)為工具,對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行分析,最終結(jié)合進(jìn)化算法,形成了一個(gè)完整的處理社區(qū)結(jié)構(gòu)檢測(cè)問題的新方法,在與其他算法結(jié)果對(duì)比中占優(yōu)。
　　(2)在基于分解的多目標(biāo)優(yōu)化算法的框架下,我們提高了其解決動(dòng)態(tài)社區(qū)結(jié)構(gòu)檢測(cè)的能力。在大量實(shí)驗(yàn)的基礎(chǔ)上,基于標(biāo)簽傳播思想的局部搜索策略確實(shí)提高了目標(biāo)算法的性能,達(dá)到了預(yù)期效果,另外通過實(shí)驗(yàn),假設(shè)合理性與框架合