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

李 輝，張建朋，陳福才

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

3 算法描述

3.1 相關(guān)定義

節(jié)點(diǎn)的貢獻(xiàn)度.節(jié)點(diǎn)v對(duì)社區(qū)C的貢獻(xiàn)度定義為

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

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

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

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

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

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

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

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

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

圖1 一條新邊到來(lái)時(shí)的處理示意圖

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

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

3.3 復(fù)雜度分析

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

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

4 實(shí)驗(yàn)評(píng)估

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

4.1 對(duì)比算法

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

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

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

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

CoEuS［8］：基于流式的局部擴(kuò)展社區(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］：基于生成對(duì)抗網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法，通過(guò)模體級(jí)（motif-level）生成器和判別器之間的競(jìng)爭(zhēng)，迭代地對(duì)學(xué)習(xí)到的向量進(jìn)行優(yōu)化并輸出最終的社區(qū)結(jié)構(gòu).

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

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

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

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

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

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

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

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

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

4.3 評(píng)價(jià)指標(biāo)

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

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

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

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

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

4.4 實(shí)驗(yàn)結(jié)果

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

圖2展示了SOCD 算法和其他6種算法在不同規(guī)模合成網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果，其中BigClam和Community-GAN 算法計(jì)算復(fù)雜度較高，在節(jié)點(diǎn)為100 萬(wàn)的網(wǎng)絡(luò)上12小時(shí)內(nèi)未運(yùn)算出結(jié)果.通過(guò)圖2可以發(fā)現(xiàn)，隨著網(wǎng)絡(luò)規(guī)模的增加，算法的準(zhǔn)確度呈下降趨勢(shì).在網(wǎng)絡(luò)規(guī)模從1 000增加到10 000時(shí)，準(zhǔn)確度只是稍微下降，當(dāng)規(guī)模增加到十萬(wàn)甚至一百萬(wàn)時(shí)，準(zhǔn)確度有一個(gè)明顯的下降.這個(gè)結(jié)果與文獻(xiàn)［16］的結(jié)論一致，算法的精度隨著混淆系數(shù)以及網(wǎng)絡(luò)規(guī)模的增大而下降.這主要是由于使用的LFR 基準(zhǔn)圖參數(shù)會(huì)造成分辨率極限和視野極限從而造成性能下降.從圖中還可以看出，在網(wǎng)絡(luò)規(guī)模較小時(shí)，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ù)下的實(shí)驗(yàn)結(jié)果，由圖中可以看出，隨著混淆系數(shù)μ不斷增大，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)愈發(fā)的不明顯，SOCD 的精度在下降.當(dāng)μ＜0.4 時(shí)，算法精度緩慢下降，當(dāng)μ＞0.4 時(shí)，算法精度才開(kāi)始有一個(gè)較大的下降；這說(shuō)明了SOCD 算法具有較強(qiáng)的魯棒性.綜上，通過(guò)在合成網(wǎng)絡(luò)上進(jìn)行的一系列實(shí)驗(yàn)，證明了SOCD算法的有效性和魯棒性.

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

4.4.2 真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

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

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

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

圖4 不同邊規(guī)模下算法的運(yùn)行時(shí)間

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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