基于染色隨機游走的可重疊社區(qū)發(fā)現(xiàn)*

昌 陽，馬慧芳,2,3

(1.西北師范大學計算機科學與工程學院，甘肅 蘭州 730070；2.廣西師范大學廣西多源信息挖掘與安全重點實驗室，廣西 桂林 541001；3.桂林電子科技大學廣西可信軟件重點實驗室，廣西 桂林 541004)

1 引言

網(wǎng)絡(luò)(或稱圖)是現(xiàn)實世界關(guān)系的自然表示，其中節(jié)點表示數(shù)據(jù)對象，邊代表數(shù)據(jù)對象間的關(guān)系。網(wǎng)絡(luò)拓撲作為一種重要的網(wǎng)絡(luò)描述，在社區(qū)發(fā)現(xiàn)任務(wù)中應(yīng)用廣泛[1]。然而網(wǎng)絡(luò)拓撲僅反映了網(wǎng)絡(luò)的一個方面，且經(jīng)常存在噪聲。單獨使用網(wǎng)絡(luò)拓撲不一定會產(chǎn)生令人滿意的網(wǎng)絡(luò)劃分。現(xiàn)實網(wǎng)絡(luò)中節(jié)點通常與大量的屬性數(shù)據(jù)相關(guān)聯(lián)，這樣的網(wǎng)絡(luò)稱為屬性網(wǎng)絡(luò)[2]。例如Twitter網(wǎng)絡(luò)、學術(shù)引用網(wǎng)絡(luò)、共同購買網(wǎng)絡(luò)及合著關(guān)系網(wǎng)絡(luò)[3]等。節(jié)點屬性描述了節(jié)點的特定特征，提供了豐富且與節(jié)點高度相關(guān)的額外信息，這些信息可以潛在地用于社區(qū)發(fā)現(xiàn)任務(wù)并對網(wǎng)絡(luò)分析[4 -6]至關(guān)重要，研究和分析屬性網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)也具有深遠的意義。社區(qū)是指在結(jié)構(gòu)上內(nèi)部的個體之間相對于社區(qū)外部有著更密切聯(lián)系的集合，集合中的個體具有高度相似性，即社區(qū)內(nèi)連接稠密、社區(qū)外連接稀疏，且社區(qū)內(nèi)部的個體共享同質(zhì)的屬性。

基于隨機游走的社區(qū)發(fā)現(xiàn)算法[7]因其有效性廣泛地應(yīng)用于社區(qū)發(fā)現(xiàn)任務(wù)中。現(xiàn)有的基于隨機游走的社區(qū)發(fā)現(xiàn)算法大多僅利用結(jié)構(gòu)轉(zhuǎn)移矩陣信息，且不能獲取種子節(jié)點和社區(qū)之間隸屬關(guān)系的先驗信息。傳統(tǒng)的基于隨機游走的社區(qū)發(fā)現(xiàn)算法例如Tong等人[8]提出的帶重啟的隨機游走算法RWR(Random Walk with Restart)，游走者從種子節(jié)點開始，以一定的概率跳轉(zhuǎn)到相鄰節(jié)點或以一定概率跳轉(zhuǎn)回種子節(jié)點，經(jīng)過迭代得到平穩(wěn)的跳轉(zhuǎn)概率分布，可以捕捉節(jié)點之間多方面的關(guān)系，捕捉圖的整體結(jié)構(gòu)信息。Andersen等人[9]提出的PageRank-Nibble算法執(zhí)行隨機游走并基于訪問概率對節(jié)點進行排名，最后返回排名最高且電導(dǎo)率最小的節(jié)點集合作為一個局部社區(qū)。Whang等人[10]提出的算法研究如何選擇最佳的種子節(jié)點來提高聚類的精度，然后使用隨機游走算法擴展社區(qū)。Bian等人[11]提出了基于記憶的隨機游走算法MRW(Memory-based Random Walk)，利用游走者的歷史訪問路徑檢測查詢節(jié)點所屬的社區(qū)信息，并在隨機游走的過程中考慮不同游走者之間的交互關(guān)系來精準挖掘社區(qū)。此外，在社區(qū)發(fā)現(xiàn)任務(wù)中，種子節(jié)點可以是單個也可以是多個。現(xiàn)有的聚類方法簡單地假設(shè)所有種子都來自同一個簇。但是，網(wǎng)絡(luò)數(shù)據(jù)可能是有噪聲或有損的，所以知道種子節(jié)點(是否在同一個社區(qū)中)的關(guān)系很重要。一般來說，現(xiàn)有的聚類方法不能充分利用種子節(jié)點的標記，而適用于結(jié)構(gòu)良好的網(wǎng)絡(luò)。對于沒有明確社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，這種方法的性能是有限的。

利用種子節(jié)點標簽面向?qū)傩詧D執(zhí)行染色隨機游走是有價值的，但仍然存在以下2個主要的挑戰(zhàn)：

(1)如何挖掘種子節(jié)點與社區(qū)的關(guān)系：對于沒有明確社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，且現(xiàn)有的網(wǎng)絡(luò)通常會存在噪聲的情況下，如何找到高質(zhì)量種子節(jié)點并挖掘其與社區(qū)的隸屬關(guān)系是比較困難的；

(2)如何同時建模結(jié)構(gòu)和屬性信息：利用隨機游走算法來執(zhí)行社區(qū)發(fā)現(xiàn)任務(wù)時，最關(guān)鍵的一點是構(gòu)建概率轉(zhuǎn)移矩陣，如何同時考慮結(jié)構(gòu)和屬性的信息，生成融合結(jié)構(gòu)-屬性的概率轉(zhuǎn)移矩陣是存在挑戰(zhàn)的。

面對上述挑戰(zhàn)，本文提出了一種基于染色隨機游走的可重疊社區(qū)發(fā)現(xiàn)算法OCDC(Overlapping Community Detection based on Colored random walk)。首先利用初始種子選擇策略和種子替換策略來挖掘種子節(jié)點與社區(qū)的關(guān)系。選擇度最大的節(jié)點作為中心節(jié)點，利用迭代選點策略，找出與度最大的節(jié)點差異度最大的節(jié)點作為下一次的中心節(jié)點，依據(jù)此方法得到初始的種子節(jié)點集合，集合內(nèi)的節(jié)點重要性高且差異大。其次利用種子替換策略找出與初始種子節(jié)點結(jié)構(gòu)相似、屬性相似且質(zhì)量更高的種子替換節(jié)點，由于替換過程可能不是一次完成的，可能需要進行多次比較，在比較的過程中得到的一系列種子的結(jié)構(gòu)屬性都很相似，故更可能屬于同一個社區(qū)，據(jù)此獲得種子替換路徑集合，便于后續(xù)染色隨機游走算法的操作。并且，本文在構(gòu)建轉(zhuǎn)移矩陣過程中融合了結(jié)構(gòu)和屬性信息，通過生成由節(jié)點與屬性的關(guān)系構(gòu)成的交互二部圖來建模結(jié)構(gòu)和屬性信息。

受文獻[12]的啟發(fā)，除了使用隨機游走者來探索網(wǎng)絡(luò)之外，本文還對種子節(jié)點和隨機游走者進行染色，位于同一社區(qū)的種子節(jié)點用相同的顏色標記。算法從具有相應(yīng)顏色的種子節(jié)點開始對每種顏色節(jié)點執(zhí)行染色隨機游走。具體地，算法框架圖如圖1所示。本文算法由4個階段組成：首先是種子選取階段，通過初始種子選擇策略與種子替換策略，挖掘并保留質(zhì)量較好的種子替換路徑集合作為先驗信息；其次是生成融合結(jié)構(gòu)-屬性轉(zhuǎn)移矩陣階段，通過結(jié)構(gòu)-屬性交互關(guān)系捕獲節(jié)點-屬性-節(jié)點轉(zhuǎn)移關(guān)系；然后是染色隨機游走階段，基于種子替換路徑集合與結(jié)構(gòu)-屬性轉(zhuǎn)移矩陣執(zhí)行染色隨機游走算法，迭代更新轉(zhuǎn)移矩陣，得到染色分布向量；最后是擴展階段，基于結(jié)合結(jié)構(gòu)和屬性的并行電導(dǎo)值擴展高質(zhì)量社區(qū)。值得注意的是，擴展階段針對每個種子節(jié)點都是獨立的，所以可能存在重疊社區(qū)和離群點。在人工網(wǎng)絡(luò)和現(xiàn)實網(wǎng)絡(luò)上的實驗表明，本文算法的性能在很大程度上優(yōu)于對比算法。

Figure 1 Framework of overlapping community detection based on colored random walk圖1 基于染色隨機游走的可重疊社區(qū)發(fā)現(xiàn)算法框架圖

2 相關(guān)概念與問題定義

2.1 問題定義

2.2 初始種子選擇策略

初始種子的選擇將在很大程度上影響算法的性能。首先選擇屬性圖G中度最大的節(jié)點作為初始種子節(jié)點，再利用最近最遠選點策略來對種子節(jié)點進行擴展。假設(shè)度最大的初始種子節(jié)點為vi，將其作為第1個社區(qū)的中心，其次從屬性和結(jié)構(gòu)2個方面綜合考慮節(jié)點間的相似度，基于Li等人[13]提出的迭代選點策略計算得到與當前種子差異度最大的節(jié)點，作為下一個社區(qū)的中心節(jié)點，重復(fù)迭代，直到無法得到新的中心點，據(jù)此可以得到距離較遠差異較大的初始種子節(jié)點集合S={v1,v2,…,vL}。值得注意的是，當所選擇的種子節(jié)點處于圖的邊界或種子節(jié)點鏈接到社區(qū)內(nèi)節(jié)點較少時，會導(dǎo)致社區(qū)劃分的效果不佳且種子節(jié)點的質(zhì)量無法保證。為解決上述問題，本文提出了一種改進方法，利用種子替換策略找到種子替換路徑集合對初始種子集合進行替換，并保存其替換路徑。進一步提升了算法的性能且為后續(xù)算法提供了先驗信息。

Table 1 Notations and meanings表1 符號和含義

2.3 種子替換策略

定義1(節(jié)點鄰域社區(qū)) 節(jié)點vi的鄰域社區(qū)被定義為：

C(vi)=N(vi)∪{vi}

(1)

其中，

N(vi)={vj|(vi,vj)∈E}

(2)

其中，E是圖G中邊的集合。

定義2(節(jié)點質(zhì)量) 節(jié)點vi的質(zhì)量被定義為：

(3)

其中，函數(shù)f(·)為sigmoid函數(shù)，k(·)為節(jié)點的度。對社區(qū)發(fā)現(xiàn)而言，度越大，連邊越多的節(jié)點在網(wǎng)絡(luò)中越重要。節(jié)點質(zhì)量作為衡量節(jié)點重要性的指標，一方面考慮了節(jié)點本身的度即鄰居個數(shù)，另一方面考慮了節(jié)點鄰居中實際連邊與形成完全圖的占比程度，故能更有效地對節(jié)點的質(zhì)量進行衡量。

定義3(節(jié)點影響區(qū)域) 對于鏈接節(jié)點對(vi,vj)，節(jié)點影響區(qū)域被定義為：

I(vi,vj)={v|v∈(C(vi)∩C(vj))}

(4)

定義4(節(jié)點影響區(qū)域密度) 對于節(jié)點影響區(qū)域I(vi,vj)，其密度定義為：

dI(vi,vj)=

(5)

其中，|I(vi,vj)(|I(vi,vj)|-1)|/2是在節(jié)點影響區(qū)域中實際存在的連邊數(shù)量，{(v1,v2)|v1,v2∈I(vi,vj),(v1,v2)∈E}是在節(jié)點影響區(qū)域中最大存在的連邊數(shù)。

定義5(節(jié)點屬性相似度) 給定節(jié)點vi與vj，其屬性相似度被定義為：

(6)

定義6(節(jié)點關(guān)系強度) 對于鏈接節(jié)點對(vi,vj)，其節(jié)點關(guān)系強度被定義為：

rs(vi,vj)=s(vi,vj)×dI(vi,vj)×

(7)

引入節(jié)點關(guān)系強度來評估相鄰節(jié)點之間的相似性，將節(jié)點影響區(qū)域密度和節(jié)點質(zhì)量都考慮進來。此外，還融合了2個節(jié)點間的屬性相似度，更全面地衡量相鄰節(jié)點間的相似性，其中較高的節(jié)點關(guān)系強度值意味著相鄰節(jié)點之間的關(guān)系較強。種子替換策略的具體步驟如算法1所示。

算法1種子替換策略

輸入：屬性圖G=(V,F,A,B)，初始種子集合S。

輸出：種子替換路徑集合Sc。

4:foreachvi∈Sdo

5:vcan=vi,rsmax=0;

6: 利用式(2)和式(3)分別計算N(vi)和Q(vi);

7:foreachvj∈N(vi)do

8: 利用式(3)計算Q(vj);

9:ifQ(vj)>Q(vi)then

10: 利用式(7)計算rs(vi,vj);

11:ifrs(vi,vj)>rsmaxthen

12:rsmax=rs(vi,vj);

13:vcan=vj;

15:endif

16:endif

17:endfor

18:endfor

19:endfor

20:returnSc

2.4 融合結(jié)構(gòu)和屬性的轉(zhuǎn)移矩陣構(gòu)建

將網(wǎng)絡(luò)中節(jié)點和屬性看作2類節(jié)點，節(jié)點與其對應(yīng)的屬性連邊生成由節(jié)點與屬性的關(guān)系構(gòu)成的交互二部圖，記作IG=(V∪F,B)，其中，V表示結(jié)構(gòu)節(jié)點集合，F(xiàn)表示屬性節(jié)點集合，B表示節(jié)點屬性矩陣，即結(jié)構(gòu)與屬性節(jié)點之間所形成的交互。通過融合結(jié)構(gòu)和屬性信息，有效地對節(jié)點和屬性交互進行探索，推動了隨機游走的多樣化。

假設(shè)從節(jié)點?vi∈V開始跳轉(zhuǎn)，一方面，基于拓撲結(jié)構(gòu)游走到相鄰節(jié)點的概率定義如式(8)所示：

(8)

其中,AN為鄰接矩陣A的行歸一化矩陣,即初始結(jié)構(gòu)轉(zhuǎn)移矩陣。

另一方面，節(jié)點vi可基于IG構(gòu)建節(jié)點-屬性-節(jié)點轉(zhuǎn)移概率，即隨機跳轉(zhuǎn)到節(jié)點上附著的屬性集中的任意屬性fk上，然后再跳轉(zhuǎn)到具有該屬性的節(jié)點vj上，其定義如式(9)所示：

(9)

則節(jié)點-屬性-節(jié)點轉(zhuǎn)移概率的定義如式(10)所示：

(10)

即節(jié)點-屬性-節(jié)點的跳轉(zhuǎn)滿足結(jié)構(gòu)-屬性交互二部圖的轉(zhuǎn)移矩陣Q∈Rn×n：

(11)

Q=D1BD2BT

(12)

其中,D1∈Rn×n是由結(jié)構(gòu)節(jié)點生成的對角矩陣，對角線元素表示結(jié)構(gòu)節(jié)點跳轉(zhuǎn)到與它相關(guān)的屬性節(jié)點之一上的概率；D2∈Rr×r是由屬性節(jié)點生成的對角矩陣，對角線元素代表屬性節(jié)點跳轉(zhuǎn)到含有該屬性的結(jié)構(gòu)節(jié)點之一上的概率。

傳統(tǒng)的隨機游走算法僅利用結(jié)構(gòu)轉(zhuǎn)移矩陣，要在結(jié)構(gòu)-屬性交互二部圖上進行結(jié)構(gòu)-屬性隨機游走需要將屬性信息添加到轉(zhuǎn)移矩陣中，生成方式如式(13)所示：

P=δ×AN+(1-δ)×Q

(13)

其中,δ是調(diào)節(jié)重要性的參數(shù)。通過式(13)生成融合結(jié)構(gòu)和屬性的轉(zhuǎn)移矩陣P，可以在保證結(jié)構(gòu)緊密的條件下保持屬性的相似性。

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

3.1 屬性網(wǎng)絡(luò)中的染色隨機游走

自然地，游走者在進行染色隨機游走的過程中會被具有相同顏色的節(jié)點吸引，并被具有不同顏色的節(jié)點排斥。利用Hadamard乘積依據(jù)上述特性來對轉(zhuǎn)移矩陣進行強化，強化通過式(14)定義：

P(l,t)=P°(1+Λ(l,t))

(14)

在染色隨機游走過程中，游走者會將一定量的染色值留給被訪問節(jié)點，所以在執(zhí)行染色隨機游走算法的過程中游走者的跳轉(zhuǎn)會被節(jié)點現(xiàn)有顏色影響。通常，游走者更可能訪問具有相同顏色的節(jié)點，并且不太可能訪問具有不同顏色的節(jié)點。此外，由于染色隨機游走過程中顏色的積累，針對不同的顏色，概率轉(zhuǎn)移矩陣P(l,t)在不同的時刻是變化的。例如，隨機游走者從第l種顏色的種子節(jié)點vi開始執(zhí)行染色隨機游走算法，其中1≤l≤L。在(t+1)時刻，游走者以概率α繼續(xù)游走或以概率(1-α)返回到種子節(jié)點vi。染色隨機游走算法在(t+1)時刻得到顏色l的當前分布向量r(l,t+1)如式(15)所示：

r(l,t+1)=(1-α)c(l)+αP(l,t)r(l,t)

(15)

其中,c(l)是顏色l的初始分布向量，r(l,t)是t時刻的顏色l的分布向量。染色隨機游走的具體步驟如算法2所示。

算法2染色隨機游走

輸入：轉(zhuǎn)移矩陣P，種子替換路徑集合Sc，迭代次數(shù)T，超參數(shù)α，參數(shù)π1,π2,衰減函數(shù)φ(t)。

輸出：染色分布向量r。

1:foreachl∈{1,2,…,L}do

2: 初始化c(l);

3:c=[c(1);c(2);…;c(l)];

5: 初始化對角矩陣Π;

6:Π=Π?E;

7:while沒有收斂andt

13:endwhile

14:endfor

算法的冪次迭代部分對于分析時間復(fù)雜度至關(guān)重要，其中包括第8行的計算染色分布向量，第9行的強化轉(zhuǎn)移矩陣和第12行的衰減轉(zhuǎn)移矩陣，其時間復(fù)雜度為O(L×|E|)。然而現(xiàn)實網(wǎng)絡(luò)中的鄰接矩陣往往稀疏，因此，總時間復(fù)雜度為O(T×L×|E|)。經(jīng)驗表明[16]，迭代次數(shù)取10足以使染色分布向量r收斂。

3.2 社區(qū)質(zhì)量量化—并行電導(dǎo)

電導(dǎo)是測定圖中一組節(jié)點緊密程度的常見指標，而并行電導(dǎo)是同時考慮結(jié)構(gòu)和屬性來進行社區(qū)度量的指標。在屬性圖中進行社區(qū)質(zhì)量量化時，需要結(jié)合結(jié)構(gòu)和屬性信息，所以本文使用并行電導(dǎo)值來進行社區(qū)質(zhì)量量化。傳統(tǒng)的電導(dǎo)[9]度量如式(16)所示：

(16)

其中，φ(H)={(u,v)∈E|u∈H,v?H},vol(H)=∑v∈Hd(v)，d(v)表示節(jié)點v的度。H代表當前找到的社區(qū)子圖，vol(V)-vol(H)代表用整個節(jié)點度的和減去當前找到社區(qū)中節(jié)點度的和。值得注意的是，0≤Con(H)≤1,電導(dǎo)值越低代表檢測出的社區(qū)緊密度越高。

結(jié)合結(jié)構(gòu)和屬性信息的并行割[17]公式如式(17)所示：

(17)

其中,Aij是圖G鄰接矩陣中的項；sij的含義與式(6)中的一致，表示2個節(jié)點之間的屬性相似度。

由式(17)對并行割的定義，結(jié)合結(jié)構(gòu)和屬性定義并行電導(dǎo)，如(18)所示：

(18)

得到染色分布向量之后，在每種顏色的分布r下，根據(jù)節(jié)點的顏色對節(jié)點進行排序，從概率最大的節(jié)點開始掃描切割社區(qū)，為每一種顏色l返回一個電導(dǎo)最小的社區(qū)Hl。由于擴展階段對于每個節(jié)點來說都是獨立進行的，所以節(jié)點可能屬于多個社區(qū)，即重疊社區(qū)是存在的。使用并行電導(dǎo)值來擴展社區(qū)，既可以保證社區(qū)內(nèi)節(jié)點共享同質(zhì)屬性也能保證連通性，能夠避免即使在原網(wǎng)絡(luò)中不連通但為具有某個相同屬性的一對節(jié)點分配相同的顏色，從而導(dǎo)致社區(qū)結(jié)果的準確性下降。社區(qū)質(zhì)量量化耗費的時間為O(L(n+n))。首先，因為要從概率最大的節(jié)點開始掃描切割社區(qū)，故而要執(zhí)行n次；其次，因為要取節(jié)點列表的長度次來劃分社區(qū)，所以節(jié)點列表的最大長度為n；最后，對每種顏色執(zhí)行一次，故社區(qū)質(zhì)量量化總體需要的時間復(fù)雜度是O(2nL)。

4 實驗及結(jié)果分析

本節(jié)通過實驗驗證OCDC算法的有效性和效率。分別在人工網(wǎng)絡(luò)數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集上設(shè)計了多組實驗，旨在回答以下問題：

問題1不同參數(shù)的選擇對本文算法的影響如何？

問題2OCDC算法中的2個重要階段是種子選取階段和生成結(jié)構(gòu)-屬性節(jié)點轉(zhuǎn)移矩陣階段，每個階段的貢獻有多少？

問題3與對比算法相比本文算法的性能如何？

4.1 實驗設(shè)置和數(shù)據(jù)集

4.1.1 人工網(wǎng)絡(luò)數(shù)據(jù)集

實驗環(huán)境采用Intel i5-8265U Core 1.60 GHz處理器，16 GB內(nèi)存，64位Windows 10操作系統(tǒng)，所有算法均使用Python實現(xiàn)。

具有基準社區(qū)的人工網(wǎng)絡(luò)是基于LFR(Lancichinetti A,Fortunato S,Radicchi F)基準[18]生成的，其具有與真實世界網(wǎng)絡(luò)類似的特征，且可以很好地表示出節(jié)點度和社區(qū)規(guī)模分布的異質(zhì)性。通過分區(qū)約束將鄰接矩陣分成塊，為每一個塊選擇概率oij以衡量每個區(qū)塊之間的密度。對角線上的塊為實際社區(qū)，非對角線塊為社區(qū)間的交叉邊[19]。另外，為節(jié)點分配屬性i∈[0,1]及其取值hi，需從屬性值服從正態(tài)分布的N(μ,σ)中提取，其余的屬性是從具有更大方差的正態(tài)分布N(0,1)中提取。利用LFR基準程序共生成了5組人工模擬網(wǎng)絡(luò)如表2所示。

Table 2 Synthetic network datasets表2 人工網(wǎng)絡(luò)數(shù)據(jù)集

4.1.2 真實網(wǎng)絡(luò)數(shù)據(jù)集

本節(jié)利用3個類型各異的真實網(wǎng)絡(luò)數(shù)據(jù)集對本文算法進行驗證，統(tǒng)計信息如表3所示。

具體地：DBLP(Digital Bibliography &Library Project)[20]為作者合著關(guān)系網(wǎng)絡(luò)，其中節(jié)點表示作者，邊表示作者之間的合著關(guān)系，屬性表示作者的研究領(lǐng)域或合作人員列表。Amazon[21]數(shù)據(jù)集是產(chǎn)品共同購買網(wǎng)絡(luò)，可從斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集獲得，其中節(jié)點是產(chǎn)品，共同購買的產(chǎn)品通過邊連接，屬性為產(chǎn)品具有的特征，每個節(jié)點都包含多種類型的屬性。實驗中只使用電子產(chǎn)品類別的元數(shù)據(jù)。Cora[22]數(shù)據(jù)集是一個由機器學習論文組成的網(wǎng)絡(luò)，其中節(jié)點是論文，邊是論文之間的引用關(guān)系，論文被另一篇論文引用一次或兩者之間相互引用記為一條邊，通過論文的關(guān)鍵字將論文劃分到相應(yīng)的機器學習的子科目中。

Table 3 Real-world network datasets表3 真實網(wǎng)絡(luò)數(shù)據(jù)集

4.2 對比算法與評價指標

4.2.1 對比算法

為了驗證OCDC算法的有效性，選擇以下5類對比算法：(1)研究保存種子替換路徑集合對于本文算法的影響，將去除種子替換策略的OCDC算法變體OCDC-noPATH與其進行比較；(2)為研究在簡單圖上本文算法和其他算法的性能，選擇了簡單圖上的染色隨機游走算法CRW和NISE(Neighborhood-Inflated Seed Expansion)；(3)選擇了一種面向?qū)傩詧D上的社區(qū)發(fā)現(xiàn)算法AGGMMR(Augmented Graph with Modularity Maximisation and Refinement)；(4)選擇了一種經(jīng)典的基于深度學習的聚類算法SDCN(Structural Deep Clustering Network)；(5)對比不考慮生成融合結(jié)構(gòu)-屬性轉(zhuǎn)移矩陣的OCDC算法的變體OCDC-noIG，研究生成結(jié)構(gòu)-屬性交互二部圖的有效性。對于SDCN算法，使用預(yù)先訓練的自動編碼器，與文獻[22]一致，使用30(epochs)輪數(shù)的所有數(shù)據(jù)點端到端地訓練自動編碼器，學習率為10-3。所有的基準算法的參數(shù)設(shè)置為相應(yīng)論文給出的參數(shù)或默認值，對比算法具體介紹如下：

(1)OCDC-noPATH：不考慮種子替換策略的OCDC算法變體。

(2)CRW[12]：該算法是半監(jiān)督的局部聚類算法，面向簡單圖執(zhí)行染色隨機游走算法，最后使用最小電導(dǎo)挖掘社區(qū)。

(3)NISE[10]：該算法是基于種子擴展的社區(qū)發(fā)現(xiàn)算法，通過過濾-播種-擴展-傳播4個階段挖掘社區(qū)，特別地為個性化的PageRank聚類方案設(shè)計新的播種策略，優(yōu)化電導(dǎo)社區(qū)得分。

(4)AGGMMR[2]：該算法通過貪婪模塊度最大化模型，設(shè)計了一個基于屬性和拓撲信息的屬性圖劃分框架。

(5)SDCN[22]：該算法設(shè)計了一個傳遞操作，將自動編碼器學習到的表示傳遞到相應(yīng)的GCN(Graph Convolutional Network)層，并設(shè)計了一個雙重自監(jiān)督機制，將這2種不同的深層神經(jīng)結(jié)構(gòu)統(tǒng)一起來，用于學習GCN的特定表示。

(6)OCDC-noIG：不考慮生成結(jié)構(gòu)-屬性交互二部圖的OCDC算法變體。

4.2.2 評價指標

本文采用文獻[23,24]中對經(jīng)典F1和歸一化互信息NMI的改進評價指標來對算法性能進行評估。

(19)

其中最佳匹配g(i)和g′(i)的定義分別如式(20)和式(21)所示：

(20)

(21)

與平均F1計算方法類似，通過基準社區(qū)和檢測出的社區(qū)之間的最佳匹配NMI來計算平均NMI,如式(22)所示：

(22)

其中最佳匹配g(i)和g′(i)定義分別如式(23)和式(24)所示：

(23)

(24)

4.3 參數(shù)分析(問題1)

本文算法中主要設(shè)計了4個參數(shù)，分別為調(diào)節(jié)轉(zhuǎn)移矩陣重要性參數(shù)δ、人工網(wǎng)絡(luò)中的混合參數(shù)μ、矩陣強化過程中的吸引系數(shù)π1與排斥系數(shù)π2。

(1)參數(shù)δ。參數(shù)δ是調(diào)節(jié)初始結(jié)構(gòu)轉(zhuǎn)移矩陣以及結(jié)構(gòu)-屬性交互二部圖轉(zhuǎn)移矩陣相對重要性的參數(shù)，通過在syn1和syn2上調(diào)節(jié)δ的大小來觀察該參數(shù)對本文算法的影響，此時人工網(wǎng)絡(luò)上μ=0.1。實驗結(jié)果如圖2所示。實驗結(jié)果表明，在δ過大或過小時算法的性能不佳，而在δ=0.5時算法的性能最好。這是因為OCDC算法在生成轉(zhuǎn)移矩陣的階段同時考慮了結(jié)構(gòu)和屬性信息。若原始拓撲信息占比過高會導(dǎo)致檢測出的社區(qū)在結(jié)構(gòu)上緊湊而在屬性上稀疏；反之如果在社區(qū)發(fā)現(xiàn)的過程中屬性信息占比過高也會導(dǎo)致算法效果不佳。

Figure 2 Effects of δ on clustering result圖2 δ對聚類結(jié)果的影響

(2)混合參數(shù)μ。μ代表社區(qū)內(nèi)部節(jié)點與社區(qū)外部鏈接的概率，且μ值越大，社區(qū)發(fā)現(xiàn)的難度會越高。圖3為不同算法在不同μ的取值下在syn2人工網(wǎng)絡(luò)上的實驗結(jié)果，此時參數(shù)π1和π2固定為最優(yōu)值，可以看出盡管μ取不同的值，OCDC算法的NMI值均高于其他算法的。從圖3中可以看出，隨著μ值增大，OCDC算法性能下降的速度與其他對比算法比較相對緩慢，從側(cè)面說明了OCDC算法選擇質(zhì)量最優(yōu)的種子節(jié)點的有效性，也進一步說明了在得到染色分布向量之后，利用并行電導(dǎo)進行社區(qū)擴展的好處。對比算法中，CRW算法利用隨機游走算法進行聚類，最后利用電導(dǎo)率對社區(qū)進行挖掘，但為半監(jiān)督算法，不能獲取種子與社區(qū)之間隸屬關(guān)系的先驗信息；AGGMMR算法初始對圖上的屬性信息進行聚類，以虛擬節(jié)點和虛擬邊構(gòu)造擴充圖，不能很好地處理網(wǎng)絡(luò)中屬性所帶來的噪聲，簡單地將這2種類型的信息結(jié)合起來可能并不總能獲得更好的性能；NISE算法利用節(jié)點的所有鄰居集進行社區(qū)擴展，很容易形成大的社區(qū)，對算法精度造成影響；SDCN算法在大多數(shù)情況下都能獲得比普通算法更好的性能，這得益于深度學習框架，而顯然本文算法的性能略優(yōu)于SDCN算法的。

Figure 3 Effects of μ on clustering result圖3 μ對聚類結(jié)果的影響

(3)參數(shù)π1和π2。參數(shù)π1和π2是算法2中強化轉(zhuǎn)移矩陣時的吸引和排斥系數(shù)，在syn4上通過改變參數(shù)π1和π2來觀察吸引和排斥系數(shù)對本文算法的影響。與文獻[12]一致，設(shè)衰減函數(shù)φ(t)=0.9。假設(shè)syn4上只有一個社區(qū)，隨機選擇社區(qū)中的1個或2個種子節(jié)點，此時沒有不同的顏色，只使用吸引系數(shù)π1，并將π2設(shè)為0，實驗結(jié)果如圖4所示。隨著π1的增大，聚類精度明顯提高，當π1趨近于0時，算法退化為傳統(tǒng)的基于隨機游走的社區(qū)發(fā)現(xiàn)算法，對于2個種子節(jié)點的情形，由于種子節(jié)點較多，初始精度會高于1個種子節(jié)點時，但在log(π1)>2.8后，由于2個單獨的種子節(jié)點周圍的過度強吸引分離了網(wǎng)絡(luò)，因此精度會略微下降。圖5也顯示了類似的結(jié)果，從2個相鄰的社區(qū)中選擇1個或2個節(jié)點，并用不同的顏色標記，在log(π2)>1.2左右性能最好。

Figure 4 Effects of π1 on clustering result圖4 π1對聚類結(jié)果的影響

Figure 5 Effects of π2 on clustering result圖5 π2對聚類結(jié)果的影響

4.4 主要階段貢獻分析(問題2)

為了進一步研究種子替換策略階段和生成結(jié)構(gòu)-屬性交互二部圖階段對于OCDC算法的貢獻。本節(jié)將對比忽略種子替換策略的OCDC-noPATH與OCDC算法的平均F1和NMI以及忽略結(jié)構(gòu)-屬性交互二部圖的OCDC-noIG與OCDC算法的平均F1和NMI。探究通過種子替換策略和生成結(jié)構(gòu)-屬性交互二部圖是否可以使得社區(qū)發(fā)現(xiàn)的結(jié)果更精確。

根據(jù)表4的結(jié)果，有以下3個主要結(jié)論：首先，如果沒有種子替換策略，即在初始選擇策略完成之后，直接將初始種子集合用于染色隨機游走。從表4可以觀察到忽略種子替換策略的OCDC-noPATH算法的平均F1與NMI在每個數(shù)據(jù)集上都呈現(xiàn)出相較OCDC算法低的值，這說明了種子替換策略的有效性。其次也可看到OCDC算法的結(jié)果具有較高的一致性值，這表明該算法相對來說是比較穩(wěn)健的。原因在于通過種子替換策略得到了質(zhì)量更高的種子替換路徑集合，同時也為染色隨機游走算法提供了先驗信息，所以游走者捕獲到的社區(qū)更加準確。

Table 4 Performance comparison on real networks表4 真實網(wǎng)絡(luò)上的性能比較

表5是忽略網(wǎng)絡(luò)中節(jié)點所攜帶的外部屬性信息，得到的面向簡單圖的不同算法與本文算法變體的平均F1和NMI。從表5中可看出，OCDC-noIG算法與不考慮屬性信息的NISE算法相比，在所有數(shù)據(jù)集上具有較高的值，得益于該算法提出了種子替換策略，得到了質(zhì)量更好的種子替換路徑集合，提高了算法的準確性，從而使得隨機游走結(jié)果在各種規(guī)模的數(shù)據(jù)集上都更精確。

Table 5 Performance comparison with other algorithms on simple networks表5 簡單網(wǎng)絡(luò)上與其他算法的性能比較

4.5 性能比較(問題3)

表6和表7展示了在5個由LFR基準生成的人工網(wǎng)絡(luò)數(shù)據(jù)集和3個真實網(wǎng)絡(luò)數(shù)據(jù)集上本文算法與對比算法的平均F1與NMI的實驗結(jié)果。

表6顯示了人工網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果，此時5個人工網(wǎng)絡(luò)的混合參數(shù)μ分別取0.1,0.3,0.5,0.4,0.2，其他參數(shù)不變。從表6中可以看出，在所有人工網(wǎng)絡(luò)上本文算法的性能都優(yōu)于其他算法的，表明OCDC算法具有較好的性能。因為OCDC算法在種子選取階段采用種子替換策略生成了質(zhì)量較好的種子替換路徑集合，為染色隨機游走算法提供了先驗信息，其次生成融合結(jié)構(gòu)和屬性的轉(zhuǎn)移矩陣，并在此基礎(chǔ)上執(zhí)行染色隨機游走得到染色分布向量，提高了社區(qū)發(fā)現(xiàn)的有效性和效率。

表7顯示了在真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果，OCDC在人工數(shù)據(jù)集上的NMI和F1優(yōu)于在真實數(shù)據(jù)集上的，這是無可厚非的。對于真實網(wǎng)絡(luò)數(shù)據(jù)集，在6個結(jié)果中，OCDC在4個結(jié)果上優(yōu)于其他對比算法的，在DBLP數(shù)據(jù)集上平均F1和平均NMI略低于SDCN的，這是因為SDCN算法得益于深度學習框架，并設(shè)計了一個傳遞操作，將自動編碼器學習到的表示傳遞到相應(yīng)的GCN層，設(shè)計了一個雙重自監(jiān)督機制，將這2種不同的深層神經(jīng)結(jié)構(gòu)統(tǒng)一起來，指導(dǎo)整個模型的更新。在規(guī)模最大的DBLP數(shù)據(jù)集上，SDCN的性能略優(yōu)于本文OCDC算法的，表明沒有使用深度學習框架的算法也能產(chǎn)生與深度學習算法相當?shù)男阅堋６贏mazon和Cora數(shù)據(jù)集上，OCDC的結(jié)果顯著優(yōu)于其他未融合深度學習的對比算法，且略優(yōu)于SDCN的，再次表明了OCDC的強大性能，以及種子替換策略和生成融合結(jié)構(gòu)和屬性的轉(zhuǎn)移矩陣的重要性。總的來說，在人工網(wǎng)絡(luò)數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集上，OCDC算法在16個結(jié)果中有14個取得了最佳性能。

5 結(jié)束語

本文研究了面向?qū)傩詧D的可重疊社區(qū)發(fā)現(xiàn)問題。具體地說，本文挖掘了種子替換路徑集合并獲取了融合結(jié)構(gòu)和屬性的轉(zhuǎn)移矩陣，在此基礎(chǔ)上執(zhí)行染色隨機游走算法，最后再基于并行電導(dǎo)擴展社區(qū)。本文算法除了利用原始拓撲轉(zhuǎn)移矩陣信息外還融合了結(jié)構(gòu)-屬性交互二部圖的節(jié)點概率轉(zhuǎn)移矩陣的信息，有效地對節(jié)點和屬性的交互進行探索。實驗表明，在人工網(wǎng)絡(luò)數(shù)據(jù)集和真實網(wǎng)絡(luò)數(shù)據(jù)集上，與對比算法相比，本文提出的OCDC算法都表現(xiàn)出較好的性能，提高了社區(qū)發(fā)現(xiàn)的有效性和效率。除了網(wǎng)絡(luò)中節(jié)點的異構(gòu)性外，真實網(wǎng)絡(luò)上的節(jié)點和邊也可能具有多種類型，據(jù)此在屬性多重異構(gòu)網(wǎng)絡(luò)上進行社區(qū)發(fā)現(xiàn)將是未來的工作。

Table 6 Average F1 and average NMI on five synthetic networks表6 5個人工網(wǎng)絡(luò)上的平均F1與平均NMI

Table 7 Average F1 and average NMI on real networks表7 真實網(wǎng)絡(luò)上的平均F1與平均NMI