本文關(guān)鍵詞：基于點距離和聚類的社區(qū)發(fā)現(xiàn)算法研究

  更多相關(guān)文章： 社區(qū)發(fā)現(xiàn) 節(jié)點距離 密度峰值聚類 凝聚層次聚類

【摘要】：社會網(wǎng)絡(luò)是指由于個體之間發(fā)生交互而產(chǎn)生的一種關(guān)系網(wǎng)絡(luò)。隨著近些年互聯(lián)網(wǎng)的飛速發(fā)展,社會網(wǎng)絡(luò)的類型也越來越多樣,其中蘊含的有價值信息也越來越多,挖掘社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)也成為了近些年研究的熱門問題。由于社區(qū)發(fā)現(xiàn)能夠發(fā)現(xiàn)社會網(wǎng)絡(luò)中節(jié)點間的共性信息,使得其在蛋白質(zhì)功能分析、用戶行為分析、網(wǎng)絡(luò)異常檢測等諸多領(lǐng)域得到了廣泛的應(yīng)用。通常認為,社區(qū)是由一些相互聯(lián)系緊密的個體所構(gòu)成的集合,并且社區(qū)間的個體相對社區(qū)內(nèi)部的個體聯(lián)系稀疏。社會網(wǎng)絡(luò)通常被抽象為圖,其中節(jié)點代表個體,節(jié)點間的邊代表個體之間發(fā)生的交互關(guān)系。挖掘社會網(wǎng)路中的社區(qū)結(jié)構(gòu)可以被理解為根據(jù)節(jié)點之間的交互關(guān)系將圖劃分為多個子圖,各個子圖中的節(jié)點相似度高而子圖之間的節(jié)點相似度低,即將社會網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題看作一個圖中的聚類問題。針對聚類方法的特點,本文的主要工作難點如下:1.如何有效的度量網(wǎng)絡(luò)中節(jié)點間的距離。2.根據(jù)網(wǎng)絡(luò)中節(jié)點間的距離,利用何種聚類算法對節(jié)點進行聚類。針對以上兩個問題,文本通過以下方法解決:1.針對網(wǎng)絡(luò)中節(jié)點間距離的度量問題,本文分析了余弦距離和Jaccard距離的不足之處,并通過引入網(wǎng)絡(luò)中節(jié)點間最短路徑的距離,分別與余弦距離、Jaccard距離相結(jié)合,提出了改進的余弦距離和改進的Jaccard距離,從而更好的度量了網(wǎng)絡(luò)中節(jié)點間的距離。2.針對聚類算法的選擇問題,本文選取了兩個基于距離的聚類方法來對節(jié)點進行聚類,分別為密度峰值聚類方法和凝聚層次聚類方法。其中密度峰值聚類方法僅根據(jù)節(jié)點間的距離就能選取出聚類中心和聚類數(shù)目,無需參數(shù)選擇過程。凝聚層次聚類方法能夠根據(jù)節(jié)點的距離對節(jié)點不斷合并,發(fā)現(xiàn)網(wǎng)絡(luò)的層次結(jié)構(gòu)。綜上所述,本文所做的主要工作如下:1.本文提出了兩種基于改進的點距離和密度峰值聚類的社區(qū)發(fā)現(xiàn)方法—CSDPC和JSDPC。其中CSDPC和JSDPC分別采用改進的余弦距離和改進的Jaccard距離度量節(jié)點間的距離。CSDPC和JSDPC能夠根據(jù)節(jié)點間的距離選取網(wǎng)絡(luò)的關(guān)鍵節(jié)點并確定網(wǎng)絡(luò)中存在的社區(qū)數(shù)目,這與其他傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法相比存在很大的優(yōu)勢。2.本文提出了一種基于改進的點距離和凝聚層次聚類的社區(qū)發(fā)現(xiàn)方法—CSAHC。CSAHC采用改進的余弦距離度量節(jié)點間的距離,利用凝聚層次聚類方法不斷對節(jié)點進行合并,構(gòu)建網(wǎng)絡(luò)的社區(qū)層次結(jié)構(gòu),并根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的不同制定了相應(yīng)的社區(qū)結(jié)果選擇策略。3.在真實網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)數(shù)據(jù)集上的實驗證明了所提算法的可行性和有效性。
【關(guān)鍵詞】：社區(qū)發(fā)現(xiàn) 節(jié)點距離 密度峰值聚類 凝聚層次聚類
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP311.13
【目錄】：

• 摘要4-6
• Abstract6-11
• 第1章 緒論11-16
• 1.1 研究背景11-12
• 1.2 研究現(xiàn)狀12-14
• 1.3 本文工作14
• 1.4 本文組織結(jié)構(gòu)14-16
• 第2章 社區(qū)發(fā)現(xiàn)相關(guān)理論與技術(shù)16-22
• 2.1 社區(qū)的定義16
• 2.2 節(jié)點相似度及距離度量16-19
• 2.2.1 余弦相似度和余弦距離17-18
• 2.2.2 Jaccard相關(guān)系數(shù)和Jaccard距離18-19
• 2.3 社區(qū)發(fā)現(xiàn)的評價指標19-21
• 2.3.1 歸一化互信息19-20
• 2.3.2 模塊度20-21
• 2.4 本章小結(jié)21-22
• 第3章 基于點距離和密度峰值聚類的社區(qū)發(fā)現(xiàn)方法22-40
• 3.1 節(jié)點距離度量22-24
• 3.1.1 改進的余弦距離度量22-23
• 3.1.2 改進的Jaccard距離度量23-24
• 3.2 密度峰值聚類方法24-25
• 3.3 基于點距離和密度峰值聚類的社區(qū)發(fā)現(xiàn)方法25-27
• 3.3.1 基于改進的余弦距離和密度峰值聚類的社區(qū)發(fā)現(xiàn)方法—CSDPC . 1525-26
• 3.3.2 基于改進的Jaccard距離和密度峰值聚類的社區(qū)發(fā)現(xiàn)方法—JSDPC26-27
• 3.4 實驗與結(jié)果分析27-39
• 3.4.1 真實網(wǎng)絡(luò)數(shù)據(jù)集27-35
• 3.4.1.1 數(shù)據(jù)集描述28
• 3.4.1.2 實驗結(jié)果與分析28-35
• 3.4.2 人工網(wǎng)絡(luò)數(shù)據(jù)集35-39
• 3.4.2.1 數(shù)據(jù)集描述35
• 3.4.2.2 實驗結(jié)果與分析35-39
• 3.5 本章小結(jié)39-40
• 第4章 基于點距離和凝聚層次聚類的社區(qū)發(fā)現(xiàn)方法40-54
• 4.1 節(jié)點距離度量40
• 4.2 層次聚類方法40-42
• 4.3 基于點距離和凝聚層次聚類的社區(qū)發(fā)現(xiàn)方法—CSAHC42-43
• 4.4 實驗與結(jié)果分析43-53
• 4.4.1 真實網(wǎng)絡(luò)數(shù)據(jù)集43-49
• 4.4.2 人工網(wǎng)絡(luò)數(shù)據(jù)集49-53
• 4.4.2.1 社區(qū)數(shù)目可以確定49-51
• 4.4.2.2 社區(qū)數(shù)目無法確定51-53
• 4.5 本章小結(jié)53-54
• 第5章 總結(jié)54-55
• 參考文獻55-59
• 作者簡介及在學(xué)期間所取得的科研成果59-60
• 致謝60

【相似文獻】

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

1 孫敏;;測速量距很簡單[J];電腦迷;2012年11期

2 徐名祝;;SSRR—采用擴展頻譜體制的距離和距離變化率測量裝置[J];電訊技術(shù);1979年04期

3 孫梅玉;;基于距離和密度的時間序列異常檢測方法研究[J];計算機工程與應(yīng)用;2012年20期

4 ;第五節(jié) 距離和距離變化率性能要求[J];電訊技術(shù);1975年04期

5 ;[J];;年期

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

1 李玉;基于點距離和聚類的社區(qū)發(fā)現(xiàn)算法研究[D];吉林大學(xué);2016年

2 張孟;關(guān)于樹的離心距離和的一些探究[D];華中師范大學(xué);2013年

3 崔娜;關(guān)于樹的離心距離和的極值[D];中國礦業(yè)大學(xué);2015年

4 布威則熱古麗·伊斯坎代爾;乘積圖的離心連通指標和離心距離和[D];新疆大學(xué);2013年

，

本文編號：1083352