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

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

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