RGNE：粗糙?；木W(wǎng)絡(luò)嵌入式重疊社區(qū)發(fā)現(xiàn)方法

趙 霞 張澤華 張晨威 李 嫻

1(太原理工大學(xué)信息與計算機學(xué)院 太原 030024)2(伊利諾伊大學(xué)芝加哥分校計算機科學(xué)學(xué)院 美國芝加哥 60607)

互聯(lián)網(wǎng)技術(shù)的快速演進(jìn)，社交網(wǎng)絡(luò)已成為大數(shù)據(jù)時代的重要載體.通過社區(qū)結(jié)構(gòu)對網(wǎng)絡(luò)進(jìn)行描述，可簡化對整個網(wǎng)絡(luò)的功能、交互及其演化的研究.社區(qū)發(fā)現(xiàn)有助于更深地了解網(wǎng)絡(luò)的本質(zhì)，獲取推薦信息、預(yù)測網(wǎng)絡(luò)的演化等.社區(qū)發(fā)現(xiàn)的目標(biāo)是利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息或者網(wǎng)絡(luò)節(jié)點的屬性信息，從復(fù)雜的網(wǎng)絡(luò)中獲得模塊化的社區(qū)結(jié)構(gòu).社區(qū)發(fā)現(xiàn)旨在探測復(fù)雜社交網(wǎng)絡(luò)中具有共性特征或緊密關(guān)系的群體，例如有相同的愛好、屬于同一個研究領(lǐng)域等.目前它在社會學(xué)、生物醫(yī)學(xué)和計算機科學(xué)等領(lǐng)域都有廣泛應(yīng)用[1].

社區(qū)發(fā)現(xiàn)研究已有眾多工作，主要方法有：1)基于模塊度優(yōu)化的方法，主要思想是優(yōu)化模塊度Q值[2].如Newman等人[3]提出的GN算法，它雖然結(jié)果較為精確但是計算復(fù)雜度太高.2)基于譜分析的社區(qū)發(fā)現(xiàn)算法，例如Shi等人[4]提出的方法結(jié)合一種經(jīng)典的計算特征值的方法來進(jìn)行局部社區(qū)發(fā)現(xiàn).這類算法多通過將節(jié)點對應(yīng)的矩陣特征分量視為空間坐標(biāo)，從而可將網(wǎng)絡(luò)節(jié)點映射到多維向量空間，再采用傳統(tǒng)的聚類算法將它們聚集成社團.但由于需要計算矩陣的特征值，通常計算開銷很大.3)基于標(biāo)簽傳播的算法(label propagation algorithm, LPA)[5-6]，這類算法時間復(fù)雜度低、收斂速度快，但易受隨機游走的影響，劃分結(jié)果不穩(wěn)定.4)基于聚類的社區(qū)發(fā)現(xiàn)方法，它的基本思想是在網(wǎng)絡(luò)中增加或是刪除邊[7].以上這些硬劃分方法都有一個前提條件，就是要保證社區(qū)是易分離的，每個元素都可被劃分到某個社區(qū).然而現(xiàn)實中復(fù)雜網(wǎng)絡(luò)存在大量不確定因素，如數(shù)據(jù)含有噪聲、節(jié)點屬性不完備等，這也導(dǎo)致一些節(jié)點屬于多個社區(qū)形成重疊社區(qū)[8-9]，使用硬劃分可能會造成劃分沖突現(xiàn)象.如何利用這些不確定性信息挖掘更加精確的社區(qū)結(jié)構(gòu)成為一大挑戰(zhàn).

針對社區(qū)邊界不確定社區(qū)漂移的情況，張澤華等人[10]提出了基于鄰域粗糙化的社區(qū)局部擴張方法,通過給出的結(jié)構(gòu)穩(wěn)定性度量進(jìn)行局部擴張生成重疊社區(qū).本文則進(jìn)一步考慮融合多源信息解決不確定網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題.由于社區(qū)發(fā)現(xiàn)的結(jié)果很大程度會受到節(jié)點間距離測度的影響，對于復(fù)雜空間中分布的數(shù)據(jù)使用傳統(tǒng)的距離測度方法難以取得較好的效果.為了得到良好的社區(qū)發(fā)現(xiàn)結(jié)果，節(jié)點對之間的相似性度量起重要的作用.直觀認(rèn)知若2個節(jié)點相似，則很可能會有共同或類似的鄰居節(jié)點.而本文采用網(wǎng)絡(luò)嵌入方法獲得的節(jié)點表示有效融合了網(wǎng)絡(luò)的結(jié)構(gòu)和屬性信息，可以更好地描述節(jié)點結(jié)構(gòu)和節(jié)點間的相似性.但由于現(xiàn)實不確定性的廣泛存在，噪聲數(shù)據(jù)、節(jié)點屬性或結(jié)構(gòu)不完整，均會導(dǎo)致難以進(jìn)行社區(qū)發(fā)現(xiàn)或是得到的社區(qū)結(jié)構(gòu)不準(zhǔn)確.

因此，本文提出了粗糙?；木W(wǎng)絡(luò)嵌入(network embedding based on rough granulation, RGNE)方法進(jìn)行社區(qū)發(fā)現(xiàn).首先，使用網(wǎng)絡(luò)嵌入將網(wǎng)絡(luò)節(jié)點映射到一個低維連續(xù)的特征向量空間，同時還能保持網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點內(nèi)容信息，這樣考慮到了多層次的信息以便于對社區(qū)結(jié)構(gòu)進(jìn)行更有意義的理解.然后，結(jié)合粗糙?；姆椒▉硖幚砩鐓^(qū)中不確定性區(qū)域.最后生成重疊社區(qū).

本文的主要貢獻(xiàn)包括3個方面：

1) 提出了融合多源信息解決不確定網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方法RGNE，該方法采用網(wǎng)絡(luò)嵌入方法來表示節(jié)點，同時考慮了網(wǎng)絡(luò)拓?fù)浜凸?jié)點屬性等多種信息.

2) 為了解決含有不確定信息的重疊社區(qū)發(fā)現(xiàn)問題，通過將傳統(tǒng)的聚類方法與粗糙粒化方法結(jié)合來準(zhǔn)確地處理網(wǎng)絡(luò)不確定區(qū)域.

3) 在公開數(shù)據(jù)集上與傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法相比，RGNE方法的有效性明顯提升，并且對主要參數(shù)進(jìn)行討論；在人工數(shù)據(jù)集上本文算法顯示出分析較大規(guī)模網(wǎng)絡(luò)的優(yōu)勢.

1 相關(guān)工作

1.1 網(wǎng)絡(luò)嵌入

復(fù)雜的信息網(wǎng)絡(luò)可以看做是由頂點和邊(鏈接)構(gòu)成的有向或是無向圖，其中可能包含數(shù)十億的頂點和邊，在這樣的網(wǎng)絡(luò)上進(jìn)行推理和分析會非常困難.因此合理地對網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)變得尤為重要.網(wǎng)絡(luò)嵌入方法(network embedding)[11]通過將網(wǎng)絡(luò)節(jié)點映射到一個連續(xù)低維的特征空間中，得到的節(jié)點表示有利于后續(xù)的機器學(xué)習(xí)任務(wù)如社區(qū)發(fā)現(xiàn)、分類、鏈路預(yù)測、可視化等[12].近年來網(wǎng)絡(luò)嵌入的研究如火如荼.早期的降維算法SVD(singular value decomposition)[13]是將所定義的矩陣壓縮為一個較小的矩陣，但是這樣的方法只能用于線性結(jié)構(gòu)的數(shù)據(jù)；后來受到深度學(xué)習(xí)的啟發(fā)，基于詞向量模型的表示學(xué)習(xí)算法相繼被提出.最有代表性的是Perozzi等人[14]提出DeepWalk算法，該算法采用SkipGram模型[15]來學(xué)習(xí)節(jié)點嵌入，克服了網(wǎng)絡(luò)稀疏性問題；由于DeepWalk只適用于無權(quán)網(wǎng)絡(luò)，Tang等人[16]提出適用于多種類型網(wǎng)絡(luò)的LINE模型，通過一階相似性和二階相似性來捕捉網(wǎng)絡(luò)局部和全局結(jié)構(gòu)；Le等人[17]提出了一種半監(jiān)督的模型Doc2Vec，該模型利用了豐富的文本信息來對詞向量和文檔向量建模，對文本信息豐富的網(wǎng)絡(luò)具有較好的效果.然而，這些基于DeepWalk的改進(jìn)模型或是只利用了網(wǎng)絡(luò)的結(jié)構(gòu)信息，或是只利用了屬性信息，無法全面地表示整個網(wǎng)絡(luò).所以，Pan等人[18]提出了將DeepWalk和Doc2Vec結(jié)合的TriDNR模型，該模型使用網(wǎng)絡(luò)結(jié)構(gòu)信息、節(jié)點內(nèi)容信息和標(biāo)簽信息來對節(jié)點進(jìn)行表示.為了捕獲高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)，Wang等人[19]提出了一種半監(jiān)督的深度模型SDNE，該模型通過一組非線性函數(shù)來優(yōu)化一階相似性和二階相似性，能將數(shù)據(jù)映射到高度非線性的空間.

從上述方法看來，現(xiàn)有網(wǎng)絡(luò)嵌入方法多僅利用單一的信息，但是結(jié)合多種信息源對網(wǎng)絡(luò)能有更加精準(zhǔn)的描述，所以本文核心工作就是利用多源信息對網(wǎng)絡(luò)節(jié)點進(jìn)行建模.

1.2 粗糙集理論

1982年由波蘭數(shù)學(xué)家Pawlak[20]提出的粗糙集理論是粒計算的一大支撐理論.它將概念粒子用集合來表示，不同粒度的粒子可視為對集合的劃分.作為一種被廣泛使用的智能計算方法，粗糙集理論能夠很好地處理不確定性問題，目前已經(jīng)被廣泛應(yīng)用到分類決策、知識發(fā)現(xiàn)、人工智能等領(lǐng)域[21-25].

人類認(rèn)識事物的過程就是對事物的理解從不確定到確定的過程，不確定是客觀事物在發(fā)展過程中表現(xiàn)出的隨機性和模糊性等基本特征[26].從粗糙集理論看，在某種信息粒度層面上，確定性和不確定性存在相互轉(zhuǎn)化的關(guān)系，而且在不確定現(xiàn)象中還隱藏著一些重要的規(guī)律.所以研究如何表示不確定問題并從中獲得某些確定的規(guī)律，并且通過計算機建立模型來模擬認(rèn)知過程尤為重要.由于粗糙集可以有效處理信息不完備的情況，所以本文選擇用它來發(fā)掘不確定性數(shù)據(jù)中隱藏的相關(guān)性，獲得不確定知識的表達(dá).有關(guān)粗糙集的一些基本定義為：

定義1.等價類.設(shè)W是非空集合，R是等價關(guān)系.對于w∈W,節(jié)點w的R等價類定義為[20]

[w]R={x|x∈W,(w,x)∈R}，

(1)

(2)

W/R={[w1]R,[w2]R,…,[wN]R},

(3)

其中，N是等價類個數(shù)，且當(dāng)i≠1時，[wi]R∩[wj]R=?，W/R是集合W的等價劃分.

定義2.對于集合O?W的上近似集U(O)、下近似集L(O)和邊界域B(O)的定義為[20]

U(O)={w|w?W,[w]R∩O≠?}，

(4)

L(O)={w|w?W,[w]R?O}，

(5)

B(O)=U(O)-L(O),

(6)

顯然，它們有??L(O)?O?U(O)的關(guān)系.

2 粗糙粒化的網(wǎng)絡(luò)嵌入社區(qū)發(fā)現(xiàn)方法

粗糙粒化的網(wǎng)絡(luò)嵌入社區(qū)發(fā)現(xiàn)方法RGNE的主要思想是先通過隨機游走得到網(wǎng)絡(luò)G(無向無權(quán))的結(jié)構(gòu)信息和屬性信息，然后結(jié)合這2部分信息得到每個節(jié)點的低維向量表示；根據(jù)粗糙集理論處理不確定區(qū)域，將社區(qū)劃分為上近似集區(qū)域和下近似集區(qū)域，再通過定義的距離度量將節(jié)點劃分到近似集中，迭代至收斂得到最后的社區(qū)發(fā)現(xiàn)結(jié)果，方法主要步驟如圖1所示.

Fig.1 The schematic illustration of RGNE圖1 RGNE方法示意圖

2.1 獲得節(jié)點表示

網(wǎng)絡(luò)嵌入的目的是將節(jié)點嵌入到低維的空間中，而且能夠保留節(jié)點之間的關(guān)系，可以通過局部信息或是全局信息來捕獲節(jié)點間的關(guān)系.節(jié)點相對于其他節(jié)點的相似性稱之為上下文信息，從網(wǎng)絡(luò)結(jié)構(gòu)信息獲得的上下文稱為結(jié)構(gòu)上下文，從節(jié)點屬性信息而來的稱為屬性上下文.在網(wǎng)絡(luò)嵌入的階段主要包括3個步驟：網(wǎng)絡(luò)生成、隨機游走和學(xué)習(xí)節(jié)點表示，如算法1所示：

算法1.網(wǎng)絡(luò)嵌入算法.

輸入：網(wǎng)絡(luò)G=(V,E)的鄰接表；

參數(shù)：步長ηs和ηa、步數(shù)φs和φa、窗口大小t、嵌入維度D；

輸出：節(jié)點的向量表示Ω、出現(xiàn)頻率最多的前K個節(jié)點.

步驟1.從G中獲得結(jié)構(gòu)圖Gs和屬性圖Ga.

步驟2.對于V∈Vs∪Va，初始化所有節(jié)點向量Ω(V).

步驟3.在結(jié)構(gòu)圖上進(jìn)行隨機游走，

Ws=RandomWalk(Gs,Vs,ηs,φs).

步驟4.在屬性圖上進(jìn)行隨機游走，

Wa=RandomWalk(Ga,Va,ηa,φa).

步驟5.Ω=SkipGram(Ws,Wa,t)結(jié)合式(7)～(9)學(xué)習(xí)節(jié)點的最終嵌入表示.

步驟6.返回節(jié)點表示Ω.

2.1.1 網(wǎng)絡(luò)生成

在網(wǎng)絡(luò)生成階段，將原始的網(wǎng)絡(luò)G=(V,E)分為結(jié)構(gòu)圖Gs=(Vs,E)和屬性圖Ga=(Va,A,Ea).其中Ga是一個二部圖，結(jié)構(gòu)節(jié)點Vs∈V，內(nèi)容節(jié)點Va∈V，A是屬性節(jié)點，Ea是屬性節(jié)點和內(nèi)容節(jié)點的邊.內(nèi)容節(jié)點之間的路徑包含屬性節(jié)點，形成了屬性上下文.

2.1.2 隨機游走

在隨機游走階段，通過短隨機游走同時獲得結(jié)構(gòu)上下文和屬性上下文，短隨機游走已經(jīng)被證明可以獲得較高相似度的節(jié)點上下文[14].在Gs上的隨機游走捕獲了結(jié)構(gòu)上下文信息，對于每個節(jié)點都進(jìn)行步長為ηs的φs步隨機游走并構(gòu)建節(jié)點庫S，si為隨機游走序列(節(jié)點庫S)中的第i個節(jié)點；在Ga上的隨機游走，更關(guān)注內(nèi)容節(jié)點共同出現(xiàn)的頻率，因此忽略了屬性節(jié)點A，而且根據(jù)經(jīng)驗所得，相似的節(jié)點會有更大的概率在隨機游走中一起出現(xiàn)，同理，對每個內(nèi)容節(jié)點都進(jìn)行步長為ηa的φa步隨機游走并建立節(jié)點庫C，cj為隨機游走序列(節(jié)點庫C)中的第j個節(jié)點.

2.1.3 節(jié)點嵌入學(xué)習(xí)

在節(jié)點嵌入階段，借助語言建模Word2vec[27]中的Skip-Gram模型來學(xué)習(xí)節(jié)點的向量表示.由于Skip-Gram是用單詞預(yù)測上下文的模型，通過將窗口內(nèi)單詞之間的共現(xiàn)概率最大化來學(xué)習(xí)向量表示.所以借鑒這個模型，將網(wǎng)絡(luò)節(jié)點當(dāng)作語言模型中的單詞，隨機游走得到的節(jié)點序列當(dāng)作語言模型中的句子作為Skip-Gram的輸入，輸出的可以是結(jié)構(gòu)節(jié)點、屬性節(jié)點亦或是兩者的共同節(jié)點.

利用結(jié)構(gòu)上下文的嵌入學(xué)習(xí)過程為

(7)

其中，m≠i，t為窗口大小，p(sm|si)表示當(dāng)中心節(jié)點是si時第m個節(jié)點在上下文中出現(xiàn)的概率，它衡量了節(jié)點間的相似度.

利用屬性上下文的嵌入學(xué)習(xí)過程為

(8)

其中，n≠j，p(cn|cj)表示當(dāng)中心節(jié)點是cj時第n個節(jié)點在上下文中出現(xiàn)的概率.

給定一個目標(biāo)節(jié)點，假設(shè)節(jié)點的上下文節(jié)點相互獨立[11].本文的目標(biāo)是最大化結(jié)構(gòu)上下文和屬性上下文的概率，所以目標(biāo)函數(shù)為

L=Ls+Lc.

(9)

計算目標(biāo)函數(shù)的難點在于計算p(sm|si)和p(cn|cj)，本文選擇使用Softmax來近似地計算這2個條件概率:

(10)

其中，γ(·)表示上下文節(jié)點，Ω(·)表示目標(biāo)節(jié)點.同理可以計算出p(cn|cj).

2.2 粗糙?；纳鐓^(qū)發(fā)現(xiàn)

傳統(tǒng)的社區(qū)發(fā)現(xiàn)方法一般將社區(qū)內(nèi)的所有節(jié)點“一視同仁”.對于一些處在不確定性區(qū)域的節(jié)點，如果使用硬劃分方法很可能會產(chǎn)生局部沖突.如圖2所示，節(jié)點被劃分為2個社區(qū)Z1和Z2，節(jié)點4和9分別是2個社區(qū)的中心，對于節(jié)點6根據(jù)現(xiàn)有的認(rèn)識無法準(zhǔn)確判斷出它屬于哪一個社區(qū).所以本文提出了結(jié)合粗糙集理論的社區(qū)發(fā)現(xiàn)算法來解決這樣的問題，該方法將社區(qū)Z分為上近似社區(qū)U(Z)和下近似社區(qū)L(Z)，其中U(Z)包括核心節(jié)點和邊緣節(jié)點，L(Z)只包含核心節(jié)點，而社區(qū)的邊界B(Z)包含屬于U(Z)不屬于L(Z)的節(jié)點(如圖3所示)，這樣就可以描述社區(qū)的不確定性區(qū)域.算法的主要步驟由算法2給出.

Fig.2 Community drift圖2 社區(qū)漂移

Fig.3 Rough community description圖3 粗糙社區(qū)描述

2.2.1 社區(qū)中心

社區(qū)發(fā)現(xiàn)任務(wù)中準(zhǔn)確找出中心節(jié)點Z*是一個非常重要的任務(wù)，找出正確的中心節(jié)點對社區(qū)發(fā)現(xiàn)來說事半功倍，錯誤的中心節(jié)點會導(dǎo)致算法收斂速度降低，甚至?xí)玫藉e誤的社區(qū)結(jié)果.在對社區(qū)進(jìn)行初始化時，先將網(wǎng)絡(luò)嵌后獲得的前K個出現(xiàn)頻率最高的節(jié)點作為初始中心節(jié)點，由于K值需要預(yù)先指定，本文將在實驗部分討論K值對最后的社區(qū)發(fā)現(xiàn)效果產(chǎn)生的影響.

(11)

其中，|L(Zk)|表示社區(qū)Zk下近似集包含的節(jié)點數(shù)，|B(Zk)|表示邊界域的節(jié)點數(shù).θL和θB分別是對應(yīng)近似域的加權(quán)參數(shù)，且θL+θB=1.

認(rèn)識來源于實踐，反過來又為實踐服務(wù)。高效節(jié)水灌溉一時的挫折或失敗，是人們在實踐中還沒有充分認(rèn)識到其技術(shù)和條件適應(yīng)性的結(jié)果，這些問題會隨著人們的認(rèn)識水平不斷提高而得到解決，因此必須要勇于實踐，不斷從實踐中提高認(rèn)識水平，又反過來進(jìn)一步指導(dǎo)新的灌溉實踐。

2.2.2 社區(qū)劃分

通過判斷節(jié)點與社區(qū)中心節(jié)點的關(guān)系，可以得出節(jié)點與社區(qū)的關(guān)系，從而將其劃分到社區(qū)的近似集中.根據(jù)粗糙集理論，節(jié)點與社區(qū)的近似集之間的關(guān)系滿足3個性質(zhì)[28]：1)一個節(jié)點只能屬于一個社區(qū)的下近似集；2)如果節(jié)點屬于一個社區(qū)Z的下近似集，那么這個節(jié)點也同樣屬于社區(qū)Z的上近似集；3)如果節(jié)點不屬于任何社區(qū)的下近似集，那么它一定屬于2個或更多社區(qū)的上近似集.

首先，對每個節(jié)點向量分別計算它們與各個社區(qū)中心節(jié)點的距離d(v,Z*)和距離最近中心節(jié)點的最小距離dmin.對于節(jié)點與社區(qū)中心節(jié)點距離的計算用到了歐氏距離，歐氏距離也稱歐幾里得距離，是最常見的距離度量，衡量的是多維空間中2個點之間的絕對距離.關(guān)于節(jié)點與第k個社區(qū)的中心節(jié)點距離計算為

(12)

其中，N為節(jié)點個數(shù).用d(v,Z*i)/d(v,Z*j)來表示節(jié)點和2個社區(qū)的關(guān)系，其中1≤i,j≤K，且i≠j.然后通過節(jié)點與社區(qū)近似集之間的3條性質(zhì)，得出節(jié)點與各個社區(qū)的關(guān)系.引入?yún)?shù)δ，0<δ≤1，當(dāng)dmin/d(v,Z*)≥δ時，表示該節(jié)點屬于對應(yīng)中心節(jié)點和距離最近社區(qū)的上近似集中，否則節(jié)點將屬于距離最近社區(qū)的上下近似集中.值得注意的是，參數(shù)δ的大小表示了社區(qū)邊界域的大小，隨著δ的減小，邊界區(qū)域?qū)嗟墓?jié)點.實驗中設(shè)置δ=0.8.

算法2.社區(qū)發(fā)現(xiàn)算法.

輸入：網(wǎng)絡(luò)節(jié)點向量表示Ω、社區(qū)個數(shù)K；

輸出：社區(qū)集合Z={Z1,Z2,…,ZK}.

步驟1.將算法1得出的出現(xiàn)頻率最多的前K個節(jié)點作為初始中心節(jié)點；

步驟3.根據(jù)dmin/d(v,Z*)≥δ，計算節(jié)點與社區(qū)中心的距離，并將其劃分到相應(yīng)的近似集中；

步驟4.根據(jù)社區(qū)近似集更新中心節(jié)點，

步驟5.返回社區(qū)結(jié)果Z.

3 實驗與分析

在不同規(guī)模的數(shù)據(jù)集上分別與4個適用于社區(qū)發(fā)現(xiàn)的算法進(jìn)行對比，驗證算法RGNE的有效性并且對參數(shù)設(shè)置進(jìn)行討論.又在人工數(shù)據(jù)集上分析網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)度分布對社區(qū)劃分結(jié)果的影響.

3.1 評測數(shù)據(jù)集

本文使用公開數(shù)據(jù)集中的DBLP數(shù)據(jù)集是從4個研究領(lǐng)域的34個會議中提取的參考書目數(shù)據(jù).將數(shù)據(jù)集中的作者作為節(jié)點，選取了60 744個節(jié)點，論文標(biāo)題作為節(jié)點內(nèi)容，將數(shù)據(jù)集中出現(xiàn)頻率3次以上的詞作為節(jié)點屬性.另外2個公開數(shù)據(jù)集是Zachary Karate Club和College Football Network.其中，Zachary Karate Club是一個空手道俱樂部的成員關(guān)系網(wǎng)絡(luò)，共有34個成員和以管理員和教練為中心的2個小組；而College Football Network是2000年美國大學(xué)足球橄欖球聯(lián)盟比賽網(wǎng)絡(luò)，115支隊伍被分為12個聯(lián)盟進(jìn)行比賽.數(shù)據(jù)基本情況如表1所示：

Table 1 Datasets Statistics表1 測試數(shù)據(jù)集

此外，使用LFR合成人工數(shù)據(jù)集[29]，用于有向、加權(quán)或重疊社區(qū)實驗評測.LFR數(shù)據(jù)集可通過參數(shù)控制人工社區(qū)的度分布和社區(qū)大小，通過增加網(wǎng)絡(luò)節(jié)點個數(shù)和改變網(wǎng)絡(luò)度分布來分別分析網(wǎng)絡(luò)規(guī)模和社區(qū)邊比率大小對本文算法的效果影響.其中，涉及到的控制參數(shù)有：網(wǎng)絡(luò)規(guī)模N、混合參數(shù)λ(社區(qū)內(nèi)的邊與其他社區(qū)邊的平均比率).

3.2 實驗設(shè)置

在節(jié)點表示階段進(jìn)行的隨機游走過程中，設(shè)置步數(shù)φs和φa分別為10，步長ηs和ηa分別為80，Skip-Gram模型的窗口大小t=5，節(jié)點表示的維度D=128.在社區(qū)發(fā)現(xiàn)的階段，將下近似集和邊界域的權(quán)重設(shè)置為θL=θB=0.5.

3.3 評價指標(biāo)和對比方法

本文使用評價社區(qū)發(fā)現(xiàn)算法效果常用的標(biāo)準(zhǔn)化互信息(normalized mutual information,NMI)[30]和模塊度Q值作為標(biāo)準(zhǔn)，分別為式(13)(14).

給定2個劃分結(jié)果X和Y，M為混淆矩陣，Mij是屬于結(jié)果X的社區(qū)i和結(jié)果Y的社區(qū)j的節(jié)點數(shù).

(13)

其中，MX是X的社區(qū)數(shù)，MY是Y的社區(qū)數(shù)，N為節(jié)點數(shù).NMI用來衡量2個結(jié)果的相似度，取值范圍是[0，1]，數(shù)值越大代表社區(qū)發(fā)現(xiàn)的結(jié)果越好.

(14)

其中，i為所屬社區(qū)號，K是社區(qū)總數(shù)，li是社區(qū)i的總邊數(shù)，di是社區(qū)i節(jié)點的總度數(shù)，m是整個網(wǎng)絡(luò)的總邊數(shù).Q值越大說明社區(qū)劃分效果越好，取值范圍是[-0.5,1]，當(dāng)Q值在0.3～0.7之間時，說明社區(qū)發(fā)現(xiàn)的效果良好.

通過與4個社區(qū)發(fā)現(xiàn)的典型算法對比，對本文提出的RGNE算法性能進(jìn)行評估.

1) LPA[5].基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法，該算法為所有節(jié)點指定一個標(biāo)簽，通過標(biāo)簽傳遞和更新.算法計算復(fù)雜度較低，易于快速收斂.

2) GN[3].算法定義一條邊的介數(shù)為網(wǎng)絡(luò)中所有節(jié)點之間的最短路徑中通過這條邊的數(shù)量，而介數(shù)高的邊要比介數(shù)低的邊更可能是社區(qū)之間的邊.每次都刪除網(wǎng)絡(luò)中介數(shù)最大的邊，直至網(wǎng)絡(luò)中的所有邊都被刪除.

3) Louvain[31].一個基于多層次優(yōu)化的啟發(fā)式算法.該算法的主要思想是將每個節(jié)點劃分到相鄰節(jié)點的社區(qū)中使得模塊度Q值不斷增大，直到Q值不再變化，此時再根據(jù)生成的社區(qū)結(jié)構(gòu)重構(gòu)網(wǎng)絡(luò).

4) DeepWalk[14].利用網(wǎng)絡(luò)結(jié)構(gòu)中隨機游走序列的信息來代替語言建模中的句子，將節(jié)點向量映射到一個低維稠密的空間中.對節(jié)點序列用SkipGram模型進(jìn)行網(wǎng)絡(luò)節(jié)點的表示學(xué)習(xí)與預(yù)測.Node2Vec[32]則采用了不同的隨機游走策略，通過定義參數(shù)p和q，同時考慮局部和宏觀的信息分別進(jìn)行廣度優(yōu)先和深度優(yōu)先搜索，其結(jié)果較依賴于參數(shù)的優(yōu)化過程.

3.4 實驗結(jié)果分析

在3.1節(jié)中公開數(shù)據(jù)集上進(jìn)行實驗，并與其他4種算法作比較驗證RGNE算法的有效性，所有方法均采用網(wǎng)絡(luò)嵌入方法得到節(jié)點的表示.由圖4和圖5可得，LPA的較差，因為該算法比較依賴初始中心節(jié)點的選取，隨機性很大.算法GN表現(xiàn)良好，但是由于要遍歷網(wǎng)絡(luò)中所有的邊，所以時間復(fù)雜度較高，只適用于小規(guī)模網(wǎng)絡(luò).Louvain采用層次凝聚的方式對網(wǎng)絡(luò)進(jìn)行聚類，它的優(yōu)點在于能夠體現(xiàn)網(wǎng)絡(luò)的不同粒度的層次結(jié)構(gòu)，易于理解和計算較便捷.但值得注意的是，不同節(jié)點上的遍歷順序?qū)Y(jié)果有一定擾動，在一定程度上會影響計算時間.此外，由于Q函數(shù)的約束，GN和Louvain算法都傾向于發(fā)現(xiàn)規(guī)模相似的網(wǎng)絡(luò)，對稀疏網(wǎng)絡(luò)效果一般.DeepWalk略優(yōu)于2種傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法，但它只利用了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)忽略了屬性信息，所以節(jié)點表示不夠全面.

Fig.4 Comparison of Q on three datasets圖4 3個數(shù)據(jù)集下各算法的Q值對比

Fig.5 Comparison of NMI on three datasets圖5 3個數(shù)據(jù)集下各算法的NMI對比

綜上所述，RGNE算法效果普遍優(yōu)于其他算法，在DBLP這樣的大規(guī)模數(shù)據(jù)集上更加突出.相較于傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法，RGNE在處理較為稀疏的網(wǎng)絡(luò)方面具有更大的優(yōu)勢；相較于同樣是網(wǎng)絡(luò)嵌入方法的DeepWalk來說，RGNE能同時利用節(jié)點的結(jié)構(gòu)信息和屬性信息，所以社區(qū)發(fā)現(xiàn)效果更好.而且利用粗糙?；纳鐓^(qū)描述對網(wǎng)絡(luò)不確定區(qū)域的節(jié)點處理更符合實際社區(qū)分布.

Fig.6 Impact of network size on community detection圖6 網(wǎng)絡(luò)規(guī)模對社區(qū)發(fā)現(xiàn)的影響

在人工數(shù)據(jù)集上，通過增加網(wǎng)絡(luò)節(jié)點和邊的數(shù)量來生成更為復(fù)雜的網(wǎng)絡(luò)，以此來驗證各個算法的可擴展性.設(shè)置混合參數(shù)λ為實驗最優(yōu)值0.3，將網(wǎng)絡(luò)規(guī)模由2.5萬個節(jié)點遞增到10萬個節(jié)點.圖6則表明，隨著網(wǎng)絡(luò)規(guī)模的增大，各種算法的NMI值出現(xiàn)了不同程度的下降，網(wǎng)絡(luò)嵌入方法的性能顯然較優(yōu)，其他的算法由于計算復(fù)雜度較高，網(wǎng)絡(luò)規(guī)模倍增時算法受影響較大，RGNE算法表現(xiàn)出良好的穩(wěn)定性.

繼續(xù)在人工數(shù)據(jù)集上進(jìn)行實驗，首先固定網(wǎng)絡(luò)大小為1 000個節(jié)點，然后改變混合參數(shù)λ的大小，λ∈[0，1].圖7顯示了在不同λ值下各算法的NMI值變化.所有算法均在λ增加的情況下，即社區(qū)結(jié)構(gòu)不清晰時NMI值逐漸降低.對于較小的λ，所有算法的差別不是很大，但是當(dāng)λ≥0.3時，RGNE算法顯示出優(yōu)勢，很明顯地曲線下降趨勢緩和，而其他算法在λ增加至某一值時NMI值降為0，原因是本文的方法可以有效融合網(wǎng)絡(luò)的結(jié)構(gòu)信息和屬性信息而且同時能正確處理不確定信息.

Fig.7 Effect of λ on NMI圖7 混合參數(shù)λ對NMI的影響

3.5 參數(shù)討論

由于預(yù)先指定了社區(qū)中心個數(shù)K，確定合適的K值會對最后的社區(qū)發(fā)現(xiàn)效果產(chǎn)生很大影響，采用手肘法來確定K值，評估指標(biāo)是誤差平方和E[33].它的核心思想是：隨著劃分?jǐn)?shù)K值的增大，劃分變得更加精細(xì)，每個社區(qū)內(nèi)的聚合度增加，E值會減小；當(dāng)K小于真實劃分?jǐn)?shù)時，K值增大會使每個社區(qū)內(nèi)聚合度增加，所以E的降幅增大；當(dāng)K值達(dá)到真實劃分?jǐn)?shù)后，再增大K值聚合度不會有很大改變，所以E降幅減緩趨于平緩.

(15)

其中，v是社區(qū)Zk中選取的樣本節(jié)點，Z*是Zk的中心，K越大，E越小，樣本的聚合程度越高.在Zachary和Football這2個數(shù)據(jù)集上對K值進(jìn)行討論.

由圖8可得，在達(dá)到真實的社區(qū)數(shù)前，E的降幅較大，因為劃分得更精細(xì)會使社區(qū)內(nèi)的聚合度增加；2個數(shù)據(jù)集分別在K=2和K=12時到達(dá)真實劃分?jǐn)?shù)，之后曲線的降幅驟減，此時再增加K值的回報很小.

Fig.8 K analysis on two datasets圖8 在2種數(shù)據(jù)集上的K值分析

此外，社區(qū)發(fā)現(xiàn)算法中的參數(shù)δ對社區(qū)發(fā)現(xiàn)結(jié)果會有一定的影響，為了更好地了解造成的影響，本文在DBLP數(shù)據(jù)集上進(jìn)行參數(shù)分析.由于δ的值代表社區(qū)邊界區(qū)域的大小，隨著δ的減小，邊界區(qū)域?qū)嗟墓?jié)點，此時社區(qū)發(fā)現(xiàn)的難度也會增大.選擇在區(qū)間[0.5，1.0]內(nèi)討論參數(shù)影響.

由圖9可得，在參數(shù)δ=0.8時5種算法均能取得最好的效果.這是因為當(dāng)δ過小或是過大，即社區(qū)邊界域太大或太小都不利于社區(qū)發(fā)現(xiàn).當(dāng)邊界域較大時社區(qū)包含更多不確定性的節(jié)點，社區(qū)發(fā)現(xiàn)的困難增大，此時結(jié)合粗糙集理論的RGNE算法明顯優(yōu)于其他算法；當(dāng)邊界域較小時，各個社區(qū)之間的邊界模糊，社區(qū)結(jié)構(gòu)不清晰同樣難以得到良好的結(jié)果.

Fig.9 Effect of δ on Q圖9 參數(shù)δ對Q值影響

4 結(jié) 論

由于現(xiàn)實中復(fù)雜網(wǎng)絡(luò)存在不確定性數(shù)據(jù)，使用傳統(tǒng)的硬劃分方法可能會造成劃分沖突.而這些不易劃分的元素在社區(qū)發(fā)現(xiàn)中是不可忽視的，利用這些不確定性元素可以挖掘出更加精確的社區(qū)結(jié)構(gòu).本文提出的RGNE算法先是通過網(wǎng)絡(luò)嵌入獲得融合結(jié)構(gòu)信息和屬性信息的節(jié)點表示，并且可以將相似的節(jié)點映射到距離相近的低維連續(xù)的向量空間.然后結(jié)合粗糙集理論來處理不確定性信息進(jìn)行社區(qū)發(fā)現(xiàn)，從而得到更為精準(zhǔn)的社區(qū)發(fā)現(xiàn)結(jié)果.目前本文的研究是在中小型規(guī)模的網(wǎng)絡(luò)上進(jìn)行，在未來的工作中可以著眼于大規(guī)模網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn).