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

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

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

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

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