復(fù)雜網(wǎng)絡(luò)中重疊社區(qū)發(fā)現(xiàn)算法的研究.pdf

1、伴隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，大量的復(fù)雜網(wǎng)絡(luò)和社會(huì)結(jié)構(gòu)正源源不斷的產(chǎn)生。人們對(duì)復(fù)雜網(wǎng)絡(luò)的研究，已經(jīng)從早期的簡(jiǎn)單圖論階段進(jìn)入到了現(xiàn)在的大批網(wǎng)絡(luò)模型與算法并現(xiàn)的繁榮階段。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一種中觀結(jié)構(gòu)，是對(duì)復(fù)雜網(wǎng)絡(luò)某種程度的壓縮，對(duì)了解網(wǎng)絡(luò)結(jié)構(gòu)與功能具有重要意義。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法大都只能發(fā)現(xiàn)非重疊社區(qū)，對(duì)于重疊社區(qū)的發(fā)現(xiàn)算法的研究，目前還處于早期探索階段?，F(xiàn)實(shí)網(wǎng)絡(luò)中存在大量的重疊社區(qū)，如一個(gè)人可以參加多個(gè)興趣小組、一篇學(xué)術(shù)論文可以橫跨多個(gè)學(xué)術(shù)

2、領(lǐng)域、一個(gè)單詞可以具有多個(gè)詞性等等，因此發(fā)現(xiàn)網(wǎng)絡(luò)中具有重疊性的社區(qū)結(jié)構(gòu)往往具有更加實(shí)際的意義。針對(duì)當(dāng)前各種應(yīng)用的需要，本文在探索各種更加有效的重疊社區(qū)發(fā)現(xiàn)算法上進(jìn)行了較系統(tǒng)和深入的研究，并形成了以下主要研究成果：
　　①針對(duì)當(dāng)前基于局部擴(kuò)展類算法的不穩(wěn)定性，提出了一種DOCNR算法。首先，新算法針對(duì) PageRank均勻分配策略進(jìn)行改進(jìn)，形成一種更適應(yīng)于無向圖處理的NodeRank算法，利用NodeRank算法計(jì)算所有網(wǎng)絡(luò)節(jié)點(diǎn)的重

3、要性，并依據(jù)節(jié)點(diǎn)的重要性選取種子節(jié)點(diǎn)。其次，一個(gè)沒有外部鏈接的無向網(wǎng)絡(luò)，經(jīng)過 NodeRank算法處理后，所有節(jié)點(diǎn)的重要度值之和近似保持不變，基于此提出了一種新的適應(yīng)度函數(shù)，并在該適應(yīng)度函數(shù)基礎(chǔ)上，以種子節(jié)點(diǎn)為核心，按照廣度遍歷的思想逐層向外擴(kuò)展社區(qū)，不同的種子節(jié)點(diǎn)擴(kuò)展出的社區(qū)間會(huì)有交集，因此新算法能夠發(fā)現(xiàn)重疊社區(qū)。最后，對(duì)重疊度過高的社區(qū)進(jìn)行合并處理，作為最終計(jì)算結(jié)果。
　?、卺槍?duì)當(dāng)前LFM算法的時(shí)間復(fù)雜度過高以及會(huì)產(chǎn)生大量孤立

4、節(jié)點(diǎn)等不足，提出一種基于貪心策略的快速擴(kuò)張的重疊社區(qū)發(fā)現(xiàn)算法（QLFM）和一種基于先擴(kuò)展后剪枝的重疊社區(qū)發(fā)現(xiàn)算法（ECLFM）。QLFM算法的特點(diǎn)是在適應(yīng)度函數(shù)的基礎(chǔ)上，基于貪心策略逐漸向外擴(kuò)張形成社區(qū)；ECLFM算法則是在適應(yīng)度函數(shù)的基礎(chǔ)上，通過隨機(jī)選取種子節(jié)點(diǎn)并以種子節(jié)點(diǎn)為核心，按照廣度遍歷的思想逐層向外擴(kuò)展社區(qū)，當(dāng)所有節(jié)點(diǎn)不能被擴(kuò)展時(shí)，回溯去除已擴(kuò)展節(jié)點(diǎn)集中所有不滿足適應(yīng)度函數(shù)的節(jié)點(diǎn)。
　　③在一組不同公開數(shù)據(jù)集上將本文算法