本文關(guān)鍵詞：基于模糊聚類的社團(tuán)劃分算法研究

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 社團(tuán)劃分 隸屬函數(shù) 模糊等價(jià)關(guān)系 等價(jià)類

【摘要】：社團(tuán)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)的重要特性之一,對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分,則可以通過對(duì)幾個(gè)小社團(tuán)的研究,以“分而治之”的方式對(duì)整個(gè)系統(tǒng)的模塊、功能及演化進(jìn)行研究,大大降低了直接對(duì)龐大的復(fù)雜系統(tǒng)進(jìn)行研究的復(fù)雜性,還進(jìn)一步加深了對(duì)復(fù)雜系統(tǒng)的組織原則、拓?fù)浣Y(jié)構(gòu)與動(dòng)力學(xué)特性的理解。目前已有的復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法中,大部分的算法主要是非重疊社團(tuán)劃分算法,劃分結(jié)果顯示為網(wǎng)絡(luò)被劃分為若干個(gè)互相獨(dú)立的社團(tuán),社團(tuán)與社團(tuán)之間沒有重疊節(jié)點(diǎn)。但是在某些實(shí)際網(wǎng)絡(luò)中,網(wǎng)絡(luò)中存在具有多個(gè)社團(tuán)屬性的節(jié)點(diǎn)即重疊節(jié)點(diǎn),社團(tuán)之間是存在一定關(guān)聯(lián)的,我們可以根據(jù)重疊節(jié)點(diǎn)進(jìn)而推斷社團(tuán)之間的關(guān)聯(lián)程度,對(duì)于動(dòng)態(tài)的網(wǎng)絡(luò),根據(jù)重疊節(jié)點(diǎn)還能對(duì)社區(qū)的下一步變化進(jìn)行預(yù)測(cè),因此,重疊節(jié)點(diǎn)的發(fā)現(xiàn)有特殊的意義和研究?jī)r(jià)值。本文在對(duì)已有的經(jīng)典社團(tuán)劃分算法的研究基礎(chǔ)上,提出了一種基于模糊聚類的社團(tuán)劃分算法,可以同時(shí)應(yīng)用于非重疊社團(tuán)和重疊社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)的社團(tuán)劃分�；谀：垲惖纳鐖F(tuán)劃分算法是一種啟發(fā)式算法,它的啟發(fā)式規(guī)則:將節(jié)點(diǎn)作為模糊聚類算法中用于聚類的樣本,應(yīng)用模糊聚類算法后,屬于同一等價(jià)類的樣本對(duì)應(yīng)的節(jié)點(diǎn)應(yīng)屬于相同的社團(tuán)。在傳統(tǒng)的模糊聚類算法中,隸屬函數(shù)的值反映的是樣本之間的模糊關(guān)系~R的程度即樣本間的相似程度。將傳統(tǒng)的模糊聚類算法應(yīng)用到社團(tuán)劃分中,將節(jié)點(diǎn)作為聚類樣本,本文算法的具體工作如下:1、對(duì)傳統(tǒng)的共享鄰居數(shù)的定義進(jìn)行了改進(jìn),通過改進(jìn)后的共享鄰居數(shù)定義表示節(jié)點(diǎn)間的相似程度并提出了一種基于節(jié)點(diǎn)間共享鄰居數(shù)的隸屬函數(shù)。2、對(duì)于網(wǎng)絡(luò)中存在重疊節(jié)點(diǎn)的情況,模糊聚類算法所得的劃分結(jié)果中,針對(duì)少數(shù)不屬于任何等價(jià)類的節(jié)點(diǎn)即重疊節(jié)點(diǎn)候選解,提出了重疊節(jié)點(diǎn)的判別準(zhǔn)則,檢測(cè)出候選解中的重疊節(jié)點(diǎn)。本文提出的算法的時(shí)間復(fù)雜度為22(log)nO n。在GN經(jīng)典人造網(wǎng)和幾個(gè)實(shí)際網(wǎng)絡(luò)上進(jìn)行測(cè)試,對(duì)社團(tuán)大小規(guī)模已知且不存在重疊社團(tuán)的GN經(jīng)典人造網(wǎng)的劃分結(jié)果符合真實(shí)情況,算法在實(shí)際網(wǎng)絡(luò)的驗(yàn)證上,通過與其它算法的劃分結(jié)果進(jìn)行比較,得到的模塊度Q值較高,并且能夠更好的檢測(cè)出實(shí)際網(wǎng)絡(luò)中的重疊節(jié)點(diǎn)。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 社團(tuán)劃分 隸屬函數(shù) 模糊等價(jià)關(guān)系 等價(jià)類
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5;O159
【目錄】：

• 摘要4-6
• ABSTRACT6-11
• 第一章 緒論11-21
• 1.1 研究背景和研究意義11-14
• 1.2 國(guó)內(nèi)外的研究現(xiàn)狀14-19
• 1.3 本文的主要工作19
• 1.4 論文組織結(jié)構(gòu)19-21
• 第二章 相關(guān)工作基礎(chǔ)21-31
• 2.1 相關(guān)定義及概念21-27
• 2.1.1 復(fù)雜網(wǎng)絡(luò)的表示方法21-24
• 2.1.2 聚類系數(shù)24-25
• 2.1.3 社團(tuán)的定義25-27
• 2.2 社團(tuán)劃分結(jié)果評(píng)價(jià)指標(biāo)27-30
• 2.2.1 模塊度27-29
• 2.2.2 標(biāo)準(zhǔn)化互信息29-30
• 2.3 本章小結(jié)30-31
• 第三章 經(jīng)典的社團(tuán)劃分算法31-45
• 3.1 非重疊社團(tuán)劃分算法31-41
• 3.1.1 Kernighan-Lin算法31-33
• 3.1.2 譜平分算法33-36
• 3.1.3 GN算法及其改進(jìn)算法36-40
• 3.1.4 Newman快速算法40-41
• 3.2 重疊社團(tuán)的劃分算法41-43
• 3.3 本章小結(jié)43-45
• 第四章 基于模糊聚類的社團(tuán)劃分算法45-59
• 4.1 模糊聚類算法的相關(guān)基礎(chǔ)45-47
• 4.1.1 模糊聚類算法的相關(guān)理論基礎(chǔ)45-46
• 4.1.2 模糊聚類算法介紹46-47
• 4.2 基于節(jié)點(diǎn)間共享鄰居數(shù)的隸屬函數(shù)47-49
• 4.2.1 相關(guān)定義及其物理意義47-49
• 4.2.2 相關(guān)數(shù)學(xué)證明49
• 4.3 重疊節(jié)點(diǎn)的判別準(zhǔn)則49-52
• 4.4 算法的主要工作52-53
• 4.5 算法的具體實(shí)現(xiàn)步驟53-56
• 4.6 算法的時(shí)間復(fù)雜度分析56-57
• 4.7 本章小結(jié)57-59
• 第五章 實(shí)驗(yàn)與分析59-69
• 5.1 實(shí)驗(yàn)數(shù)據(jù)集59-61
• 5.1.1 人工網(wǎng)絡(luò)數(shù)據(jù)集59-60
• 5.1.2 實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集60-61
• 5.2 實(shí)驗(yàn)分析61-67
• 5.2.1 評(píng)價(jià)指標(biāo)的采用依據(jù)61-62
• 5.2.2 算法的實(shí)驗(yàn)結(jié)果比較分析62-67
• 5.3 本章小結(jié)67-69
• 第六章 總結(jié)與展望69-71
• 6.1 總結(jié)69-70
• 6.2 展望70-71
• 參考文獻(xiàn)71-75
• 致謝75-77
• 攻讀碩士學(xué)位期間發(fā)表的學(xué)術(shù)論文77

【相似文獻(xiàn)】

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

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

2 許金鳳;董一鴻;王詩懿;何賢芒;陳華輝;;大規(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ù)庫 前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ù)庫 前10條

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

2 周爽;面向BSP模型的圖數(shù)據(jù)劃分算法的設(shè)計(jì)與實(shí)現(xiàn)[D];東北大學(xué);2013年

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

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

5 宋俐;基于模糊聚類的社團(tuán)劃分算法研究[D];太原理工大學(xué);2016年

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

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

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

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

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

，

本文編號(hào)：1006884