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

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

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

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

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

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

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