基于泛化模塊密度的社團(tuán)檢測算法研究與應(yīng)用.pdf

1、近年來，復(fù)雜網(wǎng)絡(luò)逐漸成為描述與分析現(xiàn)實(shí)復(fù)雜系統(tǒng)的重要工具而備受關(guān)注。復(fù)雜網(wǎng)絡(luò)的大規(guī)模性、強(qiáng)耦合性、局部性等特點(diǎn)促使研究人員通過局部特性來刻畫與研究整體特性。其中，社團(tuán)結(jié)構(gòu)作為一種局部研究方法在計(jì)算機(jī)科學(xué)、生物信息學(xué)和社會學(xué)等多個領(lǐng)域都有重要的意義。
　　在社團(tuán)檢測算法中如何有效量化社團(tuán)劃分結(jié)果及如何設(shè)計(jì)出高效、準(zhǔn)確的算法是兩大關(guān)鍵問題所在。為了解決社團(tuán)量化的問題，Newman等在對比真實(shí)網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)的基礎(chǔ)上提出了模塊度函數(shù)。盡管

2、最大化模塊度函數(shù)屬于NP-難問題，但絕大多數(shù)算法都是基于優(yōu)化模塊度函數(shù)。針對于模塊度函數(shù)存在的分辨極限問題，李等通過對比社團(tuán)內(nèi)部邊和外部邊密度提出了模塊密度函數(shù)，并證明了該測量標(biāo)準(zhǔn)可以在很大程度上克服分辨極限問題。但是模塊密度只能應(yīng)用于無權(quán)圖。在真實(shí)網(wǎng)絡(luò)中，給每一個節(jié)點(diǎn)賦予相同的權(quán)重并不合理。為了克服該缺陷，本文提出了一種泛化的模塊密度。并設(shè)計(jì)出基于優(yōu)化加權(quán)模塊密度的模擬退火算法。實(shí)驗(yàn)結(jié)果表明該測度更加有效的刻畫網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。