本文關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：對(duì)于任何包含大量個(gè)體單元的復(fù)雜系統(tǒng)來說,我們都可以將其看作復(fù)雜網(wǎng)絡(luò)來研究,復(fù)雜網(wǎng)絡(luò)具有小世界、無標(biāo)度和社團(tuán)結(jié)構(gòu)等諸多特征。社團(tuán)結(jié)構(gòu)主要刻畫了網(wǎng)絡(luò)中節(jié)點(diǎn)之間的相互關(guān)系,社團(tuán)結(jié)構(gòu)具有處于社團(tuán)內(nèi)部的節(jié)點(diǎn)聯(lián)系較為緊密,處于社團(tuán)之間的節(jié)點(diǎn)聯(lián)系較為稀疏的顯著特點(diǎn),深入了解復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)有助于發(fā)現(xiàn)網(wǎng)絡(luò)中潛藏著的規(guī)律和預(yù)測(cè)網(wǎng)絡(luò)的行為。本文依據(jù)優(yōu)化、啟發(fā)式和相似度等不同的策略對(duì)常用社團(tuán)劃分算法進(jìn)行了分類,并對(duì)其中的典型代表算法進(jìn)行了詳細(xì)的研究分析。針對(duì)相似度算法中存在的問題,本文提出了基于相似度的三元社團(tuán)合并算法(Ternary Community Merging Algorithm based on Similarity,STCMA)。然后,本文將三元社團(tuán)的概念應(yīng)用于傳統(tǒng)標(biāo)簽傳播算法(Label Propagation Algorithm,LPA),進(jìn)一步提出了基于三元社團(tuán)的LPA算法(Label Propagation Algorithm based on Ternary Community,TCLPA)。(1)基于相似度的三元社團(tuán)合并算法為解決在使用相似度判別哪些節(jié)點(diǎn)應(yīng)該被放入同一個(gè)社團(tuán)時(shí)可能出現(xiàn)的沖突問題,該算法構(gòu)建了三元社團(tuán),并將三元社團(tuán)作為網(wǎng)絡(luò)中社團(tuán)合并的基本元素。該算法通過引入三元社團(tuán),有效地增強(qiáng)了社團(tuán)內(nèi)部節(jié)點(diǎn)之間連接的緊密程度,更加清晰的凸顯了網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。該算法的時(shí)間復(fù)雜度為??2O tm n,其中n代表網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目,m代表連邊數(shù)目,t代表節(jié)點(diǎn)相似度閾值更新的次數(shù),該算法的提出能夠較好的均衡時(shí)間復(fù)雜度與正確劃分率兩者之間的關(guān)系。(2)基于三元社團(tuán)的LPA算法針對(duì)傳統(tǒng)LPA算法中存在的兩大不確定問題,一是在對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的標(biāo)簽信息進(jìn)行更改時(shí)其節(jié)點(diǎn)更新順序的不確定問題;二是在鄰居節(jié)點(diǎn)集合中具有節(jié)點(diǎn)數(shù)目最多的標(biāo)簽信息類型不惟一時(shí)從中選取標(biāo)簽信息的不確定問題,該算法在三元社團(tuán)的基礎(chǔ)上構(gòu)建了網(wǎng)絡(luò)的初始核心社團(tuán),然后結(jié)合局部最優(yōu)規(guī)則和深度計(jì)算規(guī)則計(jì)算網(wǎng)絡(luò)中其他節(jié)點(diǎn)的標(biāo)簽依賴度,并據(jù)此對(duì)這些節(jié)點(diǎn)的標(biāo)簽信息做相應(yīng)標(biāo)記。本文分別采用人工合成網(wǎng)絡(luò)與真實(shí)世界網(wǎng)絡(luò)對(duì)提出的兩種算法進(jìn)行實(shí)驗(yàn)驗(yàn)證,通過標(biāo)準(zhǔn)化互信息、正確劃分率和模塊度等指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析,同時(shí)將本文提出的兩種算法與常用社團(tuán)劃分算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明本文提出的兩種算法不僅具有較高的劃分精度,而且在運(yùn)行效率方面也有著較好的表現(xiàn)。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 社團(tuán)劃分 相似度 三元社團(tuán) 標(biāo)簽傳播
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-6
• ABSTRACT6-13
• 第一章 緒論13-21
• 1.1 研究背景及意義13-15
• 1.1.1 研究背景13-14
• 1.1.2 研究意義14-15
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀15-17
• 1.3 論文主要研究?jī)?nèi)容17-18
• 1.4 論文組織結(jié)構(gòu)18-21
• 第二章 相關(guān)理論與技術(shù)21-29
• 2.1 復(fù)雜網(wǎng)絡(luò)相關(guān)理論21-24
• 2.1.1 復(fù)雜網(wǎng)絡(luò)的表示方法21-22
• 2.1.2 復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特征22-24
• 2.2 社團(tuán)結(jié)構(gòu)相關(guān)理論24-27
• 2.2.1 社團(tuán)結(jié)構(gòu)的定義24-26
• 2.2.2 模塊度定義26-27
• 2.3 本章小結(jié)27-29
• 第三章 常用社團(tuán)劃分算法研究29-45
• 3.1 基于優(yōu)化的算法29-36
• 3.1.1 Kernighan-Lin算法30-31
• 3.1.2 Fast Newman算法31-33
• 3.1.3 CNM算法33-36
• 3.2 基于啟發(fā)式的算法36-41
• 3.2.1 GN算法36-39
• 3.2.2 快速分裂算法39-41
• 3.3 基于相似度的算法41-44
• 3.3.1 基于節(jié)點(diǎn)依賴度的算法41-44
• 3.4 本章小結(jié)44-45
• 第四章 基于相似度的三元社團(tuán)合并算法45-55
• 4.1 問題描述45
• 4.2 算法演化模型45-46
• 4.3 算法介紹46-54
• 4.3.1 算法相關(guān)定義46-48
• 4.3.2 算法核心思想48
• 4.3.3 算法具體執(zhí)行步驟及示例48-53
• 4.3.4 算法偽代碼及復(fù)雜度分析53-54
• 4.4 本章小結(jié)54-55
• 第五章 基于三元社團(tuán)的LPA算法55-63
• 5.1 傳統(tǒng)LPA算法55-56
• 5.2 問題描述56-58
• 5.3 算法介紹58-61
• 5.3.1 算法相關(guān)定義及規(guī)則58-59
• 5.3.2 算法核心思想59
• 5.3.3 算法具體執(zhí)行步驟及示例59-61
• 5.4 本章小結(jié)61-63
• 第六章 算法驗(yàn)證與分析63-75
• 6.1 實(shí)驗(yàn)數(shù)據(jù)集63-64
• 6.1.1 人工合成網(wǎng)絡(luò)數(shù)據(jù)集63
• 6.1.2 真實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)集63-64
• 6.2 社團(tuán)結(jié)構(gòu)質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)64-66
• 6.3 人工合成網(wǎng)絡(luò)實(shí)驗(yàn)分析66-67
• 6.4 真實(shí)世界網(wǎng)絡(luò)實(shí)驗(yàn)分析67-71
• 6.4.1 Zachary空手道俱樂部成員關(guān)系網(wǎng)絡(luò)67-70
• 6.4.2 美國(guó)大學(xué)足球聯(lián)賽網(wǎng)絡(luò)70-71
• 6.5 算法比較分析71-73
• 6.6 本章小結(jié)73-75
• 第七章 總結(jié)與展望75-77
• 7.1 總結(jié)75-76
• 7.2 展望76-77
• 參考文獻(xiàn)77-81
• 致謝81-83
• 攻讀碩士學(xué)位期間已發(fā)表或錄用的論文83

【相似文獻(xiàn)】

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

1 冷明平;孫凌宇;郭愷強(qiáng);邊計(jì)年;朱平;;賦權(quán)超圖劃分算法的電路劃分實(shí)驗(yàn)比較研究[J];計(jì)算機(jī)工程與應(yīng)用;2012年16期

2 許金鳳;董一鴻;王詩(shī)懿;何賢芒;陳華輝;;大規(guī)模圖數(shù)據(jù)劃分算法綜述[J];電信科學(xué);2014年07期

3 李莉杰;陳端兵;王冠楠;;有向網(wǎng)絡(luò)重疊社區(qū)的快速劃分算法[J];計(jì)算機(jī)科學(xué);2014年S1期

4 盧風(fēng)順;宋君強(qiáng);張理論;張衛(wèi)民;任開軍;朱小謙;;面向全球數(shù)值天氣預(yù)報(bào)模式的加權(quán)等積并行數(shù)據(jù)劃分算法[J];計(jì)算機(jī)研究與發(fā)展;2012年04期

5 喻云峰;賴海濤;;一種基于隨機(jī)搜索的黑洞二劃分算法實(shí)現(xiàn)[J];科技廣場(chǎng);2006年04期

6 李晨;葛聲;;一種重疊可信社團(tuán)劃分算法的設(shè)計(jì)與實(shí)現(xiàn)[J];微計(jì)算機(jī)信息;2011年09期

7 李孝偉;陳福才;劉力雄;;一種融合節(jié)點(diǎn)與鏈接屬性的社交網(wǎng)絡(luò)社區(qū)劃分算法[J];計(jì)算機(jī)應(yīng)用研究;2013年05期

8 牛建軍;劉上乾;韓寶君;任寶文;;同心圓檢測(cè)中的區(qū)域劃分算法[J];光子學(xué)報(bào);2006年12期

9 呂德奎;;聚合算法在電力GIS中的應(yīng)用[J];電力信息化;2012年05期

10 王曉芳;賈宗維;;一種新的圖劃分算法在PPI網(wǎng)絡(luò)模塊化中的研究[J];山西農(nóng)業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年06期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前4條

1 王玲娜;李興明;;基于最小支撐樹的通用區(qū)域劃分算法[A];2008年中國(guó)西部青年通信學(xué)術(shù)會(huì)議論文集[C];2008年

2 徐丹丹;章勇;;一種基于節(jié)點(diǎn)度更新的簇劃分算法[A];2008通信理論與技術(shù)新發(fā)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（下）[C];2008年

3 劉培強(qiáng);謝青松;朱大銘;;用于基因表達(dá)譜數(shù)據(jù)聚類分析的貪心圖劃分算法研究[A];2006年全國(guó)理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2006年

4 劉華偉;全慶一;;能量有效的基于連通度的分布式簇劃分算法[A];2011年全國(guó)通信安全學(xué)術(shù)會(huì)議論文集[C];2011年

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

1 吳磊;復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法研究[D];太原理工大學(xué);2016年

2 馬靜;基于社交網(wǎng)絡(luò)的社團(tuán)劃分算法研究[D];山東師范大學(xué);2011年

3 韓明偉;超大規(guī)模集成電路劃分算法研究[D];西安電子科技大學(xué);2008年

4 許金鳳;大規(guī)模動(dòng)態(tài)自適應(yīng)圖劃分算法[D];寧波大學(xué);2015年

5 辛娟娟;社區(qū)劃分算法的研究與應(yīng)用[D];北京林業(yè)大學(xué);2015年

6 杜鵬飛;基于邊的相似性的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法研究[D];山東師范大學(xué);2014年

7 趙琴;并行計(jì)算中圖劃分算法的研究[D];華中師范大學(xué);2013年

8 戴曉罡;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)劃分算法研究[D];南京郵電大學(xué);2014年

9 林慧嫻;個(gè)性化服務(wù)中用戶建模及社區(qū)劃分算法研究[D];南京郵電大學(xué);2015年

10 王秀芹;軟硬件協(xié)同設(shè)計(jì)中的劃分算法研究[D];哈爾濱工程大學(xué);2005年

  本文關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法研究，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：308843