復雜網(wǎng)絡中的社團檢測問題研究.pdf

1、近年來,由于信息技術(shù)的飛速發(fā)展,科學家和學者們能夠越來越容易地在現(xiàn)實世界中收集到高通量的網(wǎng)絡數(shù)據(jù),這使得復雜網(wǎng)絡的研究變得炙手可熱起來。除了Watts和Strogatz在1998年發(fā)現(xiàn)的小世界特性以及Barabási和Albert在1999年發(fā)現(xiàn)的無標度(尺度)特性外,網(wǎng)絡的社團(社區(qū)、模塊)結(jié)構(gòu)特性被認為是復雜網(wǎng)絡中最重要的統(tǒng)計特性之一。目前,關于網(wǎng)絡中的社團仍然不存在統(tǒng)一的定義,通常指的是滿足下面條件的節(jié)點子集:子集內(nèi)部節(jié)點之間具有

2、稠密的連接,而與子集外部的節(jié)點具有稀疏的連接。研究表明,網(wǎng)絡的這種社團結(jié)構(gòu)與某些功能屬性有著緊密的聯(lián)系,比如網(wǎng)絡的魯棒性和信息快速傳遞特性等。因此在網(wǎng)絡中描述和檢測這些社團結(jié)構(gòu)具有重要的實際意義并已成為近幾年來的研究熱點。
　　 本論文中,我們主要關注復雜網(wǎng)絡中社團結(jié)構(gòu)檢測相關問題的研究,取得的主要研究成果如下:
　　 1.提出了一種新的社團檢測方法-JEOMD。該方法以加入懲罰項的模塊密度函數(shù)D作為指標函數(shù),并使用跳躍

3、極值最優(yōu)化方法來優(yōu)化該指標函數(shù),能夠得到網(wǎng)絡的層次分割結(jié)果。在一組真實網(wǎng)絡上的實驗表明,與基于模塊化函數(shù)Q的優(yōu)化方法相比,JEOMD方法能夠更有效地檢測出網(wǎng)絡中存在的不同層次和不同規(guī)模的社團結(jié)構(gòu)。在該組真實網(wǎng)絡及其對應的隨機網(wǎng)絡上的對比實驗表明,加入懲罰項的模塊密度函數(shù)D作為社團檢測的指標函數(shù)在一定程度上比模塊化函數(shù)Q更有效。
　　 2.提出了一個新的衡量社團劃分質(zhì)量的指標函數(shù),稱之為標準化模塊密度(normalized mod

4、ularity density-NMD)。在示例網(wǎng)絡中證明了NMD能夠改善模塊化函數(shù)Q中存在的分辨率極限問題；證明了NMD與圖分割中廣泛應用的normalized-cut目標函數(shù)存在著緊密的聯(lián)系,即當社團數(shù)目m已知時,最大化標準化模塊密度相當于最小化目標函數(shù)normalized-cut。使用改進的模擬退火算法優(yōu)化指標NMD。在一組模擬網(wǎng)絡上的實驗表明,與基于模塊化函數(shù)Q的優(yōu)化方法相比,基于NMD的方法能夠取得更高的檢測正確率；在一組真實

5、網(wǎng)絡上的實驗表明,基于NMD的方法能夠檢測出網(wǎng)絡中更精細的模塊結(jié)構(gòu),從而為NMD能夠改善Q的分辨率問題提供了更進一步的證據(jù)；
　　 把指標函數(shù)NMD和D推廣到其加權(quán)形式NMDw和Dw,并用于在加權(quán)網(wǎng)絡中進行社團檢測。分析了加權(quán)模塊化函數(shù)Qw同樣存在分辨率極限問題；指出了加權(quán)模塊密度函數(shù)Dw存在的負社團問題；在兩個實例網(wǎng)絡上證明了NMDw不僅能夠克服Qw中存在的分辨率極限問題,而且能夠避免Dw中出現(xiàn)的負社團問題。為了比較指標NMD

6、w與Qw和Dw在加權(quán)網(wǎng)絡社團檢測中的性能,使用模擬退火算法實現(xiàn)三個指標的優(yōu)化。在一組模擬網(wǎng)絡上的實驗表明,優(yōu)化NMDw指標能夠取得比優(yōu)化Qw和Dw更高的檢測正確率；在一組真實網(wǎng)絡上的實驗表明,優(yōu)化NMDw指標,不僅能夠從加權(quán)網(wǎng)絡中檢測出精細尺度下的社團,尤其是優(yōu)化Qw所不能檢測出來的小而稠密的社團,而且能夠避免優(yōu)化Dw時出現(xiàn)的負社團問題。
　　 3.提出了一種基于自適應核仿射傳播的網(wǎng)絡社團檢測方法-AKAP。在該方法中,標準化的

7、馬爾可夫擴散核(Markov diffusion kernel)被用來隱式地衡量節(jié)點之間的非相似度,引入自適應仿射傳播方法優(yōu)化得到的非相似度矩陣。在模擬網(wǎng)絡上的實驗表明,與Newman快速算法相比,AKAP方法能夠取得更高的檢測正確率；在一組真實網(wǎng)絡上的實驗表明,AKAP方法能夠有效地檢測出網(wǎng)絡中存在的有意義的社團結(jié)構(gòu)和包含的社團數(shù)目。
　　 4.提出了一種有效的網(wǎng)絡節(jié)點的可視化方法。在該方法中,定義了一種新的節(jié)點間距離,將得到