基于大規(guī)模復(fù)雜網(wǎng)絡(luò)的重疊社團檢測算法研究.pdf

1、近年來，由于社交網(wǎng)絡(luò)的發(fā)展和大數(shù)據(jù)時代的興起，大規(guī)模復(fù)雜網(wǎng)絡(luò)社團檢測已成為研究熱點之一。社團檢測作為復(fù)雜網(wǎng)絡(luò)研究中一項基礎(chǔ)而又重要的工作，旨在挖掘網(wǎng)絡(luò)中一組節(jié)點集合，這些集合內(nèi)部的節(jié)點連接緊密，而集合之間的節(jié)點連接稀疏。然而在現(xiàn)實世界網(wǎng)絡(luò)中經(jīng)常存在一些節(jié)點可能會同時屬于多個社團的情況，即重疊社團結(jié)構(gòu)。因此，對重疊社團結(jié)構(gòu)的檢測更加重要且具有應(yīng)用價值。隨著網(wǎng)絡(luò)科學(xué)的不斷發(fā)展，許多復(fù)雜網(wǎng)絡(luò)的規(guī)模甚至包含數(shù)百萬數(shù)量的節(jié)點和數(shù)十億條邊。對如此大

2、規(guī)模的復(fù)雜網(wǎng)絡(luò)進行重疊社團挖掘一直是該領(lǐng)域內(nèi)的難點之一?；诖?，本文對大規(guī)模復(fù)雜網(wǎng)絡(luò)重疊社團檢測問題進行了深入研究，提出了一種基于弱團滲流思想的重疊社團檢測算法。此外，為了解決數(shù)百萬數(shù)量級的超大規(guī)模復(fù)雜網(wǎng)絡(luò)重疊社團檢測問題，本文還提出一種基于局部鄰居信息的快速重疊社團檢測算法。這兩種算法均是以檢測大規(guī)模復(fù)雜網(wǎng)絡(luò)重疊社團結(jié)構(gòu)為目的，相比較其他重疊社團檢測算法，本文所提算法計算效率更快，社團檢測精度更高。
　　本文的主要研究工作如下:

3、
　　(1)本文提出了一種基于弱團滲流的重疊社團檢測算法。k-團滲流方法是當(dāng)前最常用的重疊社團檢測算法之一，其基本思想是將社團結(jié)構(gòu)定義為由一系列共享很多節(jié)點的完全連通子圖組成。k-團滲流方法需要檢測網(wǎng)絡(luò)中所有k-團(即，k-clique)，然而k-團的檢測是NP完全問題，因此基于k-團滲流方法的時間復(fù)雜度很高。為了提高重疊社團檢測算法在大規(guī)模復(fù)雜網(wǎng)絡(luò)上檢測重疊社團的效率和準確性，本文利用網(wǎng)絡(luò)中的局部拓撲信息快速挖掘網(wǎng)絡(luò)中的弱團。本

4、文將弱團定義為由網(wǎng)絡(luò)中兩個關(guān)鍵節(jié)點及其公共鄰居組合而成，由于僅僅利用節(jié)點的鄰居信息，因此檢測弱團要比檢測k-團高效很多。同時在滲流過程中，提出新的相似度指標來衡量兩個弱團之間的相似性，并以此來判斷兩個弱團是否應(yīng)該合并，以提升算法的準確性。在新的相似度指標中不僅考慮了兩個弱團之間共享的節(jié)點數(shù)目還統(tǒng)計了弱團之間邊的連接數(shù)目。在LFR基準數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果表明，與現(xiàn)有幾種重疊社團檢測算法相比，基于弱團滲流的重疊社團檢測算法在計

5、算效率和發(fā)現(xiàn)重疊社團質(zhì)量方面都具有明顯優(yōu)勢。
　　(2)本文提出一種基于局部鄰居信息的快速重疊社團檢測算法。隨著社交網(wǎng)絡(luò)的興起和互聯(lián)網(wǎng)時代的發(fā)展，目前復(fù)雜網(wǎng)絡(luò)的規(guī)模變得越來越巨大。為了能夠在數(shù)百萬數(shù)量級這種超大規(guī)模復(fù)雜網(wǎng)絡(luò)中檢測重疊社團結(jié)構(gòu)，本文提出了一種基于局部鄰居信息的快速重疊社團檢測算法，稱之為OCLN(OverlappingCommunity detection by using Local-Neighborhood in

6、formation)算法。OCLN算法的基本思想在于首先利用網(wǎng)絡(luò)中節(jié)點的內(nèi)部度數(shù)和外部度數(shù)這些局部結(jié)構(gòu)快速擴充社團，隨后根據(jù)社團中每個節(jié)點的局部鄰居信息在該社團中的貢獻度計算節(jié)點的隸屬度指標。從社團中刪除掉一些隸屬度較低的節(jié)點，提高算法的準確性。由于整個算法全部利用網(wǎng)絡(luò)的局部結(jié)構(gòu)，因此OCLN算法的時間復(fù)雜度為線性，即O(n+m)，n為網(wǎng)絡(luò)中節(jié)點的數(shù)目，m為邊的數(shù)目。通過對LFR基準網(wǎng)絡(luò)和大規(guī)模真實網(wǎng)絡(luò)上的實驗分析表明，OCLN算法在算