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

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

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

2、ectionAlgorithmsBasedonVertexDistanceandClusteringMethods作者姓名：李玉領(lǐng)域（方向）：計(jì)算機(jī)技術(shù)指導(dǎo)教師：黃嵐教授類(lèi)別：工程碩士答辯日期：2016年5月25日未經(jīng)本論女作者的書(shū)面授權(quán)，化法收存和保管本論文書(shū)面版本、電子版本的任何單位和個(gè)人，均不得對(duì)本論文的全部或部分內(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)下，獨(dú)立進(jìn)行研巧工作所取

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

4、網(wǎng)絡(luò)異常檢測(cè)等諸多領(lǐng)域得到了廣泛的應(yīng)用。通常認(rèn)為，社區(qū)是由一些相互聯(lián)系緊密的個(gè)體所構(gòu)成的集合，并且社區(qū)間的個(gè)體相對(duì)社區(qū)內(nèi)部的個(gè)體聯(lián)系稀疏。社會(huì)網(wǎng)絡(luò)通常被抽象為圖，其中節(jié)點(diǎn)代表個(gè)體，節(jié)點(diǎn)間的邊代表個(gè)體之間發(fā)生的交互關(guān)系。挖掘社會(huì)網(wǎng)路中的社區(qū)結(jié)構(gòu)可以被理解為根據(jù)節(jié)點(diǎn)之間的交互關(guān)系將圖劃分為多個(gè)子圖，各個(gè)子圖中的節(jié)點(diǎn)相似度高而子圖之間的節(jié)點(diǎn)相似度低，即將社會(huì)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問(wèn)題看作一個(gè)圖中的聚類(lèi)問(wèn)題。針對(duì)聚類(lèi)方法的特點(diǎn)，本文的主要工作難點(diǎn)如下：1.如何有效的度量網(wǎng)絡(luò)中節(jié)點(diǎn)間的距離。2.根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)間的距離，利用何種聚類(lèi)算法對(duì)節(jié)點(diǎn)進(jìn)行聚類(lèi)。針對(duì)以上兩個(gè)問(wèn)題，文本通過(guò)以下方法解決：1.針對(duì)

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

6、密度峰值聚類(lèi)的社區(qū)發(fā)現(xiàn)方法—CSDPC和I摘要JSDPC。其中CSDPC和JSDPC分別采用改進(jìn)的余弦距離和改進(jìn)的Jaccard距離度量節(jié)點(diǎn)間的距離。CSDPC和JSDPC能夠根據(jù)節(jié)點(diǎn)間的距離選取網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)并確定網(wǎng)絡(luò)中存在的社區(qū)數(shù)目，這與其他傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法相比存在很大的優(yōu)勢(shì)。2.本文提出了一種基于改進(jìn)的點(diǎn)距離和凝聚層次聚類(lèi)的社區(qū)發(fā)現(xiàn)方法—CSAHC。CSAHC采用改進(jìn)的余弦距離度量節(jié)點(diǎn)間的距離，利用凝聚層次聚類(lèi)方法不斷對(duì)節(jié)點(diǎn)進(jìn)行合并，構(gòu)建網(wǎng)絡(luò)的社區(qū)層次結(jié)構(gòu)，并根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的不同制定了相應(yīng)的社區(qū)結(jié)果選擇策略。3.在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)證明了所提算法的可行

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