李 輝，張建朋，陳福才

（信息工程大學(xué)信息技術(shù)研究所，河南鄭州 450002）

1 引言

復(fù)雜網(wǎng)絡(luò)普遍存在于物理自然世界和人類社會之中，近些年來受到了人們的廣泛關(guān)注.復(fù)雜網(wǎng)絡(luò)可以將各個領(lǐng)域的實體以及實體之間的關(guān)系進行抽象.復(fù)雜網(wǎng)絡(luò)雖然形態(tài)各異，但仍然表現(xiàn)出高度的有序性和組織性，呈現(xiàn)出明顯的社區(qū)結(jié)構(gòu).一個良好的社區(qū)應(yīng)該具有內(nèi)部連接緊密、外部連接稀疏的特性.利用網(wǎng)絡(luò)拓?fù)渲兴N含的信息從網(wǎng)絡(luò)中發(fā)現(xiàn)模塊化的結(jié)構(gòu)則被稱為社區(qū)發(fā)現(xiàn)，也被稱為圖聚類或社區(qū)檢測.社區(qū)發(fā)現(xiàn)對復(fù)雜網(wǎng)絡(luò)的拓?fù)浞治觥⒐δ芊治龊托袨轭A(yù)測具有重要的理論意義和實踐價值.早期的社區(qū)發(fā)現(xiàn)算法主要將節(jié)點劃分到單個社區(qū).然而，真實網(wǎng)絡(luò)中的社區(qū)經(jīng)常相互重疊，一個節(jié)點可以屬于多個社區(qū)，這些重疊節(jié)點對信息的傳播和網(wǎng)絡(luò)的演化具有重要價值［1］.一方面，重疊節(jié)點具有“多面性”，對重疊節(jié)點的挖掘有利于更全面地了解節(jié)點的特性.另一方面，重疊節(jié)點是社區(qū)間的橋梁，對社區(qū)間的交互和社區(qū)演化能夠發(fā)揮關(guān)鍵作用.因此，識別出這些重疊社區(qū)對理解真實網(wǎng)絡(luò)的結(jié)構(gòu)和功能具有重要意義.

近些年來，眾多社區(qū)發(fā)現(xiàn)算法相繼被提出來解決各個領(lǐng)域的實際問題，如基于模塊度優(yōu)化［2］、基于局部擴展［3，4］、基于圖表示學(xué)習(xí)［5］等算法.然而，隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)的規(guī)模越來越大，已有的很多算法在計算時間和內(nèi)存消耗上都無法對如此規(guī)模巨大的網(wǎng)絡(luò)進行處理.目前，解決網(wǎng)絡(luò)數(shù)據(jù)規(guī)模過大問題主要有2 種思路.一是采用并行算法［6，7］，利用多個集群來加速運算，將原有的一些經(jīng)典算法進行改進以適應(yīng)分布式運算，但這種方法需要大量的計算資源.二是基于流式分析［8，9］，核心思想是以流的方法對網(wǎng)絡(luò)中的邊進行單遍掃描處理，每條邊只需處理一次，不需要一次性將整個網(wǎng)絡(luò)讀入內(nèi)存，時間復(fù)雜度和空間復(fù)雜度都較低，適用于處理大規(guī)模網(wǎng)絡(luò).然而，文獻［8］所提算法需要先驗信息，使得算法實用性不高.文獻［9］利用的網(wǎng)絡(luò)結(jié)構(gòu)信息較少，算法精度有待進一步提升，且不支持重疊社區(qū)的檢測.為了解決上述存在的問題，本文提出一種基于流式分析的大規(guī)模網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法（Streaming-based Overlapping Community Detection algorithm，SOCD）.本文主要貢獻包括：

（1）算法通過對網(wǎng)絡(luò)中的每條邊進行單遍掃描處理，每條邊僅被處理一次，擁有線性的時間和空間復(fù)雜度，無需任何先驗信息，能夠快速地挖掘出大規(guī)模網(wǎng)絡(luò)中隱藏的社區(qū)結(jié)構(gòu)，并且可以識別出網(wǎng)絡(luò)中的重疊社區(qū)；

（2）算法引入節(jié)點的貢獻度來衡量節(jié)點與社區(qū)之間的緊密程度，并且與節(jié)點移動前后社區(qū)之間的連邊數(shù)量等信息共同指導(dǎo)節(jié)點的劃分，提高了社區(qū)劃分的精度；

（3）在人工合成網(wǎng)絡(luò)以及6個大規(guī)模真實網(wǎng)絡(luò)上的實驗結(jié)果表明了SOCD 算法的高效性和魯棒性，SOCD算法在運算時間上具有較大的優(yōu)勢，相較于非流式算法，SOCD 算法要快10 倍以上，并且在大規(guī)模網(wǎng)絡(luò)上能夠取得近似甚至更好的社區(qū)劃分精度.

2 相關(guān)工作

隨著社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)的興起，網(wǎng)絡(luò)的規(guī)模呈爆炸式增長，已有的許多算法無法有效處理這些規(guī)模龐大的網(wǎng)絡(luò).近些年，一種新的解決方案被提出用來解決網(wǎng)絡(luò)規(guī)模過大的問題，即以流的方式對網(wǎng)絡(luò)進行處理.基于流式方法的核心思想是對網(wǎng)絡(luò)中的邊進行單遍掃描處理［10］，無需一次性將整個網(wǎng)絡(luò)讀入內(nèi)存，擁有較低的時間和空間復(fù)雜度，能夠提升在大規(guī)模網(wǎng)絡(luò)中挖掘社區(qū)的效率.Yun 等人［11］提出了一種空間消耗隨網(wǎng)絡(luò)線性增長的算法來解決內(nèi)存限制的問題.該算法首先構(gòu)建網(wǎng)絡(luò)的鄰接矩陣，然后順序讀取鄰接矩陣的列向量進行處理，通過對鄰接矩陣的部分信息進行局部譜聚類，從而對節(jié)點進行劃分.算法無需一次性處理整個鄰接矩陣，只需順序的讀取鄰接矩陣的列向量進行運算即可.算法所需內(nèi)存小，但需要提前構(gòu)建網(wǎng)絡(luò)的鄰接矩陣且較為耗時.Liakos等人［8］提出了基于種子集擴展的流式社區(qū)發(fā)現(xiàn)算法.算法通過流的方式讀取網(wǎng)絡(luò)中的每條邊并進行處理，在時間窗口內(nèi)，通過種子向外擴張，然后對社區(qū)進行剪枝以保證社區(qū)的質(zhì)量，并且能夠自動確定社區(qū)的大小.算法具有較高的計算效率，通過特殊的數(shù)據(jù)結(jié)構(gòu)，所需空間與網(wǎng)絡(luò)規(guī)模成正比.但是算法需要提前指定社區(qū)的個數(shù)，這使得實用性大大降低.Hollocou等人［9］提出了線性流式的社區(qū)發(fā)現(xiàn)算法.算法基于社區(qū)內(nèi)邊的數(shù)量要遠(yuǎn)大于社區(qū)之間邊的數(shù)量的特性，認(rèn)為在網(wǎng)絡(luò)中隨機的選取一條邊，這條邊是社區(qū)內(nèi)的邊的概率要遠(yuǎn)大于是社區(qū)間邊的概率.因此，當(dāng)網(wǎng)絡(luò)中的邊以隨機的順序到達(dá)，算法根據(jù)邊到達(dá)的先后順序以及節(jié)點的度信息來判定是社區(qū)內(nèi)的邊還是社區(qū)間的邊.算法以流的方式處理每一條邊且每條邊只處理一次，可以快速處理大規(guī)模網(wǎng)絡(luò)并且所需內(nèi)存小.但算法僅通過節(jié)點度大小來判斷節(jié)點的移動，處理規(guī)則過于簡單，會造成很多錯誤的移動，并且該算法只能挖掘出非重疊社區(qū).

針對以上流式算法存在的問題，本文提出了一種基于流式分析的大規(guī)模網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法（SOCD）.算法在2個方面進行優(yōu)化以解決上述問題.一是保證算法在具有線性計算復(fù)雜度的情況下利用更多的信息對每條邊進行處理，提高社區(qū)劃分的質(zhì)量.二是將其擴展到重疊社區(qū)領(lǐng)域以挖掘出真實網(wǎng)絡(luò)中存在的大量重疊社區(qū)結(jié)構(gòu).本文定義了節(jié)點的貢獻度來量化節(jié)點與社區(qū)的緊密程度，并且與節(jié)點的度信息以及節(jié)點移動前后社區(qū)之間連邊數(shù)量的變化信息來對每條邊進行處理，更加合理地對節(jié)點進行劃分，提高社區(qū)劃分的精度.同時，算法可以根據(jù)節(jié)點信息識別出網(wǎng)絡(luò)中的重疊節(jié)點.

3 算法描述

3.1 相關(guān)定義

節(jié)點的貢獻度.節(jié)點v對社區(qū)C的貢獻度定義為

其中，||表示節(jié)點v的鄰居節(jié)點在社區(qū)C中的數(shù)量，|N(v)|表示節(jié)點v的鄰居節(jié)點數(shù)量.越大，表示節(jié)點v對社區(qū)C的貢獻值越大，節(jié)點v與社區(qū)C的聯(lián)系越緊密.

給定網(wǎng)絡(luò)G(V，E)，V是網(wǎng)絡(luò)中的節(jié)點集，E?V×V代表網(wǎng)絡(luò)中的邊集，N=|V|表示網(wǎng)絡(luò)中節(jié)點的數(shù)量，M=|E|表示邊的數(shù)量.假定A∈V，B∈V，給出以下定義：

由以上定義可知e(A，A)?e(A).

假定C?V為要挖掘的社區(qū)，隨機不重復(fù)地從網(wǎng)絡(luò)中選取邊，定義從e(C)中最先選取的k條邊屬于e(C，C)為事件Intrak(C)，則此事件的概率為

當(dāng)l較小時，φl(C)非常接近社區(qū)C的連通度（conductance）φ(C)，

根據(jù)社區(qū)的性質(zhì)，一個良好的社區(qū)應(yīng)該內(nèi)部連接緊密，外部連接稀疏，具有較低的連通度.因此，當(dāng)C為一個良好的社區(qū)時，l取較小值，則最先選擇的k條邊有更大概率是社區(qū)內(nèi)的邊.

3.2 基于流式分析的大規(guī)模網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法

算法在處理每一條邊e=(u，v)時，如果兩端的節(jié)點在一個社區(qū)之內(nèi)，則對此條邊不做處理.如果兩端節(jié)點位于不同社區(qū)，則需要對兩端節(jié)點的社區(qū)歸屬重新判定.在文獻［9］中，根據(jù)du和dv是否小于閾值D來進行判定.如果du或dv大于給定的閾值D，算法認(rèn)為節(jié)點u或v在之前已被處理過多次，大概率是社區(qū)間的邊，則不做處理；否則，將度小的節(jié)點移動到度大的節(jié)點所在的社區(qū).在實驗中發(fā)現(xiàn)，僅利用節(jié)點的度信息來判斷節(jié)點的社區(qū)歸屬會造成一些錯誤.這樣的判定準(zhǔn)則太過簡單，利用的信息太少，會在節(jié)點移動的過程中使移動方向發(fā)生錯誤，造成節(jié)點u本應(yīng)該從社區(qū)A移動到社區(qū)B，但實際卻是節(jié)點v從社區(qū)B移動到了社區(qū)A.這個錯誤的移動不僅損害了兩個社區(qū)的質(zhì)量，還會對后續(xù)節(jié)點的劃分造成錯誤累計，從而使得整個網(wǎng)絡(luò)的社區(qū)劃分精度不高.發(fā)生這種問題的主要原因在于僅利用節(jié)點的度信息無法準(zhǔn)確衡量節(jié)點與社區(qū)之間的緊密程度，無法準(zhǔn)確判斷移動方向.基于以上問題，本文定義節(jié)點貢獻度來衡量節(jié)點與社區(qū)的緊密程度.由貢獻度定義可知，節(jié)點u在社區(qū)C中的鄰居節(jié)點越多，則節(jié)點u與社區(qū)C的聯(lián)系越緊密，對社區(qū)的貢獻度也越大，有著更大的概率被劃分到社區(qū)C中.因此，在判斷節(jié)點移動方向時不僅需要考慮節(jié)點的度信息，還需要考慮節(jié)點對每個社區(qū)的貢獻度大小.由社區(qū)的特性可知，一個社區(qū)內(nèi)部連接越緊密，外部連接越稀疏，則社區(qū)的質(zhì)量越高.節(jié)點在移動的過程中會造成兩個社區(qū)間連邊的數(shù)量的變化，為了提高發(fā)現(xiàn)社區(qū)的質(zhì)量，期望節(jié)點移動后社區(qū)之間的連邊數(shù)量變少.綜上所述，在判斷節(jié)點的移動方向時，需要將節(jié)點的度、節(jié)點對每個社區(qū)的貢獻度以及移動前后社區(qū)之間連邊數(shù)量的變化等信息考慮在內(nèi).這樣可以更加精細(xì)地對節(jié)點進行劃分，降低節(jié)點劃分的錯誤率.

如圖1所示，當(dāng)一條新的連邊（2，4）到達(dá)時，若僅根據(jù)節(jié)點度信息來移動，則節(jié)點2 應(yīng)該移動到節(jié)點4 所在的社區(qū).但是很顯然，這破壞了社區(qū)D的結(jié)構(gòu)，而且使得社區(qū)D和社區(qū)C之間的連邊增多.這是因為，雖然節(jié)點4 的度比節(jié)點2 的度大，但是節(jié)點2 的鄰居節(jié)點都在社區(qū)D內(nèi)部，而節(jié)點4 的鄰居節(jié)點只有1 個在社區(qū)C，節(jié)點2 與社區(qū)D的緊密程度要大于節(jié)點4 與社區(qū)C之間的緊密程度.為了解決上述問題，本文采用度信息來判斷節(jié)點是否需要移動，用節(jié)點對社區(qū)的貢獻度以及移動前后社區(qū)間的連邊數(shù)量變化來判斷節(jié)點的移動方向.

圖1 一條新邊到來時的處理示意圖

本文所提SOCD 算法的處理過程如算法1所示.算法的輸入為網(wǎng)絡(luò)的邊的序列以及閾值D，在實驗中閾值D取網(wǎng)絡(luò)中節(jié)點度的眾數(shù)，閾值D的選取會在后續(xù)內(nèi)容進行探討.為了能夠隨機讀取網(wǎng)絡(luò)中的邊，首先將網(wǎng)絡(luò)中邊的順序打亂，并對所有節(jié)點進行初始化.當(dāng)讀取一條新的邊e=(u，v)時，節(jié)點u和v的度增加1.如果其中一個節(jié)點的度為1，則將其加入到另一個節(jié)點所在的社區(qū)；如果都為1，則將兩個節(jié)點劃分到一個社區(qū)，這樣可以避免孤立節(jié)點的小社區(qū).如果du和dv都小于或等于D，則需要考慮節(jié)點是否為重疊節(jié)點以及節(jié)點是否需要移動并判斷移動方向.此處需要衡量兩個指標(biāo)：一是節(jié)點對每個社區(qū)的貢獻度，節(jié)點對社區(qū)的貢獻度越大，節(jié)點與社區(qū)之間的聯(lián)系越緊密，在移動時應(yīng)將貢獻度小的節(jié)點移動到貢獻度大的節(jié)點所在的社區(qū)；二是節(jié)點移動前后兩個社區(qū)之間連邊數(shù)量的變化，連邊數(shù)量越少，社區(qū)的質(zhì)量越高，因此應(yīng)該使移動后社區(qū)之間的連邊數(shù)量比移動前社區(qū)間的連邊數(shù)量少.根據(jù)這兩個指標(biāo)，對每一條新來的邊進行節(jié)點劃分.

首先計算節(jié)點u和v對各自社區(qū)的貢獻度，若，根據(jù)貢獻度指標(biāo)應(yīng)將節(jié)點v移動到節(jié)點u所在的社區(qū)，但還需要考慮移動前后社區(qū)之間連邊數(shù)量的變化.定義節(jié)點移動后社區(qū)間連邊數(shù)量與移動前社區(qū)間連邊數(shù)量的差值為ΔN.如果ΔN＜0，說明此移動方向使兩個社區(qū)之間的連邊數(shù)量變少，讓兩個指標(biāo)都得到了優(yōu)化，提升了社區(qū)的質(zhì)量.如果ΔN＞0，則說明節(jié)點v有較多鄰居節(jié)點在其他社區(qū).根據(jù)社區(qū)的性質(zhì)，節(jié)點v大概率是一個重疊節(jié)點，因此把節(jié)點v作為重疊節(jié)點并加入到u所在的社區(qū).如果，若移動前后ΔN＜0，使社區(qū)間的連邊數(shù)量變少，則說明也是一個正向的移動；若ΔN=0，那么移動前后對兩個目標(biāo)都沒有得到優(yōu)化，因此不做任何處理.由以上的判斷準(zhǔn)則，可以對網(wǎng)絡(luò)中的每一條邊進行處理并對節(jié)點進行劃分.

3.3 復(fù)雜度分析

SOCD算法的運算時間主要包括三部分.第一部分計算閾值D，閾值D為網(wǎng)絡(luò)中節(jié)點度的眾數(shù)，只需要將所有的邊掃描一遍，時間復(fù)雜度為O（M）；第二部分是將網(wǎng)絡(luò)中邊的順序隨機化，復(fù)雜度為O（M）；第三部分是算法的核心處理過程，算法流式的對每一條邊進行處理，時間復(fù)雜度為O（M）.因此，SOCD 算法總的時間復(fù)雜度為O（M）.相較于其他算法，SOCD 降低了時間復(fù)雜度，能夠快速處理大規(guī)模網(wǎng)絡(luò).算法對每條邊進行處理時，僅需比較節(jié)點的度、節(jié)點對社區(qū)的貢獻度以及節(jié)點移動前后社區(qū)間連邊數(shù)量的變化，這些信息計算簡單，可以非常快速地完成.這使得算法可以在極短的時間內(nèi)對每條邊進行處理.SOCD 算法的運行時間與邊的數(shù)量成線性關(guān)系，隨著網(wǎng)絡(luò)規(guī)模的持續(xù)增長，算法仍能快速地對其進行處理.

對于算法的空間復(fù)雜度，計算節(jié)點度的眾數(shù)時需要大小為n的數(shù)組，復(fù)雜度為O（N）；算法在處理每一條邊時，需要存儲每個節(jié)點當(dāng)前的度數(shù)，復(fù)雜度為O（N）；需要存儲節(jié)點當(dāng)前所在社區(qū)的編號，復(fù)雜度為O（N）；需要存儲節(jié)點對當(dāng)前所在社區(qū)的社區(qū)貢獻度，復(fù)雜度為O（N）；還需要存儲每個社區(qū)內(nèi)的邊，復(fù)雜度為O（M）.因此，SOCD 算法總的空間復(fù)雜度為O（N+M），表明了算法擁有線性的空間復(fù)雜度.

4 實驗評估

為了驗證本文所提SOCD 算法的有效性和高效性，分別采用不同規(guī)模的人工合成網(wǎng)絡(luò)以及真實世界的大規(guī)模網(wǎng)絡(luò)來進行實驗，并與其他幾種高效算法進行對比實驗.實驗環(huán)境為：Ubuntu16.04 操作系統(tǒng)，Intel（R）Xeon（R）CPU E5-2620 v4 @ 2.10 GHz，128 GB 內(nèi)存的服務(wù)器，算法實現(xiàn)為Python 3.6.

4.1 對比算法

為了評估本文提出算法的性能，將本文算法與其他6種高效算法進行了對比，其中既有非重疊社區(qū)算法也有重疊社區(qū)算法，既有流式算法也有非流式算法.

4.1.1 非重疊社區(qū)發(fā)現(xiàn)算法

Louvain［2］：基于模塊度優(yōu)化的高效算法.

4.1.2 重疊社區(qū)發(fā)現(xiàn)算法

CoEuS［8］：基于流式的局部擴展社區(qū)發(fā)現(xiàn)算法.

BigClam［12］：基于非負(fù)矩陣分解的重疊社區(qū)發(fā)現(xiàn)算法.

OCSC（Overlap Compact Structure Community detection algorithm）［13］：基于結(jié)構(gòu)緊密性的重疊社區(qū)發(fā)現(xiàn)算法，可分布式并行處理大規(guī)模網(wǎng)絡(luò).

CommunityGAN［14］：基于生成對抗網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法，通過模體級（motif-level）生成器和判別器之間的競爭，迭代地對學(xué)習(xí)到的向量進行優(yōu)化并輸出最終的社區(qū)結(jié)構(gòu).

LCDNN（Local Community Detection algorithm based on NGC Nodes）［4］：基于節(jié)點中心性的社區(qū)發(fā)現(xiàn)算法，通過局部擴展來挖掘網(wǎng)絡(luò)中的重疊社區(qū).

4.2 數(shù)據(jù)集

為了評估算法的性能，分別將7種算法在人工合成網(wǎng)絡(luò)以及真實網(wǎng)絡(luò)上進行對比實驗.

4.2.1 人工合成網(wǎng)絡(luò)

采用LRF-benchmark 基準(zhǔn)程序［15］生成兩組人工合成網(wǎng)絡(luò)D1和D2.D1 用來測試算法在不同規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集下的性能，詳細(xì)參數(shù)如表1所示.其中，N表示網(wǎng)絡(luò)的節(jié)點數(shù)，k表示網(wǎng)絡(luò)的平均度，on 表示網(wǎng)絡(luò)中重疊節(jié)點的比例，μ表示混淆系數(shù)，μ越小說明網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯.D2 為了驗證SOCD 算法的魯棒性，生成了不同混淆系數(shù)下的網(wǎng)絡(luò)，其中N=100 000，k=20，μ為0.1～0.7.

表1 人工合成網(wǎng)絡(luò)D1參數(shù)

4.2.2 真實網(wǎng)絡(luò)

使用斯坦福大學(xué)社交網(wǎng)絡(luò)分析項目（Stanford Network Analysis Platform，SNAP）提供的6個公開的真實網(wǎng)絡(luò)對算法進行實驗評估，這些網(wǎng)絡(luò)包括商品共同購買網(wǎng)絡(luò)（Amazon）、科研協(xié)作網(wǎng)絡(luò)（DBLP）以及社交網(wǎng)絡(luò)（YouTube，LiveJournal，Orkut，F(xiàn)riendster）.這些網(wǎng)絡(luò)的規(guī)模從三十萬節(jié)點到六千萬節(jié)點，從一百萬條邊到2億條邊，每一個網(wǎng)絡(luò)都帶有節(jié)點真實的社區(qū)標(biāo)簽.這些大規(guī)模且?guī)в袠?biāo)簽的數(shù)據(jù)集可以很好地測試算法的性能，網(wǎng)絡(luò)的特征如表2所示.

表2 6個大規(guī)模真實網(wǎng)絡(luò)的特征

4.3 評價指標(biāo)

由于上述網(wǎng)絡(luò)節(jié)點的社區(qū)標(biāo)簽已知，因此采用有監(jiān)督的2 個評價指標(biāo)平均F1-Score和擴展的歸一化互信息ENMI來評估算法性能.

F1-Score 通常用來評價分類結(jié)果的好壞.它綜合考慮了精確率（precision）和召回率（recall），可以用來衡量檢測到的社區(qū)與真實社區(qū)之間的差異.給定一個檢測到的社區(qū)Cf和真實社區(qū)Ct，F(xiàn)1-Score定義如下：

社區(qū)發(fā)現(xiàn)算法將網(wǎng)絡(luò)劃分為K個社區(qū)，其中，Cf={C1，C2，…，CK}，真實的社區(qū)劃分Ct={C1，C2，…，CL}，定義算法劃分社區(qū)的F1-Score為

平均F1-Score 越大，說明算法的精度越高，檢測到的社區(qū)與真實社區(qū)越相近.

ENMI 是基于信息熵的評價指標(biāo)，用于量化2 個社區(qū)之間的相似程度.取值［0，1］，ENMI 越大，表示發(fā)現(xiàn)的社區(qū)與真實社區(qū)越接近.

4.4 實驗結(jié)果

4.4.1 人工合成網(wǎng)絡(luò)實驗結(jié)果

圖2展示了SOCD 算法和其他6種算法在不同規(guī)模合成網(wǎng)絡(luò)上的實驗結(jié)果，其中BigClam和Community-GAN 算法計算復(fù)雜度較高，在節(jié)點為100 萬的網(wǎng)絡(luò)上12小時內(nèi)未運算出結(jié)果.通過圖2可以發(fā)現(xiàn)，隨著網(wǎng)絡(luò)規(guī)模的增加，算法的準(zhǔn)確度呈下降趨勢.在網(wǎng)絡(luò)規(guī)模從1 000增加到10 000時，準(zhǔn)確度只是稍微下降，當(dāng)規(guī)模增加到十萬甚至一百萬時，準(zhǔn)確度有一個明顯的下降.這個結(jié)果與文獻［16］的結(jié)論一致，算法的精度隨著混淆系數(shù)以及網(wǎng)絡(luò)規(guī)模的增大而下降.這主要是由于使用的LFR 基準(zhǔn)圖參數(shù)會造成分辨率極限和視野極限從而造成性能下降.從圖中還可以看出，在網(wǎng)絡(luò)規(guī)模較小時，SOCD 算法的平均F1-Score 值要比傳統(tǒng)的方法精度低，但兩者相差并不懸殊.隨著網(wǎng)絡(luò)規(guī)模逐漸增大，SOCD 算法的平均F1-Score和傳統(tǒng)的方法較為接近；這表明在大規(guī)模網(wǎng)絡(luò)上，相較于傳統(tǒng)算法，SOCD 算法能取得近似的結(jié)果.

圖2 不同規(guī)模的合成網(wǎng)絡(luò)上的準(zhǔn)確度比較

圖3 展示了SOCD 算法在不同混淆系數(shù)下的實驗結(jié)果，由圖中可以看出，隨著混淆系數(shù)μ不斷增大，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)愈發(fā)的不明顯，SOCD 的精度在下降.當(dāng)μ＜0.4 時，算法精度緩慢下降，當(dāng)μ＞0.4 時，算法精度才開始有一個較大的下降；這說明了SOCD 算法具有較強的魯棒性.綜上，通過在合成網(wǎng)絡(luò)上進行的一系列實驗，證明了SOCD算法的有效性和魯棒性.

圖3 不同μ值下SOCD算法的精度

4.4.2 真實網(wǎng)絡(luò)上的實驗結(jié)果

表3列出了SOCD 算法和其他算法在6個大規(guī)模真實網(wǎng)絡(luò)上運行的時間，表格中標(biāo)“—”的數(shù)據(jù)對應(yīng)執(zhí)行時間超過12 小時未返回結(jié)果的算法.由表可知，SOCD算法處理100 萬條邊只需要18 s，處理1.8 億條邊大約需要7 個小時，這是非常高效的.當(dāng)網(wǎng)絡(luò)規(guī)模到達(dá)一定程度時，常規(guī)的方法就無法在有限的時間內(nèi)返回結(jié)果，而本文算法可以很快速地將這些大規(guī)模網(wǎng)絡(luò)進行處理，挖掘出其中的社區(qū)，這說明了本文算法在處理大規(guī)模網(wǎng)絡(luò)時具有巨大的時間優(yōu)勢.而基于流式的局部擴展算法CoEuS 只在前4 個數(shù)據(jù)集上運算出結(jié)果，無法在12 個小時內(nèi)在剩下的大規(guī)模網(wǎng)絡(luò)中返回結(jié)果，這主要因為CoEuS 的時間復(fù)雜度與社區(qū)個數(shù)以及連邊數(shù)量成正比.表2 中6 個數(shù)據(jù)集的社區(qū)個數(shù)和連邊數(shù)量相差較大，特別是Orkut 數(shù)據(jù)集的社區(qū)個數(shù)以及Friendster 數(shù)據(jù)集的連邊數(shù)量都遠(yuǎn)大于其他數(shù)據(jù)集，導(dǎo)致CoEuS 沒能在規(guī)定時間返回結(jié)果.但相較于非流式的局部擴展算法LCDNN，采用流式的CoEuS 算法極大地提升了運算速度，這表明了以流的方式對網(wǎng)絡(luò)進行處理的高效性.

表3 算法在大規(guī)模真實網(wǎng)絡(luò)上的運行時間

圖4 顯示了7 種算法在不同邊的規(guī)模下的運行時間.由圖中可知，SOCD 算法運行時間至少比非流式方法快一個數(shù)量級，且與邊的規(guī)模成線性關(guān)系.這是因為SOCD 算法降低了時間復(fù)雜度，所以計算速度能夠有數(shù)量級的提升.

圖4 不同邊規(guī)模下算法的運行時間

圖5和圖6 分別展示了SOCD 算法和其他算法在6個真實大規(guī)模網(wǎng)絡(luò)上社區(qū)劃分的平均F1-Score和ENMI.從圖中可以看出，在Amazon 數(shù)據(jù)集上，CommunityGAN算法有著最好的實驗效果，這是因為CommunityGAN 利用生成對抗網(wǎng)絡(luò)能夠更好地提取網(wǎng)絡(luò)的特征，但是模型預(yù)訓(xùn)練和訓(xùn)練時間較長，沒辦法處理較大規(guī)模的網(wǎng)絡(luò).當(dāng)網(wǎng)絡(luò)的規(guī)模增大到1億條邊時，就只有SOCD算法和并行算法OCSC能夠在有限的時間內(nèi)返回結(jié)果.并行算法OCSC 設(shè)置了8個集群，但在12個小時內(nèi)仍然沒能成功處理Friendster數(shù)據(jù)集，這是因為分布式算法對效率的提升是有限的，當(dāng)集群規(guī)模到達(dá)一定數(shù)量時，繼續(xù)增加集群數(shù)量也無法提升效率，而SOCD 算法可以高效的挖掘出Friendster 網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu).從圖中還可以發(fā)現(xiàn)，SOCD算法在YouTube，LiveJournal以及Orkut數(shù)據(jù)集上與分布式算法OCSC 的準(zhǔn)確率較為接近，在You-Tube，LiveJournal數(shù)據(jù)集上還要優(yōu)于Louvain算法.而基于流式的局部算法CoEuS 在大幅提高運算效率的情況下還可以取得與OCSC和LCDNN近似的結(jié)果，這都說明了對大規(guī)模網(wǎng)絡(luò)進行流式處理的巨大優(yōu)勢.綜上所述，基于流式分析的SOCD 算法具有線性的時間復(fù)雜度，在處理大規(guī)模網(wǎng)絡(luò)上具有很大的時間優(yōu)勢，并且能夠和非流式算法獲得近似甚至更優(yōu)的社區(qū)劃分結(jié)果.

圖5 算法在真實網(wǎng)絡(luò)上的平均F1-Score

圖6 算法在真實網(wǎng)絡(luò)上的ENMI

4.5 參數(shù)D敏感性分析

在處理每一條邊的過程中，根據(jù)閾值D來決定節(jié)點是否需要移動.當(dāng)D較小時，會將大社區(qū)劃分為多個小社區(qū)，極端情況D=1時，每個社區(qū)僅包含2個節(jié)點；當(dāng)D太大時，算法對社區(qū)間的邊不敏感，會造成挖掘出的社區(qū)質(zhì)量下降.因此，D與網(wǎng)絡(luò)中的度分布有著很大的關(guān)系，可以考慮從以下幾個選項來選擇此參數(shù).

平均度：D=d_avg，網(wǎng)絡(luò)中節(jié)點度的平均值，在實驗中四舍五入取整.

中位度：D=d_med，網(wǎng)絡(luò)中節(jié)點度的中位數(shù).

眾數(shù)度：D=d_mod e，網(wǎng)絡(luò)中節(jié)點度的眾數(shù).

定義Q(D)=為參數(shù)對應(yīng)社區(qū)的相對質(zhì)量比，其中D={d_avg，d_med，d_mod e}，maxF1(D')=max(F1(d_avg)，F(xiàn)1(d_med)，F(xiàn)1(d_mod e)).

在2 個真實網(wǎng)絡(luò)以及2 個合成網(wǎng)絡(luò)上的實驗結(jié)果如圖7 所示，由圖中可知，除了在N=100 000 網(wǎng)絡(luò)上眾數(shù)度對應(yīng)的社區(qū)質(zhì)量不是最高，在其他網(wǎng)絡(luò)上都是最優(yōu).因此，選擇網(wǎng)絡(luò)中節(jié)點度的眾數(shù)作為閾值D可以獲得更優(yōu)的結(jié)果.

圖7 D的不同選擇對應(yīng)的相對質(zhì)量Q

5 結(jié)束語

針對網(wǎng)絡(luò)數(shù)據(jù)規(guī)模龐大的問題，本文提出了一種基于流式分析的大規(guī)模網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法（SOCD）.該算法定義了節(jié)點對社區(qū)的貢獻度來量化節(jié)點與社區(qū)之間的緊密程度，并利用社區(qū)間的連邊數(shù)量等信息來共同指導(dǎo)節(jié)點的劃分.算法擁有線性的時間和空間復(fù)雜度，能夠快速地挖掘出大規(guī)模網(wǎng)絡(luò)中隱藏的社區(qū)結(jié)構(gòu).在合成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)上的實驗結(jié)果表明了SOCD算法具有較強的魯棒性和較高的運算效率，并且能夠挖掘出網(wǎng)絡(luò)中的重疊社區(qū).相較于非流式算法，SOCD 要快10倍以上，這是由于算法降低了時間復(fù)雜度，運算時間與邊的規(guī)模成線性關(guān)系，所以能夠處理大規(guī)模甚至超大規(guī)模的網(wǎng)絡(luò)；并且SOCD 算法可以和非流式算法獲得相近甚至更優(yōu)的社區(qū)劃分.可以看到，網(wǎng)絡(luò)的規(guī)模越大，SOCD算法的優(yōu)勢就越顯著.