復(fù)雜網(wǎng)絡(luò)重疊社區(qū)挖掘算法研究與設(shè)計(jì).pdf

1、復(fù)雜網(wǎng)絡(luò)是目前計(jì)算機(jī)科學(xué)、社會(huì)學(xué)等多學(xué)科共同研究的熱門(mén)課題之一。所謂復(fù)雜網(wǎng)絡(luò)，是指網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)復(fù)雜多樣，同時(shí)有許多獨(dú)特的性質(zhì)。模塊性即社區(qū)結(jié)構(gòu)就是其中非常重要的一個(gè)特性，表現(xiàn)為網(wǎng)絡(luò)中社區(qū)內(nèi)部節(jié)點(diǎn)關(guān)系緊密、社區(qū)之間節(jié)點(diǎn)關(guān)系稀疏，且由于網(wǎng)絡(luò)的復(fù)雜性，社區(qū)之間普遍存在重疊現(xiàn)象。因而重疊社區(qū)的挖掘研究代替非重疊社區(qū)成為當(dāng)前復(fù)雜網(wǎng)絡(luò)的研究熱點(diǎn)，研究結(jié)果更能揭示真實(shí)網(wǎng)絡(luò)的結(jié)構(gòu)特性和潛在規(guī)律，也是本論文的主要研究點(diǎn)。
　　重疊社區(qū)的挖掘算法主要

2、可分為基于全局信息與局部信息兩大類(lèi)。局部方法因其計(jì)算量少、無(wú)需驗(yàn)證網(wǎng)絡(luò)先驗(yàn)知識(shí)等優(yōu)點(diǎn)越來(lái)越受到研究者的青睞。但隨著復(fù)雜網(wǎng)絡(luò)規(guī)模與數(shù)據(jù)量的不斷增大，局部挖掘方法的難度也逐步升級(jí)，提高社區(qū)挖掘精度和降低時(shí)間復(fù)雜度仍是當(dāng)前研究的主要目標(biāo)。
　　為提高重疊社區(qū)挖掘質(zhì)量，論文設(shè)計(jì)了一種基于核心節(jié)點(diǎn)的局部社區(qū)挖掘算法COCMA。該算法主要是對(duì)傳統(tǒng)局部挖掘算法中初始節(jié)點(diǎn)選取、局部社區(qū)擴(kuò)展階段進(jìn)行了改進(jìn)：初始節(jié)點(diǎn)的選取采用了優(yōu)化策略，即以網(wǎng)絡(luò)中綜

3、合影響力大的節(jié)點(diǎn)為核心節(jié)點(diǎn)，然后以該節(jié)點(diǎn)為挖掘中心進(jìn)行局部社區(qū)擴(kuò)展；擴(kuò)展過(guò)程的改進(jìn)在于適應(yīng)度函數(shù)的設(shè)計(jì)綜合考慮社區(qū)聚集度與社區(qū)自身密度兩個(gè)因素以適用更多的社區(qū)挖掘場(chǎng)景。經(jīng)驗(yàn)證，改進(jìn)的算法與主流局部算法相比，有更好的挖掘質(zhì)量。
　　為提高大型復(fù)雜網(wǎng)絡(luò)中重疊社區(qū)挖掘算法的運(yùn)行效率，論文設(shè)計(jì)了一種基于核心子團(tuán)的社區(qū)挖掘算法。論文算法的設(shè)計(jì)依據(jù)是基于對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)分布情況的分析，結(jié)果發(fā)現(xiàn)網(wǎng)絡(luò)中重疊節(jié)點(diǎn)只占了節(jié)點(diǎn)總數(shù)很小的一部分，而傳統(tǒng)重疊算

4、法對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行多次重復(fù)計(jì)算。為此論文提出以核心子團(tuán)，即網(wǎng)絡(luò)中核心節(jié)點(diǎn)與其直接鄰居構(gòu)成的子團(tuán)為社區(qū)擴(kuò)展基礎(chǔ)，以?xún)晒?jié)點(diǎn)間路徑長(zhǎng)度為其緊密度衡量指標(biāo)，通過(guò)該方法對(duì)核心子團(tuán)的分布進(jìn)行調(diào)整，挖掘網(wǎng)絡(luò)主要的社區(qū)結(jié)構(gòu)，識(shí)別網(wǎng)絡(luò)潛在重疊節(jié)點(diǎn)，然后僅對(duì)這些節(jié)點(diǎn)進(jìn)行多次計(jì)算以完成潛在重疊節(jié)點(diǎn)的多社區(qū)分配，從而大幅度減少計(jì)算量，提高算法的運(yùn)行效率。實(shí)驗(yàn)結(jié)果表明：改進(jìn)的算法在挖掘大規(guī)模復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)時(shí)有著明顯的速度優(yōu)勢(shì)，挖掘質(zhì)量與同類(lèi)算法相比也更高