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

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

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

• 摘要4-6
• Abstract6-11
• 第1章 緒論11-17
• 1.1 研究背景與研究意義11-13
• 1.2 國內(nèi)外研究現(xiàn)狀13-15
• 1.3 本文主要工作15-16
• 1.4 本文組織架構(gòu)16-17
• 第2章 復雜網(wǎng)絡與社區(qū)發(fā)現(xiàn)17-29
• 2.1 復雜網(wǎng)絡17-20
• 2.1.1 網(wǎng)絡與表示17-18
• 2.1.2 復雜網(wǎng)絡的屬性18-20
• 2.2 社區(qū)發(fā)現(xiàn)的研究方法20-23
• 2.2.1 基于結(jié)點為中心的社區(qū)發(fā)現(xiàn)21
• 2.2.2 基于群組為中心的社區(qū)發(fā)現(xiàn)21-22
• 2.2.3 基于網(wǎng)絡為中心的社區(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)算法簡介29
• 3.2 基于社區(qū)相似的層次聚類社區(qū)發(fā)現(xiàn)算法（CSHC）29-34
• 3.2.1 相關問題探究29-33
• 3.2.2 CSHC 社區(qū)發(fā)現(xiàn)算法33-34
• 3.3 實驗評估標準34-35
• 3.3.1 純度34
• 3.3.2 模塊度34-35
• 3.4 實驗結(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 實驗總結(jié)41
• 3.6 本章小結(jié)41-42
• 第4章 基于重要結(jié)點的社區(qū)發(fā)現(xiàn)算法42-54
• 4.1 相關問題探究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é)點的社區(qū)發(fā)現(xiàn)算法（INC）45-46
• 4.3 實驗結(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 實驗總結(jié)52
• 4.5 本章小結(jié)52-54
• 第5章 基于社區(qū)的重要結(jié)點評定方法54-58
• 5.1 中心性簡介54-55
• 5.1.1 度中心54
• 5.1.2 緊密度中心54-55
• 5.2 基于社區(qū)的重要結(jié)點評估算法（ICC）55-56
• 5.3 實驗結(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
• 參考文獻60-63
• 作者簡介及在學期間所取得的科研成果63-64
• 致謝64

【共引文獻】

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

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

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

3 牟向偉;陳燕;楊明;李桃迎;;班輪航運網(wǎng)絡拓撲特性[J];大連海事大學學報;2009年02期

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

5 田煒;鄧貴仕;武佩劍;車文嬌;;世界航運網(wǎng)絡復雜性分析[J];大連理工大學學報;2007年04期

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

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

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

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

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

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

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

2 王小磊;張瑾;許洪波;;基于交互增強原理的多文檔自動文摘算法[A];第四屆全國學生計算語言學研討會會議論文集[C];2008年

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

4 林敏;張傳海;;基于數(shù)學手段的復雜系統(tǒng)仿真方法研究概述[A];系統(tǒng)仿真技術及其應用學術論文集（第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屆中國控制與決策會議論文集[C];2014年

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

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

1 徐森;文本聚類集成關鍵技術研究[D];哈爾濱工程大學;2010年

2 宋軍;水交換模型的理論方法及應用研究[D];中國海洋大學;2010年

3 胡進;復雜網(wǎng)絡上的博弈及其在通信網(wǎng)絡資源管理中的應用[D];華中科技大學;2010年

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

5 楊樹忠;復雜網(wǎng)絡中的社團檢測問題研究[D];北京交通大學;2009年

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

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

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

9 呂紹高;統(tǒng)計學習中回歸與正則化譜聚類算法的研究[D];中國科學技術大學;2011年

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

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

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

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

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

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

5 王學勇;復雜網(wǎng)絡演化與軟件平臺研究[D];西安電子科技大學;2011年

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

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

8 雷玲;離散正則化方法在草場檢測上的研究與應用[D];吉林大學;2011年

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

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

本文編號：867188