復(fù)雜網(wǎng)絡(luò)密度收縮社區(qū)檢測算法與應(yīng)用.pdf

1、現(xiàn)實(shí)生活中,大量的復(fù)雜系統(tǒng)都可以用網(wǎng)絡(luò)的方式表示,比如人際關(guān)系網(wǎng)絡(luò),生物網(wǎng)絡(luò),交通網(wǎng)絡(luò)等等。實(shí)際網(wǎng)絡(luò)有幾個(gè)比較重要的特征:無標(biāo)度特征、存在明顯的社區(qū)結(jié)構(gòu)、小世界特征等。本論文中主要討論了網(wǎng)絡(luò)中的社區(qū)檢測方法。隨著互聯(lián)網(wǎng)的快速發(fā)展,人類進(jìn)入了一個(gè)大數(shù)據(jù)時(shí)代,每天都會(huì)產(chǎn)生海量的數(shù)據(jù)需要處理,大數(shù)據(jù)處理中很重要的一個(gè)方面就是尋找數(shù)據(jù)中存在的社區(qū)結(jié)構(gòu),比如在社交網(wǎng)絡(luò)中,獲得社區(qū)結(jié)構(gòu)后,便可以將同一社區(qū)中但沒有直接聯(lián)系的用戶,推薦為好友。對于用戶

2、數(shù)以億計(jì)的網(wǎng)絡(luò),如此巨量的數(shù)據(jù)完全通過人工處理是不現(xiàn)實(shí)的,得益于計(jì)算技術(shù)的發(fā)展,我們可以通過計(jì)算機(jī)對數(shù)據(jù)進(jìn)行處理。這需要開發(fā)出高效的算法進(jìn)行實(shí)現(xiàn),目前存在的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測算法主要有四類:圖分割算法、層次聚類算法、基于模塊度優(yōu)化的算法和基于譜的算法。其中基于模塊度優(yōu)化的算法得到了廣泛的研究,并且在實(shí)際中也有應(yīng)用。但是基于模塊度優(yōu)化的算法存在的缺陷是,存在分辨率問題,也就是說當(dāng)社區(qū)的尺寸小于某個(gè)一定值時(shí),此社區(qū)便不能被正確的劃分。本論文主

3、要工作如下:
　　(1)在基于層次聚類、譜分析等社區(qū)劃分算法中,相似度函數(shù)是一個(gè)最基礎(chǔ)的部分,在本論文中提出了基于路徑的相似度計(jì)算函數(shù),函數(shù)中的參數(shù)可以根據(jù)網(wǎng)絡(luò)平均度的特征進(jìn)行自適應(yīng)調(diào)整,為不同路徑長度賦予了不同的權(quán)值,在最終的相似度中,較好的平衡了離被計(jì)算的兩個(gè)節(jié)點(diǎn)遠(yuǎn)近不同的局部連接信息在最終的相似度中起到的作用,可以在一定程度上避免基于模塊度優(yōu)化的算法帶來的分辨率問題,并且基于路徑長度的算法,計(jì)算量主要集中在鄰接矩陣相乘部分,

4、可以很方便的通過GPU、多核等實(shí)現(xiàn)并行計(jì)算。
　　(2)傳統(tǒng)的密度收縮算法(Dense Shrink)一個(gè)比較大的缺點(diǎn)就是尋找微社區(qū)步驟耗時(shí)較長,并且這一步驟也不方便通過并行計(jì)算方式實(shí)現(xiàn)。尋找微社區(qū)這一步驟在算法中的有效性,實(shí)際上跟相似度計(jì)算函數(shù)及網(wǎng)絡(luò)中節(jié)點(diǎn)的連接狀況密切相關(guān),根據(jù)網(wǎng)絡(luò)本身的特征選擇合適的相似度計(jì)算函數(shù)可以替代尋找微社區(qū)這一步所起到的作用,不再需要進(jìn)行此步的迭代計(jì)算,提出了不需要尋找微社區(qū)的DSMCF(Dense