復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測(cè)問題研究.pdf

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

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

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

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

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

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

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