陳 卓,姜 鵬,袁璽明

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院,青島 266061)

現(xiàn)實世界中的很多系統(tǒng)都可以被抽象為復(fù)雜網(wǎng)絡(luò),如社交網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、生物網(wǎng)絡(luò),這些網(wǎng)絡(luò)都具有一種普遍的特性——社區(qū)結(jié)構(gòu).在不同類型的網(wǎng)絡(luò)中,社區(qū)有著不同的含義,但是所有社區(qū)內(nèi)部節(jié)點間的聯(lián)系總是比不同社區(qū)節(jié)點間的聯(lián)系密切,準(zhǔn)確地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)是在中觀層面上理解復(fù)雜網(wǎng)絡(luò)進而研究復(fù)雜系統(tǒng)的有效途徑.

社區(qū)發(fā)現(xiàn)的研究歷史可以追溯到1927年,Rice 等基于投票模式的相似性發(fā)現(xiàn)小的政治團體中的社區(qū)[1].早期的研究工作大部分都圍繞非重疊社區(qū)發(fā)現(xiàn)展開,此類算法將復(fù)雜網(wǎng)絡(luò)劃分成若干個互不相連的社區(qū)結(jié)構(gòu)且一個節(jié)點只能隸屬于一個社區(qū)[2].然而,現(xiàn)實中網(wǎng)絡(luò)社區(qū)之間往往是相互重疊的,硬劃分的社區(qū)發(fā)現(xiàn)算法無法滿足需求,例如,在社交網(wǎng)絡(luò)中,如果每個社區(qū)代表擁有共同興趣愛好的用戶所組成的群體,則一個用戶可以擁有諸多興趣愛好而隸屬于多個社區(qū),顯然,重疊的社區(qū)結(jié)構(gòu)更能體現(xiàn)出復(fù)雜網(wǎng)絡(luò)的特性,進而幫助我們從中觀層面對復(fù)雜系統(tǒng)進行分析.

對復(fù)雜網(wǎng)絡(luò)中重疊社區(qū)的發(fā)現(xiàn)與研究也因此成為近年來新的研究熱點,而社區(qū)發(fā)現(xiàn)作為社區(qū)分析相關(guān)工作的前提,對于其他領(lǐng)域的研究有著重要影響.目前,重疊社區(qū)的發(fā)現(xiàn)結(jié)果可以被應(yīng)用于情感分析、個性化推薦、實體消歧和鏈接預(yù)測等領(lǐng)域的研究.

1 相關(guān)工作

近年來,學(xué)者們相繼提出大量能夠識別重疊社區(qū)的算法.Palla 等提出一種基于最大團的派系過濾算法CPM 來分析重疊的社區(qū)結(jié)構(gòu)[3],該算法易受k值影響,且以最大團為種子的方式計算復(fù)雜度較高.COPRA 算法[4]對基于標(biāo)簽傳播的非重疊社區(qū)發(fā)現(xiàn)算法進行改進,在標(biāo)簽后面附上節(jié)點對該標(biāo)簽的歸屬系數(shù),以便衡量該節(jié)點包含多個社區(qū)的信息比重,在迭代更新節(jié)點標(biāo)簽的過程中允許一個節(jié)點同時擁有多個標(biāo)簽,以發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū),該算法每次迭代的時間復(fù)雜度接近線性但穩(wěn)定度較差.基于鏈路的重疊社區(qū)發(fā)現(xiàn)算法首先對網(wǎng)絡(luò)的邊進行聚類,然后通過收集鏈路社區(qū)內(nèi)的所有連接的節(jié)點進行社區(qū)劃分,代表算法為LINK算法[5].在此基礎(chǔ)上,Li 等[6]提出一種基因表示模型,通過將鏈路社區(qū)映射成節(jié)點社區(qū)的方式,實現(xiàn)對重疊節(jié)點的發(fā)現(xiàn).基于局部社區(qū)優(yōu)化和擴展的方法則從局部社區(qū)出發(fā),基于優(yōu)化函數(shù)進行擴張,社區(qū)間的交叉部分則為重疊節(jié)點,代表算法為LFM 算法[7],除此之外,Su 等[8]提出利用隨機游走策略擴展優(yōu)化的方法.文獻[9]在此基礎(chǔ)上提出基于種子節(jié)點選擇的重疊社區(qū)發(fā)現(xiàn)算法,首先通過定義的影響力函數(shù)選取種子節(jié)點,然后通過吸引力函數(shù)以種子節(jié)點為核心進行擴展,發(fā)現(xiàn)種子所在的局部社區(qū)結(jié)構(gòu).其中,基于種子節(jié)點選擇和擴展的算法由于穩(wěn)定性好、效率高而成為主流的社區(qū)發(fā)現(xiàn)算法.Wang 等[10]提出一種基于結(jié)構(gòu)中心性的種子選擇算法,實現(xiàn)了一個高覆蓋率的樸實算法,提高了社區(qū)發(fā)現(xiàn)質(zhì)量,但算法不能很好地適用于大規(guī)模數(shù)據(jù)集.於志勇等提出的i-SEOCD 算法能夠高效地從種子節(jié)點出發(fā)進行局部擴展,最終發(fā)現(xiàn)穩(wěn)定的重疊社區(qū)[11],但是該算法在計算節(jié)點相似度時只考慮了局部網(wǎng)絡(luò),提高算法執(zhí)行效率的同時也犧牲了算法準(zhǔn)確性.

現(xiàn)有基于種子節(jié)點擴展的重疊社區(qū)發(fā)現(xiàn)算法雖然在穩(wěn)定性方面表現(xiàn)較好,但在衡量兩節(jié)點間關(guān)系時,往往將兩節(jié)點間是否有連邊作為唯一判別標(biāo)準(zhǔn),而只考慮狹小作用域范圍內(nèi)的局部信息的做法,雖然提升了社區(qū)發(fā)現(xiàn)的效率,但忽略了網(wǎng)絡(luò)中更大范圍內(nèi)節(jié)點和邊因素對社區(qū)發(fā)現(xiàn)過程的影響,使得算法在提升效率的同時往往以犧牲部分準(zhǔn)確性為代價.同時,現(xiàn)有算法在基于種子節(jié)點進行社區(qū)擴展的過程中,往往需要不斷地迭代計算現(xiàn)有社區(qū)與未劃分節(jié)點間的相似性關(guān)系,計算量大,不適合進行大規(guī)模網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn).

為了更好地解決以上問題,本文利用Node2Vec[12]算法對網(wǎng)絡(luò)結(jié)構(gòu)進行學(xué)習(xí),通過控制在游走產(chǎn)生節(jié)點序列過程中對深度優(yōu)先和廣度優(yōu)先的趨向,將更大范圍內(nèi)的拓撲結(jié)構(gòu)信息體現(xiàn)到節(jié)點因素中,提出了基于Node2Vec 的重疊社區(qū)發(fā)現(xiàn)算法,該算法能夠解決現(xiàn)有算法存在的以犧牲準(zhǔn)確性來提高效率和不適合大規(guī)模數(shù)據(jù)集的問題.

2 基于Node2Vec 的重疊社區(qū)發(fā)現(xiàn)算法

針對以Jaccard 相似度為指標(biāo)衡量節(jié)點間距離的方法所存在的局限性,本文采用網(wǎng)絡(luò)表示學(xué)習(xí)算法學(xué)習(xí)到網(wǎng)絡(luò)中每個節(jié)點的向量表示,針對傳統(tǒng)種子節(jié)點選擇方法穩(wěn)定性和魯棒性差的缺點,提出了新的種子節(jié)點選擇算法,并以此為基礎(chǔ)進行社區(qū)擴張和優(yōu)化.

2.1 Node2Vec 算法

Perozzi 等[13]提出了將Word2Vec 的思想用于圖節(jié)點表示學(xué)習(xí)的Deepwalk 算法,Node2Vec 在此的基礎(chǔ)上改變了隨機游走的序列生成方式,通過半監(jiān)督的方式學(xué)習(xí)p,q兩個超參數(shù)的值,控制游走對深度和廣度的趨向,其中p控制跳向前節(jié)點鄰居的概率,q控制跳向前節(jié)點非鄰居的概率,如圖1所示.

圖1 隨機游走過程圖

圖1中,q>1時,趨向于遍歷臨近t節(jié)點的x1節(jié)點,即趨向于BFS;p>1時,趨向于遍歷臨近t節(jié)點的x2或x3節(jié)點,即趨向于DFS.在確定要遍歷的鄰居節(jié)點之后,采用skip-gram 模型進行訓(xùn)練進而獲得節(jié)點的向量表示.

在進行種子節(jié)點發(fā)現(xiàn)前,首先利用Node2Vec 算法對網(wǎng)絡(luò)結(jié)構(gòu)進行學(xué)習(xí),在學(xué)習(xí)到網(wǎng)絡(luò)中每個節(jié)點的向量表示后,對于任意節(jié)點u和v,可利用算法內(nèi)置的相似度計算工具計算其在高維空間中的相似度sim(u,v),其取值范圍為0～1,通過該方式進一步計算網(wǎng)絡(luò)中任意節(jié)點之間的相似度,并用相似度矩陣An×n表示整個網(wǎng)絡(luò)中節(jié)點間的相似度信息,其中Auv表示節(jié)點u和v之間的相似度,進而可以用1?sim(u,v)來表示節(jié)點間的相異度.

2.2 種子節(jié)點選擇算法

通常,一個網(wǎng)絡(luò)可以用無向圖G=(V,E)表示,其中V表示圖中n個節(jié)點的集合,E表示圖中m條邊的集合.

在網(wǎng)絡(luò)中,節(jié)點u的鄰居集合N(u)定義如下:

節(jié)點u對節(jié)點v的影響力用F(u,v)表示如下:

其中,D(u)和D(v)分別表示節(jié)點u和v的度,sim(u,v)表示u,v節(jié)點的相似度,可通過Node2Vec 生成的節(jié)點向量計算得到,1?sim(u,v)表示為兩節(jié)點間的距離,距離越遠,u對v的影響力越小.

節(jié)點u的影響力值通過以下公式計算得到:

節(jié)點影響力的大小與其鄰居節(jié)點的數(shù)量、度數(shù)以及相異度有關(guān),影響力越大,節(jié)點越有機會成為種子節(jié)點.

在種子節(jié)點選擇算法中,首先根據(jù)節(jié)點的向量計算所有節(jié)點的影響力值,如果某節(jié)點的影響力值比其所有鄰居節(jié)點的影響力值都大,則將該節(jié)點加入到種子節(jié)點的集合中.算法1 中列出了種子節(jié)點選擇算法的偽代碼,其中2-4 行利用定義的節(jié)點影響力計算公式計算出每個幾點的影響力值,5-9 行將每個節(jié)點的影響力值與其所有鄰居的影響力值進行比較,若鄰居節(jié)點中沒有比當(dāng)前節(jié)點影響力值大的節(jié)點,則將該節(jié)點加入到種子節(jié)點集合中.

算法1.種子節(jié)點選擇算法輸入:無向圖;相似度矩陣.輸出:種子節(jié)點集合S.G=(V,E) An×n 1.S ←?2.for do 3.利用式(3)計算F(u)4.end for∈u∈V 5.for u V do?v∈N(u) F(u)≥F(v)6.if and S ←S ∪u 7.8.end if 9.end for 10.return S

2.3 社區(qū)擴展算法

針對現(xiàn)有算法在社區(qū)擴張過程中重復(fù)計算量大的問題,本文在得到分布均勻、影響力大的種子節(jié)點之后,充分利用前一階段計算所得的節(jié)點相似度矩陣,從每個種子節(jié)點出發(fā)進行社區(qū)擴展,首先,以集合中的每個種子節(jié)點為核心構(gòu)建社區(qū),若節(jié)點與種子節(jié)點的相似度大于閾值ε,則將該節(jié)點劃入該種子節(jié)點所屬的社區(qū),然后,對于尚未被劃分的節(jié)點,比較其與各個種子節(jié)點的相似度,選取與之最相似的種子節(jié)點,加入其所在社區(qū),最終完成社區(qū)的劃分.

算法2 中列出了社區(qū)擴展算法的偽代碼,2-4 行首先將所有節(jié)點標(biāo)記為false,5-13 行分別以每個種子節(jié)點為核心進行社區(qū)擴展,并將被劃分的節(jié)點標(biāo)記為true,此過程中以各節(jié)點為核心的社區(qū)獨立進行擴展,能夠很好地根據(jù)閾值 ε的大小控制重疊節(jié)點的規(guī)模,閾值ε越小,發(fā)現(xiàn)重疊節(jié)點的幾率越大,14-19 行將一輪劃分結(jié)束后沒有歸屬的節(jié)點分離出來,20-25 行則對標(biāo)記為false 的節(jié)點進行處理,選擇與之相似度最高的種子節(jié)點所在的社區(qū)作為其社區(qū)歸屬,最終經(jīng)過兩個階段的處理,得到最終的社區(qū).

算法2.社區(qū)擴展算法輸入:無向圖;相似度矩陣;種子集合S.輸出:社區(qū)結(jié)構(gòu)C.G=(V,E) An×n 1.C←?2.for do Label(u)=false u∈V 3.4.end for 5.for seed in S do CS ←?,CS ←CS ∪{seed}6.7.for and A[seed][u]≥ε u∈Vu?S 8.if 9.,10.end if 11.end for C←C∪CS CS ←CS ∪{U} Label(u)=true 12.13.end for R←?14.15.for node in V Label(node)=false 16.if 17.18.end if 19.end for R R←R∪{node}20.for v in 21.for seed in S 22.CS_num=argmax 23.end for CS ←CS ∪{v} Label(v)=true A[seed][v]24.,2.5 end for 26.return C

通常情況下,選擇合適的閾值 ε能夠使得大部分節(jié)點經(jīng)過第一階段的處理能夠劃入相應(yīng)的社區(qū),閾值 ε越小,需要進行第二階段處理的節(jié)點越少,但也會導(dǎo)致社區(qū)之間重疊度很高.本文在基于種子節(jié)點進行社區(qū)擴展的過程中,充分利用前階段的計算結(jié)果,將迭代更新的過程簡化成了尋址過程,完美狀態(tài)下,只需進行k×n次計算即可完成社區(qū)檢測,最壞情況下,則需進行2×k×n次 計算,其中k表示種子節(jié)點個數(shù),n表示網(wǎng)絡(luò)中節(jié)點的個數(shù),且二者間滿足k<

綜上,基于Node2Vec 的重疊社區(qū)發(fā)現(xiàn)算法整體流程大致分為以下3 個步驟:

首先,利用NodeVec 算法對網(wǎng)絡(luò)結(jié)構(gòu)進行學(xué)習(xí),得到包含豐富拓撲結(jié)構(gòu)信息的節(jié)點的向量表示,基于節(jié)點向量值計算每對節(jié)點間的相似度,用一個n×n階矩陣來表示網(wǎng)絡(luò)結(jié)構(gòu)中所有n個節(jié)點間的相似度值.

然后,利用前一階段計算得到的節(jié)點相似度,根據(jù)定義的節(jié)點影響力公式篩選出能夠獨立領(lǐng)導(dǎo)社區(qū)的種子節(jié)點集合.

最后,以種子節(jié)點為核心,分階段進行社區(qū)擴展,首先通過比較每個種子節(jié)點與所有非種子節(jié)點間相似度與給定閾值的大小關(guān)系初步擴展社區(qū),然后對于未被劃分的節(jié)點,選擇與之相似度最大的種子節(jié)點,劃入其所屬社區(qū),直至所有節(jié)點都有至少一個社區(qū)歸屬,重疊社區(qū)檢測完畢.

3 實驗

為驗證算法的相關(guān)性能,在多個不同規(guī)模的真實數(shù)據(jù)集上與其他經(jīng)典重疊社區(qū)發(fā)現(xiàn)算法進行對比實驗,待比較的算法分別是CPM、LINK、COPRA 和LFM 算法.

3.1 實驗數(shù)據(jù)集

分別選取不同類型不同數(shù)量級的5 個真實網(wǎng)絡(luò)數(shù)據(jù)集,具體包括美國空手道俱樂部網(wǎng)絡(luò)Karate[14]、海豚關(guān)系網(wǎng)Dolphins[15]、大學(xué)生足球聯(lián)賽網(wǎng)絡(luò)Football[16]、歐洲研究機構(gòu)電子郵件網(wǎng)絡(luò)Email-EU[17]和高能物理范疇論文引用關(guān)系網(wǎng)Ca-HepPh[18],各網(wǎng)絡(luò)規(guī)模如表1.

3.2 評價指標(biāo)

由于社區(qū)劃分沒有標(biāo)準(zhǔn)的結(jié)果,對于真實數(shù)據(jù)集,Newman 提出的模塊度函數(shù)[19]被廣泛認可,但該評價標(biāo)準(zhǔn)并不能很好地適用于重疊社區(qū),Shen 等在此基礎(chǔ)上提出了能衡量重疊社區(qū)劃分結(jié)果的重疊模塊度函數(shù)[20],定義如下:

其中,m表示網(wǎng)絡(luò)中的總邊數(shù),A為網(wǎng)絡(luò)的鄰接矩陣,ku為節(jié)點u的度數(shù),Qu表示節(jié)點u所屬的社區(qū)數(shù)量.

表1 真實數(shù)據(jù)情況表

3.3 實驗結(jié)果

本文提出的算法在基于種子節(jié)點進行社區(qū)擴展時,社區(qū)劃分結(jié)果易受閾值 ε大小的影響,故首先在不同數(shù)據(jù)集上在不同閾值ε 的指引下進行社區(qū)劃分,通常情況下閾值ε 的取值范圍為0.3～0.7,取步長h=0.1進行實驗,社區(qū)劃分結(jié)果隨閾值 ε大小改變而變化的情況如圖2

圖2 重疊模塊度隨閾值變化圖

從圖2可以看出,在不同數(shù)據(jù)集上,模塊度總是在ε=0.5左 右的位置取到峰值,這也說明閾值ε 對劃分結(jié)果的影響趨勢在所有數(shù)據(jù)值上是大致相當(dāng)?shù)?

將本文算法與其他4 個經(jīng)典的重疊社區(qū)發(fā)現(xiàn)算法在不同規(guī)模不同類型的數(shù)據(jù)集上進行對比實驗(閾值取ε=0.5),結(jié)果如表2所示.

在大多數(shù)數(shù)據(jù)集上,本文算法均取得了最高的模塊度值,尤其是在Emai-EU 和Ca-HepPh 兩個大規(guī)模的數(shù)據(jù)集上,分別取得了接近0.5 和0.4 重疊模塊度值,所發(fā)現(xiàn)的社區(qū)質(zhì)量明顯優(yōu)于其他算法,實驗證明,使用Node2Vec 算法將更大作用域范圍內(nèi)的網(wǎng)絡(luò)信息映射到節(jié)點向量中的方式,能夠有效地避免范圍限制所帶來的準(zhǔn)確率方面的犧牲,提升社區(qū)發(fā)現(xiàn)質(zhì)量,在規(guī)模大、結(jié)構(gòu)復(fù)雜的網(wǎng)絡(luò)上,提升效果格外顯著.

表2 真實數(shù)據(jù)集對比結(jié)果表

4 結(jié)論與展望

本文提出了一種基于Node2Vec 的重疊社區(qū)發(fā)現(xiàn)算法,首先獲得網(wǎng)絡(luò)結(jié)構(gòu)的向量表示并計算節(jié)點之間的相似度值,利用定義的影響力函數(shù)選擇出種子節(jié)點,然后以每個種子節(jié)點為核心進行社區(qū)擴張.本文選取了不同類型不同規(guī)模的真實網(wǎng)絡(luò)數(shù)據(jù)集,并在這些數(shù)據(jù)集上將本文算法與其他類經(jīng)典重疊社區(qū)發(fā)現(xiàn)算法進行對比性實驗,實驗結(jié)果表明,本文算法在大部分數(shù)據(jù)集尤其是大規(guī)模數(shù)據(jù)集上表現(xiàn)出了明顯的優(yōu)勢.后續(xù)工作將提高算法的性能,降低算法復(fù)雜度,并將算法應(yīng)用到動態(tài)社區(qū)發(fā)現(xiàn)研究中.