1、大連理工大學(xué)碩士學(xué)位論文I碩士學(xué)位論文基于相似度的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)檢測(cè)算法研究基于相似度的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)檢測(cè)算法研究Researchondetectingalgithmsfcommunitystructuresincomplexwksbasedonintimacy作者姓名：秦小蒙學(xué)科、專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)學(xué)號(hào)：21409179指導(dǎo)教師：王興元完成日期：2017年05月大連理工大學(xué)DalianUniversityofTechnology

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

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

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

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