基于點距離和聚類的社區(qū)發(fā)現(xiàn)算法研究

《基于點距離和聚類的社區(qū)發(fā)現(xiàn)算法研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、分類號：TP39單位代碼：10183研究生學(xué)號：2013534016密級：公開研吉林大學(xué)碩士學(xué)位論文（專業(yè)學(xué)位）基于點距離和聚類的社區(qū)發(fā)現(xiàn)算法研究ResearchonCommunityDetectionAlgorithmsBasedonVertexDistanceandClusteringMethods作者姓名：李玉類別：工程碩士領(lǐng)域（方向）：計算機(jī)技術(shù)指導(dǎo)教師：黃嵐教授培養(yǎng)單位：計算機(jī)科學(xué)與技術(shù)學(xué)院2016年4月———————————————————————基于點距離和聚類的社區(qū)發(fā)現(xiàn)算法研究———————————————————————ResearchonCommunityDet

2、ectionAlgorithmsBasedonVertexDistanceandClusteringMethods作者姓名：李玉領(lǐng)域（方向）：計算機(jī)技術(shù)指導(dǎo)教師：黃嵐教授類別：工程碩士答辯日期：2016年5月25日未經(jīng)本論女作者的書面授權(quán)，化法收存和保管本論文書面版本、電子版本的任何單位和個人，均不得對本論文的全部或部分內(nèi)容進(jìn)行任何形式的復(fù)制、修改、發(fā)行、出租、改編等有礙作者著作權(quán)的商業(yè)性使用（但純學(xué)術(shù)性使用不在此限）。否則，應(yīng)承擔(dān)侵權(quán)的法律責(zé)任。吉林大學(xué)碩：ｔ學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交學(xué)位論文，是本人在指導(dǎo)教師的指導(dǎo)下，獨立進(jìn)行研巧工作所取

3、得的成果。除文中己經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個人或集體己經(jīng)發(fā)表或撰寫過的作品成果。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中明確方式標(biāo)明。本人完全意識到本聲明的法律結(jié)果由本人承擔(dān)。學(xué)位論文作者簽名：日期：２０化年夕月乂日摘要摘要基于點距離和聚類的社區(qū)發(fā)現(xiàn)算法研究社會網(wǎng)絡(luò)是指由于個體之間發(fā)生交互而產(chǎn)生的一種關(guān)系網(wǎng)絡(luò)。隨著近些年互聯(lián)網(wǎng)的飛速發(fā)展，社會網(wǎng)絡(luò)的類型也越來越多樣，其中蘊(yùn)含的有價值信息也越來越多，挖掘社會網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)也成為了近些年研究的熱門問題。由于社區(qū)發(fā)現(xiàn)能夠發(fā)現(xiàn)社會網(wǎng)絡(luò)中節(jié)點間的共性信息，使得其在蛋白質(zhì)功能分析、用戶行為分析、

4、網(wǎng)絡(luò)異常檢測等諸多領(lǐng)域得到了廣泛的應(yīng)用。通常認(rèn)為，社區(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é)點進(jìn)行聚類。針對以上兩個問題，文本通過以下方法解決：1.針對

5、網(wǎng)絡(luò)中節(jié)點間距離的度量問題，本文分析了余弦距離和Jaccard距離的不足之處，并通過引入網(wǎng)絡(luò)中節(jié)點間最短路徑的距離，分別與余弦距離、Jaccard距離相結(jié)合，提出了改進(jìn)的余弦距離和改進(jìn)的Jaccard距離，從而更好的度量了網(wǎng)絡(luò)中節(jié)點間的距離。2.針對聚類算法的選擇問題，本文選取了兩個基于距離的聚類方法來對節(jié)點進(jìn)行聚類，分別為密度峰值聚類方法和凝聚層次聚類方法。其中密度峰值聚類方法僅根據(jù)節(jié)點間的距離就能選取出聚類中心和聚類數(shù)目，無需參數(shù)選擇過程。凝聚層次聚類方法能夠根據(jù)節(jié)點的距離對節(jié)點不斷合并，發(fā)現(xiàn)網(wǎng)絡(luò)的層次結(jié)構(gòu)。綜上所述，本文所做的主要工作如下：1.本文提出了兩種基于改進(jìn)的點距離和

6、密度峰值聚類的社區(qū)發(fā)現(xiàn)方法—CSDPC和I摘要JSDPC。其中CSDPC和JSDPC分別采用改進(jìn)的余弦距離和改進(jìn)的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.本文提出了一種基于改進(jìn)的點距離和凝聚層次聚類的社區(qū)發(fā)現(xiàn)方法—CSAHC。CSAHC采用改進(jìn)的余弦距離度量節(jié)點間的距離，利用凝聚層次聚類方法不斷對節(jié)點進(jìn)行合并，構(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ù)集上的實驗證明了所提算法的可行

7、性和有效性。關(guān)鍵詞：社區(qū)發(fā)現(xiàn)，節(jié)點距離，密度峰值聚類，凝聚層次聚類IIAbstractAbstractResearchonCommunityDetectionAlgorithmsBasedonVertexDistanceandClusteringMethodsSocialnetworksareinteractivenetworkofrelationshipsbetweenindividuals.WiththerapiddevelopmentofInternetinre