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

1、近年來網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測受到越來越多的關(guān)注。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個重要屬性。網(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)系相對稀疏。網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)分析對于理解網(wǎng)絡(luò)子結(jié)構(gòu)的功能、發(fā)現(xiàn)網(wǎng)絡(luò)中的隱藏規(guī)律以及預(yù)測網(wǎng)絡(luò)的行為不僅有十分重要的理論意義,而且有廣泛的應(yīng)用前景。
　　基于密度的方法在社區(qū)結(jié)構(gòu)檢測領(lǐng)域的研究熱度越來越高。這類方法依賴于兩個參數(shù),因此對輸入的參數(shù)極為敏感,導(dǎo)致難以選擇合適

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

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

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

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