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

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

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

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

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

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

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