本文關鍵詞：基于模塊度最大化的社區(qū)發(fā)現(xiàn)算法的研究

  更多相關文章： 復雜網(wǎng)絡 模塊度 社區(qū)結構 標簽傳播 社區(qū)發(fā)現(xiàn)

【摘要】：隨著網(wǎng)絡的迅速發(fā)展,對復雜網(wǎng)絡的研究在許多領域都備受關注。社區(qū)結構是復雜網(wǎng)絡的一個普遍特征,對社區(qū)結構的挖掘成為了網(wǎng)絡分析中的研究熱點。復雜網(wǎng)絡由許許多多個社區(qū)構成,社區(qū)發(fā)現(xiàn)對于了解復雜網(wǎng)絡中的社區(qū)結構有著重要的意義。從計算角度而言,社區(qū)劃分相當于將任務分解,可以降低計算復雜度;從實際應用而言,社區(qū)發(fā)現(xiàn)“產(chǎn)生”了推薦,方便了人們的生活。本文針對社區(qū)發(fā)現(xiàn)問題,結合社區(qū)結構這個重要屬性,利用模塊度最大化方法對社區(qū)發(fā)現(xiàn)算法中的時間復雜度以及社區(qū)結構的強弱展開了深入研究。首先,針對基于模塊度最大化這類標簽傳播算法中時間復雜度高的問題,本文依據(jù)“先傳播,后合并”的原則,降低了社區(qū)合并導致整個網(wǎng)絡需要更新帶來的較高時間復雜度;結合社區(qū)結構的概念提出了基于模塊度最大化的標簽傳播算法CDMM-LPA。基于社區(qū)結構的重要性,本文將社區(qū)結構作為一個重要的考慮因素融入CDMM-LPA算法中,使得最終獲得的社區(qū)屬于強結構社區(qū)。其次,提出了基于模塊度最大化的雙向合并的社區(qū)發(fā)現(xiàn)算法CDPM。CDPM算法是基于混合式合并的社區(qū)發(fā)現(xiàn)的改進算法。該算法通過計算節(jié)點之間的相似度,減少算法初始階段生成的子社區(qū)數(shù)目。通過檢查生成的社區(qū)是否含有弱結構社區(qū)來決定CDPM算法的運行次數(shù),避免了通過設置參數(shù)來控制算法的執(zhí)行次數(shù),從而降低了CDPM算法的時間復雜度。最后,基于真實網(wǎng)絡數(shù)據(jù)集和模擬生成的網(wǎng)絡數(shù)據(jù)集,驗證并分析了兩種算法的可行性。
【關鍵詞】：復雜網(wǎng)絡 模塊度 社區(qū)結構 標簽傳播 社區(qū)發(fā)現(xiàn)
【學位授予單位】：燕山大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP301.6;O157.5
【目錄】：

• 摘要5-6
• Abstract6-9
• 第1章 緒論9-15
• 1.1 研究的背景及意義9-10
• 1.2 國內(nèi)外研究現(xiàn)狀10-14
• 1.2.1 國外研究現(xiàn)狀11-12
• 1.2.2 國內(nèi)研究現(xiàn)狀12-14
• 1.3 本文研究的內(nèi)容14
• 1.4 本文組織結構14-15
• 第2章 社區(qū)發(fā)現(xiàn)算法中的相關概念15-23
• 2.1 社區(qū)15
• 2.1.1 社區(qū)概述15
• 2.1.2 社區(qū)性質15
• 2.2 社區(qū)結構15-16
• 2.3 社區(qū)結構評價標準16-18
• 2.3.1 模塊度16-18
• 2.4 基于層次聚類的相關算法18-20
• 2.4.1 GN算法18-19
• 2.4.2 基于混合式合并的社區(qū)發(fā)現(xiàn)算法19-20
• 2.5 基于標簽傳播的相關算法20-22
• 2.5.1 基于標簽傳播的社區(qū)發(fā)現(xiàn)算法20-21
• 2.5.2 LPAm+算法21-22
• 2.6 本章小結22-23
• 第3章 基于模塊度最大化的標簽傳播算法23-33
• 3.1 算法描述23-26
• 3.1.1 相關定義23-26
• 3.2 算法實現(xiàn)過程26-32
• 3.2.1 劃分網(wǎng)絡27
• 3.2.2 更新標簽27
• 3.2.3 算法部分偽代碼27-29
• 3.2.4 實例說明29-32
• 3.3 本章小結32-33
• 第4章 基于雙向合并的社區(qū)發(fā)現(xiàn)算法33-40
• 4.1 雙向合并的社區(qū)發(fā)現(xiàn)算法的描述33-35
• 4.1.1 層次聚類思想33
• 4.1.2 選取相似度33-34
• 4.1.3 雙向合并34-35
• 4.2 算法的實現(xiàn)35-36
• 4.2.1 算法舉例35-36
• 4.3 算法的部分偽代碼36-39
• 4.4 本章小結39-40
• 第5章 算法的實驗結果分析40-51
• 5.1 實驗環(huán)境的基本配置40
• 5.2 CDMM-LPA算法40-45
• 5.2.1 實驗數(shù)據(jù)40-44
• 5.2.2 不同算法之間的比較44-45
• 5.3 CDPM算法45-50
• 5.3.1 真實數(shù)據(jù)集實驗46-48
• 5.3.2 模擬數(shù)據(jù)集實驗48-50
• 5.4 本章小結50-51
• 結論51-53
• 參考文獻53-57
• 攻讀碩士學位期間承擔的科研任務與主要成果57-58
• 致謝58-59
• 作者簡介59

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 智源;行飛;;復雜網(wǎng)絡社區(qū)結構問題綜述[J];陰山學刊(自然科學);2011年03期

2 王林;戴冠中;趙煥成;;一種新的評價社區(qū)結構的模塊度研究[J];計算機工程;2010年14期

3 韓瑞凱;孟嗣儀;劉云;郭英慧;張彥超;;基于興趣相似度的社區(qū)結構發(fā)現(xiàn)算法研究[J];鐵路計算機應用;2010年10期

4 劉旭;易東云;;基于保守合并策略的復雜網(wǎng)絡社區(qū)結構發(fā)現(xiàn)[J];復雜系統(tǒng)與復雜性科學;2011年04期

5 黃發(fā)良;肖南峰;;用于網(wǎng)絡重疊社區(qū)發(fā)現(xiàn)的粗糙譜聚類算法[J];小型微型計算機系統(tǒng);2012年02期

6 馬瑞新;鄧貴仕;王曉;;啟發(fā)式動態(tài)社區(qū)挖掘算法研究與實現(xiàn)[J];大連理工大學學報;2012年02期

7 梁沙沙;;復雜網(wǎng)絡重疊社區(qū)結構發(fā)現(xiàn)算法研究[J];陰山學刊(自然科學);2013年02期

8 劉大有;金弟;何東曉;黃晶;楊建寧;楊博;;復雜網(wǎng)絡社區(qū)挖掘綜述[J];計算機研究與發(fā)展;2013年10期

9 時京晶;;三種經(jīng)典復雜網(wǎng)絡社區(qū)結構劃分算法研究[J];電腦與信息技術;2011年04期

10 黃發(fā)良;肖南峰;;基于線圖與PSO的網(wǎng)絡重疊社區(qū)發(fā)現(xiàn)[J];自動化學報;2011年09期

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 刁元波;李夢龍;文志寧;印家健;鄭波;;人類細胞信號網(wǎng)絡社區(qū)結構分析[A];第九屆全國計算（機）化學學術會議論文摘要集[C];2007年

2 劉欣;李德毅;李兵;王樹良;陶志偉;;復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)研究[A];2006全國復雜網(wǎng)絡學術會議論文集[C];2006年

3 單波;姜守旭;張碩;高宏;李建中;;IC:動態(tài)社會關系網(wǎng)絡社區(qū)結構的增量識別算法[A];第26屆中國數(shù)據(jù)庫學術會議論文集（A輯）[C];2009年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 記者 熊明 實習生 李瑞瑩;度假區(qū)不斷創(chuàng)新社區(qū)結構[N];云南日報;2013年

中國博士學位論文全文數(shù)據(jù)庫 前7條

1 閔磊;復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)算法研究[D];華中師范大學;2015年

2 蔡清;基于群體智能優(yōu)化的大數(shù)據(jù)復雜網(wǎng)絡結構分析[D];西安電子科技大學;2015年

3 杜楠;復雜網(wǎng)絡中社區(qū)結構發(fā)現(xiàn)算法研究及建模[D];北京郵電大學;2009年

4 李一嘯;基于復雜網(wǎng)絡和演化博弈理論的社會[D];浙江大學;2010年

5 韓院彬;Web服務網(wǎng)絡分析和社區(qū)發(fā)現(xiàn)研究[D];天津大學;2014年

6 謝輝;基于復雜網(wǎng)絡的若干動態(tài)機制研究[D];西安電子科技大學;2013年

7 任薇;基于微博的社會網(wǎng)絡特征研究[D];西南大學;2014年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 王童童;社區(qū)框架與隱藏社區(qū)的挖掘[D];山東建筑大學;2015年

2 賀成龍;復雜網(wǎng)絡中的社區(qū)發(fā)現(xiàn)算法研究[D];解放軍信息工程大學;2015年

3 賈娜;基于矩陣分解的重疊社區(qū)探測研究[D];吉林大學;2016年

4 李青云;多階信息模型及推薦技術研究[D];北京理工大學;2015年

5 萬云;基于模塊度最大化的社區(qū)發(fā)現(xiàn)算法的研究[D];燕山大學;2016年

6 戴飛飛;基于進化算法的復雜網(wǎng)絡社區(qū)結構發(fā)現(xiàn)[D];電子科技大學;2008年

7 王熙;復雜網(wǎng)絡中的層次重疊社區(qū)發(fā)現(xiàn)及可視化[D];北京交通大學;2010年

8 徐李恒;復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)方法研究[D];太原理工大學;2011年

9 李兆南;基于距離相似度的復雜網(wǎng)絡社區(qū)挖掘方法[D];吉林大學;2011年

10 商源純;復雜網(wǎng)絡中的重疊社區(qū)發(fā)現(xiàn)算法研究[D];北京交通大學;2011年

，

本文編號：1053388