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

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 模塊度 社區(qū)結(jié)構(gòu) 標(biāo)簽傳播 社區(qū)發(fā)現(xiàn)

【摘要】：隨著網(wǎng)絡(luò)的迅速發(fā)展,對復(fù)雜網(wǎng)絡(luò)的研究在許多領(lǐng)域都備受關(guān)注。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個普遍特征,對社區(qū)結(jié)構(gòu)的挖掘成為了網(wǎng)絡(luò)分析中的研究熱點。復(fù)雜網(wǎng)絡(luò)由許許多多個社區(qū)構(gòu)成,社區(qū)發(fā)現(xiàn)對于了解復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)有著重要的意義。從計算角度而言,社區(qū)劃分相當(dāng)于將任務(wù)分解,可以降低計算復(fù)雜度;從實際應(yīng)用而言,社區(qū)發(fā)現(xiàn)“產(chǎn)生”了推薦,方便了人們的生活。本文針對社區(qū)發(fā)現(xiàn)問題,結(jié)合社區(qū)結(jié)構(gòu)這個重要屬性,利用模塊度最大化方法對社區(qū)發(fā)現(xiàn)算法中的時間復(fù)雜度以及社區(qū)結(jié)構(gòu)的強(qiáng)弱展開了深入研究。首先,針對基于模塊度最大化這類標(biāo)簽傳播算法中時間復(fù)雜度高的問題,本文依據(jù)“先傳播,后合并”的原則,降低了社區(qū)合并導(dǎo)致整個網(wǎng)絡(luò)需要更新帶來的較高時間復(fù)雜度;結(jié)合社區(qū)結(jié)構(gòu)的概念提出了基于模塊度最大化的標(biāo)簽傳播算法CDMM-LPA�；谏鐓^(qū)結(jié)構(gòu)的重要性,本文將社區(qū)結(jié)構(gòu)作為一個重要的考慮因素融入CDMM-LPA算法中,使得最終獲得的社區(qū)屬于強(qiáng)結(jié)構(gòu)社區(qū)。其次,提出了基于模塊度最大化的雙向合并的社區(qū)發(fā)現(xiàn)算法CDPM。CDPM算法是基于混合式合并的社區(qū)發(fā)現(xiàn)的改進(jìn)算法。該算法通過計算節(jié)點之間的相似度,減少算法初始階段生成的子社區(qū)數(shù)目。通過檢查生成的社區(qū)是否含有弱結(jié)構(gòu)社區(qū)來決定CDPM算法的運(yùn)行次數(shù),避免了通過設(shè)置參數(shù)來控制算法的執(zhí)行次數(shù),從而降低了CDPM算法的時間復(fù)雜度。最后,基于真實網(wǎng)絡(luò)數(shù)據(jù)集和模擬生成的網(wǎng)絡(luò)數(shù)據(jù)集,驗證并分析了兩種算法的可行性。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 模塊度 社區(qū)結(jié)構(gòu) 標(biāo)簽傳播 社區(qū)發(fā)現(xiàn)
【學(xué)位授予單位】：燕山大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：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 本文組織結(jié)構(gòu)14-15
• 第2章 社區(qū)發(fā)現(xiàn)算法中的相關(guān)概念15-23
• 2.1 社區(qū)15
• 2.1.1 社區(qū)概述15
• 2.1.2 社區(qū)性質(zhì)15
• 2.2 社區(qū)結(jié)構(gòu)15-16
• 2.3 社區(qū)結(jié)構(gòu)評價標(biāo)準(zhǔn)16-18
• 2.3.1 模塊度16-18
• 2.4 基于層次聚類的相關(guān)算法18-20
• 2.4.1 GN算法18-19
• 2.4.2 基于混合式合并的社區(qū)發(fā)現(xiàn)算法19-20
• 2.5 基于標(biāo)簽傳播的相關(guān)算法20-22
• 2.5.1 基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法20-21
• 2.5.2 LPAm+算法21-22
• 2.6 本章小結(jié)22-23
• 第3章 基于模塊度最大化的標(biāo)簽傳播算法23-33
• 3.1 算法描述23-26
• 3.1.1 相關(guān)定義23-26
• 3.2 算法實現(xiàn)過程26-32
• 3.2.1 劃分網(wǎng)絡(luò)27
• 3.2.2 更新標(biāo)簽27
• 3.2.3 算法部分偽代碼27-29
• 3.2.4 實例說明29-32
• 3.3 本章小結(jié)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 本章小結(jié)39-40
• 第5章 算法的實驗結(jié)果分析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 本章小結(jié)50-51
• 結(jié)論51-53
• 參考文獻(xiàn)53-57
• 攻讀碩士學(xué)位期間承擔(dān)的科研任務(wù)與主要成果57-58
• 致謝58-59
• 作者簡介59

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：1053388