基于代數(shù)連通性的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型研究.pdf

1、在復(fù)雜網(wǎng)絡(luò)分析中，社區(qū)發(fā)現(xiàn)是該領(lǐng)域的重要課題。如何快速有效地將復(fù)雜網(wǎng)絡(luò)中的社區(qū)挖掘出來呈現(xiàn)給數(shù)據(jù)的使用者越來越受到研究者的重視。本文基于譜圖理論中的代數(shù)連通性函數(shù)給出三個(gè)復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型。
　　第一個(gè)是基于代數(shù)連通性的譜優(yōu)化復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型。在復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型當(dāng)中，Newman與Girvan的GN模型受到了領(lǐng)域內(nèi)的廣泛關(guān)注，但其時(shí)間復(fù)雜度高。在此基礎(chǔ)上，基于代數(shù)連通性函數(shù)給出了一種合理的解決辦法。代數(shù)連通性函數(shù)可用于測(cè)

2、量網(wǎng)絡(luò)的連通程度。為改善社區(qū)發(fā)現(xiàn)算法的時(shí)間復(fù)雜度，模型基于代數(shù)連通性提出了一種譜優(yōu)化模型。該凸優(yōu)化問題可由半正定規(guī)劃求全局最優(yōu)解，但其時(shí)間復(fù)雜度較高。模型采用貪婪策略優(yōu)化方法，通過最小化網(wǎng)絡(luò)連通性函數(shù)在候選邊集中選擇刪除的邊集。使該模型應(yīng)用于中等規(guī)模網(wǎng)絡(luò)中。
　　第二個(gè)是基于代數(shù)連通性的快速?gòu)?fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型。隨著互聯(lián)網(wǎng)中虛擬社會(huì)網(wǎng)絡(luò)的發(fā)展，處理大規(guī)模網(wǎng)絡(luò)越來越受到人們的重視。Newman等人基于隨機(jī)游走，最短路徑和總有效阻抗提

3、出了邊中心性(Edgebetweenness)的概念。本模型首次基于代數(shù)連通性函數(shù)提出邊中心性測(cè)度，有效降低該測(cè)度計(jì)算的時(shí)間復(fù)雜度，從而設(shè)計(jì)出線性的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法。當(dāng)社區(qū)混合度不高時(shí)，模型準(zhǔn)確地識(shí)別社區(qū)，但當(dāng)社區(qū)混合度升高時(shí)算法準(zhǔn)確度下降較快。
　　第三個(gè)是基于代數(shù)連通性的自動(dòng)標(biāo)注社會(huì)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型，本模型分為分割步驟和標(biāo)注步驟。本模型根據(jù)社會(huì)網(wǎng)絡(luò)的節(jié)點(diǎn)特性將中心節(jié)點(diǎn)刪除，有效降低社區(qū)間的混合程度，同時(shí)由于社區(qū)內(nèi)的龐大節(jié)點(diǎn)

4、集，社區(qū)依然緊密地聚集在一起。分割步驟結(jié)束后，根據(jù)已標(biāo)注節(jié)點(diǎn)信息去標(biāo)注未標(biāo)注節(jié)點(diǎn)，并更新已標(biāo)注節(jié)點(diǎn)，得到社區(qū)結(jié)果。
　　本文采用常用的LRFbenchmark生成的虛擬復(fù)雜網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)對(duì)本文提到的模型進(jìn)行評(píng)價(jià)。結(jié)果表明基于代數(shù)連通性的譜優(yōu)化復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型有效降低了GN算法的迭代次數(shù)，一定程度上降低其時(shí)間復(fù)雜度，并有效保持其分割效果?；诖鷶?shù)連通性的快速?gòu)?fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)模型是當(dāng)今最快的社區(qū)發(fā)現(xiàn)模型之一，在社區(qū)混合度不高的復(fù)雜