基于相似度的復雜網(wǎng)絡社團結構檢測算法研究

1、大連理工大學碩士學位論文I碩士學位論文基于相似度的復雜網(wǎng)絡社團結構檢測算法研究基于相似度的復雜網(wǎng)絡社團結構檢測算法研究Researchondetectingalgithmsfcommunitystructuresincomplexwksbasedonintimacy作者姓名：秦小蒙學科、專業(yè)：計算機應用技術學號：21409179指導教師：王興元完成日期：2017年05月大連理工大學DalianUniversityofTechnology

2、大連理工大學碩士學位論文III摘要社團結構指的是復雜網(wǎng)絡內(nèi)部聚合的情況。復雜網(wǎng)絡的聚類情況對研究復雜網(wǎng)絡的網(wǎng)絡行為、拓撲結構和信息傳播與挖掘都有十分重要的意義。所以，近幾年，越來越多的學者投身到復雜網(wǎng)絡的社團結構檢測中，同時，大量的算法也被提出。而不同的網(wǎng)絡，由于其網(wǎng)絡特性的差異，其社團結構的檢測方法也存在不同，且存在一定的問題。如在重疊社團檢測上重疊界限要求過于嚴格，而對于有向加權網(wǎng)絡和二分網(wǎng)絡的社團檢測，研究過程中則可能存在信息丟失

3、等問題，需進一步的探究。為此，本文針對不同的網(wǎng)絡提出了三種不同的基于相似度的社團結構檢測算法，主要工作和創(chuàng)新點如下：(1)提出了一個基于關鍵節(jié)點的重疊社團劃分算法。算法通過對復雜網(wǎng)絡的節(jié)點進行預處理，篩選出其中的關鍵節(jié)點，并形成以關鍵節(jié)點為中心的核心區(qū)域，隨后吸收與該核心區(qū)域關系緊密的節(jié)點以形成初始社團，再根據(jù)吸收度擴大社團。算法利用了一種初始網(wǎng)絡篩選方法和最新的吸收度函數(shù)對重疊社團進行檢測。實驗結果表明了該算法能有效地檢測出網(wǎng)絡的社團

4、結構，且算法時間復雜度相對較低。(2)提出了一種基于非對稱親密度的有向加權網(wǎng)絡的社團檢測算法。通過對有向加權網(wǎng)絡節(jié)點間的關系特點的研究，給出了一種既能體現(xiàn)節(jié)點對間直接關系又能體現(xiàn)其間接關系的親密度參數(shù)，并將其設計和引申至社團間的親密關系。利用節(jié)點間的關系對網(wǎng)絡進行聚類分析，最終根據(jù)最優(yōu)模塊度選擇出最終的劃分結果。通過對比試驗發(fā)現(xiàn)了該算法的優(yōu)越性和親密度參數(shù)設計的合理性。(3)提出了一種二分網(wǎng)絡社團結構檢測算法。通過分析二分網(wǎng)絡中節(jié)點間的

5、互連特點，設計出分別體現(xiàn)二分網(wǎng)絡中同種類型節(jié)點間與異種類型節(jié)點間的親密度關系。利用該親密度關系分析和聚類節(jié)點，形成多個子社團，再通過社團間的關系參數(shù)，進一步合并子社團，以形成最終的社團結構。實驗結果很好的反映了算法和參數(shù)設計的優(yōu)越性，并能有效地檢測出網(wǎng)絡的二分社團結構。本文設計和實現(xiàn)了針對不同網(wǎng)絡所提出的三種不同的基于網(wǎng)絡中節(jié)點間的親密關系的社團檢測算法，研究不斷地深入、遞進。其中基于關鍵節(jié)點的重疊社團劃分方法和非對稱親密度的算法針對的