本文關(guān)鍵詞：面向復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 社區(qū)相似 層次聚類 k-means算法 社區(qū)發(fā)現(xiàn) 重要結(jié)點(diǎn)評(píng)估

【摘要】：網(wǎng)絡(luò)是一種呈現(xiàn)復(fù)雜系統(tǒng)的有效方法。復(fù)雜網(wǎng)絡(luò)（complex network）描述了一系列的自然和社會(huì)系統(tǒng)，例如信息系統(tǒng)、生物系統(tǒng)、社會(huì)系統(tǒng)、交通系統(tǒng)、航空網(wǎng)絡(luò)、電力系統(tǒng)以及一些合作性質(zhì)的網(wǎng)絡(luò)系統(tǒng)等。自然界中大量真的網(wǎng)絡(luò)都具有其獨(dú)特的結(jié)構(gòu)特點(diǎn)，系統(tǒng)內(nèi)部個(gè)元組之間的聯(lián)系以及相互作用，可以抽象為具有一定組織關(guān)系的小型網(wǎng)絡(luò)，這種小型網(wǎng)絡(luò)承擔(dān)著系統(tǒng)的功能，并且能夠具體的體現(xiàn)網(wǎng)絡(luò)中的組織關(guān)系特點(diǎn)。這些小型網(wǎng)絡(luò)就定義為復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)（community）。 復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的研究可以揭示復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)和一些網(wǎng)絡(luò)現(xiàn)象的成因。將復(fù)雜網(wǎng)絡(luò)中的個(gè)體劃分為不同的社區(qū)結(jié)構(gòu)進(jìn)行研究，可以有針對(duì)性的對(duì)復(fù)雜網(wǎng)絡(luò)的某些特征進(jìn)行研究，也可以減少對(duì)復(fù)雜網(wǎng)絡(luò)某些特征研究的工作量。因此，復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法的研究具有巨大的社會(huì)、經(jīng)濟(jì)和科研價(jià)值。 本文針對(duì)復(fù)雜網(wǎng)絡(luò)，，首先，基于Louvain社區(qū)發(fā)現(xiàn)算法的啟發(fā)，提出了基于社區(qū)相似的層次聚類社區(qū)發(fā)現(xiàn)算法（CSHC）。算法初始階段將每一個(gè)結(jié)點(diǎn)作為一個(gè)社區(qū)，然后提出社區(qū)之間的相似性和模塊度最大增益之間的一個(gè)合并系數(shù)，決定社區(qū)是否合并，迭代算法的停止條件為達(dá)到需要?jiǎng)澐值纳鐓^(qū)個(gè)數(shù)k為止。CSHC算法分別在Karate ClubNetwork數(shù)據(jù)集和American College Football數(shù)據(jù)集上得到了很好的社區(qū)劃分，其純度與模塊度對(duì)以往的社區(qū)發(fā)現(xiàn)算法都有一定的提高。并且CSHC算法可以在很少次的合并達(dá)到社區(qū)劃分結(jié)果，與以往社區(qū)發(fā)現(xiàn)算法相比其效率大大增加。其次，本文提出了基于重要結(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法（INC），首先依據(jù)模塊度最大化理論，計(jì)算出網(wǎng)絡(luò)的模塊度矩陣B的最大k特征向量矩陣S。然后，提出聚類中心方法用于求出k個(gè)社團(tuán)的重要結(jié)點(diǎn)作為k聚類中心。利用歐幾里得距離計(jì)算每一個(gè)結(jié)點(diǎn)到k個(gè)聚類中心的距離，將結(jié)點(diǎn)分配到距離聚類中心最近的社區(qū)中。最后，對(duì)網(wǎng)絡(luò)應(yīng)用k-means方法進(jìn)行迭代計(jì)算，最終得到k個(gè)社區(qū)的劃分。INC算法分別在Karate Club Network數(shù)據(jù)集和American CollegeFootball數(shù)據(jù)集上得到了很好的社區(qū)劃分，并且可以有效的發(fā)現(xiàn)潛在社區(qū)，其純度與模塊度對(duì)以往的社區(qū)發(fā)現(xiàn)算法都有一定的提高。并且INC算法可以在很少次的迭代達(dá)到社區(qū)劃分結(jié)果，與以往社區(qū)發(fā)現(xiàn)算法相比其效率有很大提高。 復(fù)雜網(wǎng)絡(luò)內(nèi)部的各個(gè)社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征的具體承擔(dān)者和復(fù)雜網(wǎng)絡(luò)屬性特征的具體體現(xiàn)者。另外，在系統(tǒng)內(nèi)部，并不是所有的元組個(gè)體對(duì)復(fù)雜網(wǎng)絡(luò)的特征和結(jié)構(gòu)都起到一樣的作用，一些元組會(huì)扮演更為重要角色，這種元組被稱為網(wǎng)絡(luò)中的關(guān)鍵結(jié)點(diǎn)。因此，本文提出了基于社區(qū)的重要結(jié)點(diǎn)評(píng)定方法，既充分的考慮到一個(gè)結(jié)點(diǎn)與其他所有結(jié)點(diǎn)之間的緊密程度，又充分考慮到結(jié)點(diǎn)在社區(qū)中的貢獻(xiàn)，提出ICC算法對(duì)網(wǎng)絡(luò)中結(jié)點(diǎn)進(jìn)行重要性的評(píng)定。ICC算法分別在Karate Club Network數(shù)據(jù)集和AmericanCollege Football數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，并與經(jīng)典的中心性計(jì)算方法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，ICC算法很好的將社區(qū)中重要結(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的實(shí)際意義凸現(xiàn)出來(lái)，對(duì)網(wǎng)絡(luò)中重要結(jié)點(diǎn)的評(píng)價(jià)有了新的視角，并且對(duì)網(wǎng)絡(luò)的實(shí)際意義做出很好的評(píng)判。 現(xiàn)代科學(xué)的網(wǎng)絡(luò)為復(fù)雜網(wǎng)絡(luò)的理解帶來(lái)了重大的發(fā)展。復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)與社區(qū)發(fā)現(xiàn)算法的研究對(duì)關(guān)鍵問(wèn)題的討論、集群的意義以及對(duì)真實(shí)網(wǎng)絡(luò)的描述具有重要的意義。由于復(fù)雜網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)的重要程度不同，對(duì)復(fù)雜網(wǎng)絡(luò)中的屬性貢獻(xiàn)就不同。因此，挖掘復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵結(jié)點(diǎn)，具有巨大的實(shí)用價(jià)值。
【關(guān)鍵詞】：復(fù)雜網(wǎng)絡(luò) 社區(qū)相似 層次聚類 k-means算法 社區(qū)發(fā)現(xiàn) 重要結(jié)點(diǎn)評(píng)估
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-6
• Abstract6-11
• 第1章 緒論11-17
• 1.1 研究背景與研究意義11-13
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀13-15
• 1.3 本文主要工作15-16
• 1.4 本文組織架構(gòu)16-17
• 第2章 復(fù)雜網(wǎng)絡(luò)與社區(qū)發(fā)現(xiàn)17-29
• 2.1 復(fù)雜網(wǎng)絡(luò)17-20
• 2.1.1 網(wǎng)絡(luò)與表示17-18
• 2.1.2 復(fù)雜網(wǎng)絡(luò)的屬性18-20
• 2.2 社區(qū)發(fā)現(xiàn)的研究方法20-23
• 2.2.1 基于結(jié)點(diǎn)為中心的社區(qū)發(fā)現(xiàn)21
• 2.2.2 基于群組為中心的社區(qū)發(fā)現(xiàn)21-22
• 2.2.3 基于網(wǎng)絡(luò)為中心的社區(qū)發(fā)現(xiàn)22
• 2.2.4 基于層次為中心的社區(qū)發(fā)現(xiàn)22-23
• 2.3 社區(qū)發(fā)現(xiàn)經(jīng)典算法23-28
• 2.3.1 譜聚類23-26
• 2.3.2 潛在空間模型26-28
• 2.4 本章小結(jié)28-29
• 第3章 基于社區(qū)相似的層次聚類社區(qū)發(fā)現(xiàn)算法29-42
• 3.1 Louvain 社區(qū)發(fā)現(xiàn)算法簡(jiǎn)介29
• 3.2 基于社區(qū)相似的層次聚類社區(qū)發(fā)現(xiàn)算法（CSHC）29-34
• 3.2.1 相關(guān)問(wèn)題探究29-33
• 3.2.2 CSHC 社區(qū)發(fā)現(xiàn)算法33-34
• 3.3 實(shí)驗(yàn)評(píng)估標(biāo)準(zhǔn)34-35
• 3.3.1 純度34
• 3.3.2 模塊度34-35
• 3.4 實(shí)驗(yàn)結(jié)果及分析35-41
• 3.4.1 Karate Club Network 數(shù)據(jù)集35-37
• 3.4.2 American College Football 數(shù)據(jù)集37-41
• 3.5 實(shí)驗(yàn)總結(jié)41
• 3.6 本章小結(jié)41-42
• 第4章 基于重要結(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法42-54
• 4.1 相關(guān)問(wèn)題探究42-45
• 4.1.1 模塊度最大化42-43
• 4.1.2 K-means 方法介紹43-44
• 4.1.3 歐幾里得度量44
• 4.1.4 聚類中心44-45
• 4.2 基于重要結(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法（INC）45-46
• 4.3 實(shí)驗(yàn)結(jié)果及分析46-52
• 4.3.1 Karate Club Network 數(shù)據(jù)集47-48
• 4.3.2 American College Football 數(shù)據(jù)集48-52
• 4.4 實(shí)驗(yàn)總結(jié)52
• 4.5 本章小結(jié)52-54
• 第5章 基于社區(qū)的重要結(jié)點(diǎn)評(píng)定方法54-58
• 5.1 中心性簡(jiǎn)介54-55
• 5.1.1 度中心54
• 5.1.2 緊密度中心54-55
• 5.2 基于社區(qū)的重要結(jié)點(diǎn)評(píng)估算法（ICC）55-56
• 5.3 實(shí)驗(yàn)結(jié)果及分析56-57
• 5.3.1 Karate Club Network 數(shù)據(jù)集56-57
• 5.3.2 American College Football 數(shù)據(jù)集57
• 5.4 本章小結(jié)57-58
• 第6章 總結(jié)與展望58-60
• 6.1 總結(jié)58
• 6.2 展望58-60
• 參考文獻(xiàn)60-63
• 作者簡(jiǎn)介及在學(xué)期間所取得的科研成果63-64
• 致謝64

【共引文獻(xiàn)】

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

1 秦洋;王立宏;武栓虎;宋宜斌;;基于拉普拉斯矩陣的DNA序列集相似性分析[J];北京交通大學(xué)學(xué)報(bào);2009年06期

2 楊華;聶玉超;張洪斌;樊瑛;;基于復(fù)雜網(wǎng)絡(luò)的快遞網(wǎng)絡(luò)性質(zhì)分析[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年01期

3 牟向偉;陳燕;楊明;李桃迎;;班輪航運(yùn)網(wǎng)絡(luò)拓?fù)涮匦訹J];大連海事大學(xué)學(xué)報(bào);2009年02期

4 莫輝輝;王姣娥;金鳳君;;交通運(yùn)輸網(wǎng)絡(luò)的復(fù)雜性研究[J];地理科學(xué)進(jìn)展;2008年06期

5 田煒;鄧貴仕;武佩劍;車文嬌;;世界航運(yùn)網(wǎng)絡(luò)復(fù)雜性分析[J];大連理工大學(xué)學(xué)報(bào);2007年04期

6 王建偉;榮莉莉;郭天柱;;一種基于局部特征的網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法[J];大連理工大學(xué)學(xué)報(bào);2010年05期

7 王姣娥;莫輝輝;金鳳君;;中國(guó)航空網(wǎng)絡(luò)空間結(jié)構(gòu)的復(fù)雜性[J];地理學(xué)報(bào);2009年08期

8 武文杰;董正斌;張文忠;金鳳君;馬修軍;謝昆青;;中國(guó)城市空間關(guān)聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)的時(shí)空演變[J];地理學(xué)報(bào);2011年04期

9 王茂軍;田麗英;楊雪春;;山東省城鎮(zhèn)網(wǎng)絡(luò)結(jié)構(gòu)與城鎮(zhèn)網(wǎng)絡(luò)角色識(shí)別——基于民國(guó)時(shí)期土貨/洋貨流通網(wǎng)絡(luò)的分析[J];地理研究;2011年09期

10 徐天順;;譜聚類算法研究[J];電腦知識(shí)與技術(shù);2012年16期

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

1 ;Pinning Complex Dynamical Networks with Local Betweeness Centrality Information[A];中國(guó)自動(dòng)化學(xué)會(huì)控制理論專業(yè)委員會(huì)C卷[C];2011年

2 王小磊;張瑾;許洪波;;基于交互增強(qiáng)原理的多文檔自動(dòng)文摘算法[A];第四屆全國(guó)學(xué)生計(jì)算語(yǔ)言學(xué)研討會(huì)會(huì)議論文集[C];2008年

3 于連飛;呂國(guó)棟;修保新;張維明;范�？�;;基于復(fù)雜網(wǎng)絡(luò)的C2組織描述與建模綜述[A];2014第二屆中國(guó)指揮控制大會(huì)論文集（上）[C];2014年

4 林敏;張傳海;;基于數(shù)學(xué)手段的復(fù)雜系統(tǒng)仿真方法研究概述[A];系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)論文集（第15卷）[C];2014年

5 Shengfu Zhou;Kun Yue;Qiyu Fang;Yunlei Zhu;Weiyi Liu;;An Efficient Algorithm for Influence Maximization under Linear Threshold Model[A];第26屆中國(guó)控制與決策會(huì)議論文集[C];2014年

6 畢娟;秦志光;黃嘉;;Dynamic Topic Model for Detecting Community in Social Networks[A];第十一屆全國(guó)博士生學(xué)術(shù)年會(huì)——信息技術(shù)與安全專題論文集[C];2013年

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

1 徐森;文本聚類集成關(guān)鍵技術(shù)研究[D];哈爾濱工程大學(xué);2010年

2 宋軍;水交換模型的理論方法及應(yīng)用研究[D];中國(guó)海洋大學(xué);2010年

3 胡進(jìn);復(fù)雜網(wǎng)絡(luò)上的博弈及其在通信網(wǎng)絡(luò)資源管理中的應(yīng)用[D];華中科技大學(xué);2010年

4 杜文博;面向航空交通系統(tǒng)的復(fù)雜網(wǎng)絡(luò)與網(wǎng)絡(luò)動(dòng)力學(xué)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

5 楊樹(shù)忠;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測(cè)問(wèn)題研究[D];北京交通大學(xué);2009年

6 陳偉;基于時(shí)序文本挖掘的新聞內(nèi)容理解與推薦技術(shù)研究[D];浙江大學(xué);2010年

7 錢(qián)鵬江;大規(guī)模數(shù)據(jù)集聚類方法研究及應(yīng)用[D];江南大學(xué);2011年

8 王偉;鐵路網(wǎng)抗毀性分析與研究[D];北京交通大學(xué);2011年

9 呂紹高;統(tǒng)計(jì)學(xué)習(xí)中回歸與正則化譜聚類算法的研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2011年

10 朱天;社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)角色以及群體演化研究[D];北京郵電大學(xué);2011年

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

1 李靜偉;基于共享近鄰的自適應(yīng)譜聚類算法[D];大連理工大學(xué);2010年

2 孫玉俠;數(shù)據(jù)挖掘中的譜聚類算法研究[D];中國(guó)海洋大學(xué);2010年

3 溫程;并行聚類算法在MapReduce上的實(shí)現(xiàn)[D];浙江大學(xué);2011年

4 毛菥;基于文本分析技術(shù)的新聞閱讀平臺(tái)的研究與實(shí)現(xiàn)[D];浙江大學(xué);2011年

5 王學(xué)勇;復(fù)雜網(wǎng)絡(luò)演化與軟件平臺(tái)研究[D];西安電子科技大學(xué);2011年

6 張漢珍;譜劃分算法中特征向量選取方法的研究[D];西安電子科技大學(xué);2010年

7 王蓓金;蛋白質(zhì)網(wǎng)絡(luò)模塊分解的密度聚類算法研究[D];西安電子科技大學(xué);2010年

8 雷玲;離散正則化方法在草場(chǎng)檢測(cè)上的研究與應(yīng)用[D];吉林大學(xué);2011年

9 錢(qián)新宇;基于實(shí)例推理的虛擬裝配序列規(guī)劃研究[D];大連海事大學(xué);2011年

10 黃旭;群智能優(yōu)化算法及其在PPI網(wǎng)絡(luò)中的應(yīng)用研究[D];陜西師范大學(xué);2011年

本文編號(hào)：867188