基于染色隨機游走的可重疊社區發現*

昌 陽，馬慧芳,2,3

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

1 引言

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

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

利用種子節點標簽面向屬性圖執行染色隨機游走是有價值的，但仍然存在以下2個主要的挑戰：

(1)如何挖掘種子節點與社區的關系：對于沒有明確社區結構的網絡，且現有的網絡通常會存在噪聲的情況下，如何找到高質量種子節點并挖掘其與社區的隸屬關系是比較困難的；

(2)如何同時建模結構和屬性信息：利用隨機游走算法來執行社區發現任務時，最關鍵的一點是構建概率轉移矩陣，如何同時考慮結構和屬性的信息，生成融合結構-屬性的概率轉移矩陣是存在挑戰的。

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

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

Figure 1 Framework of overlapping community detection based on colored random walk圖1 基于染色隨機游走的可重疊社區發現算法框架圖

2 相關概念與問題定義

2.1 問題定義

2.2 初始種子選擇策略

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

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

2.3 種子替換策略

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

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

(1)

其中，

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

(2)

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

定義2(節點質量) 節點vi的質量被定義為：

(3)

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

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

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

(4)

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

dI(vi,vj)=

(5)

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

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

(6)

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

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

(7)

引入節點關系強度來評估相鄰節點之間的相似性，將節點影響區域密度和節點質量都考慮進來。此外，還融合了2個節點間的屬性相似度，更全面地衡量相鄰節點間的相似性，其中較高的節點關系強度值意味著相鄰節點之間的關系較強。種子替換策略的具體步驟如算法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 融合結構和屬性的轉移矩陣構建

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

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

(8)

其中,AN為鄰接矩陣A的行歸一化矩陣,即初始結構轉移矩陣。

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

(9)

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

(10)

即節點-屬性-節點的跳轉滿足結構-屬性交互二部圖的轉移矩陣Q∈Rn×n：

(11)

Q=D1BD2BT

(12)

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

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

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

(13)

其中,δ是調節重要性的參數。通過式(13)生成融合結構和屬性的轉移矩陣P，可以在保證結構緊密的條件下保持屬性的相似性。

3 可重疊社區發現算法

3.1 屬性網絡中的染色隨機游走

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

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

(14)

在染色隨機游走過程中，游走者會將一定量的染色值留給被訪問節點，所以在執行染色隨機游走算法的過程中游走者的跳轉會被節點現有顏色影響。通常，游走者更可能訪問具有相同顏色的節點，并且不太可能訪問具有不同顏色的節點。此外，由于染色隨機游走過程中顏色的積累，針對不同的顏色，概率轉移矩陣P(l,t)在不同的時刻是變化的。例如，隨機游走者從第l種顏色的種子節點vi開始執行染色隨機游走算法，其中1≤l≤L。在(t+1)時刻，游走者以概率α繼續游走或以概率(1-α)返回到種子節點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染色隨機游走

輸入：轉移矩陣P，種子替換路徑集合Sc，迭代次數T，超參數α，參數π1,π2,衰減函數φ(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

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

3.2 社區質量量化—并行電導

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

(16)

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

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

(17)

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

由式(17)對并行割的定義，結合結構和屬性定義并行電導，如(18)所示：

(18)

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

4 實驗及結果分析

本節通過實驗驗證OCDC算法的有效性和效率。分別在人工網絡數據集和真實網絡數據集上設計了多組實驗，旨在回答以下問題：

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

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

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

4.1 實驗設置和數據集

4.1.1 人工網絡數據集

實驗環境采用Intel i5-8265U Core 1.60 GHz處理器，16 GB內存，64位Windows 10操作系統，所有算法均使用Python實現。

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

Table 2 Synthetic network datasets表2 人工網絡數據集

4.1.2 真實網絡數據集

本節利用3個類型各異的真實網絡數據集對本文算法進行驗證，統計信息如表3所示。

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

Table 3 Real-world network datasets表3 真實網絡數據集

4.2 對比算法與評價指標

4.2.1 對比算法

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

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

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

(3)NISE[10]：該算法是基于種子擴展的社區發現算法，通過過濾-播種-擴展-傳播4個階段挖掘社區，特別地為個性化的PageRank聚類方案設計新的播種策略，優化電導社區得分。

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

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

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

4.2.2 評價指標

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

(19)

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

(20)

(21)

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

(22)

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

(23)

(24)

4.3 參數分析(問題1)

本文算法中主要設計了4個參數，分別為調節轉移矩陣重要性參數δ、人工網絡中的混合參數μ、矩陣強化過程中的吸引系數π1與排斥系數π2。

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

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

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

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

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

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

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

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

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

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

Table 4 Performance comparison on real networks表4 真實網絡上的性能比較

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

Table 5 Performance comparison with other algorithms on simple networks表5 簡單網絡上與其他算法的性能比較

4.5 性能比較(問題3)

表6和表7展示了在5個由LFR基準生成的人工網絡數據集和3個真實網絡數據集上本文算法與對比算法的平均F1與NMI的實驗結果。

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

表7顯示了在真實網絡數據集上的實驗結果，OCDC在人工數據集上的NMI和F1優于在真實數據集上的，這是無可厚非的。對于真實網絡數據集，在6個結果中，OCDC在4個結果上優于其他對比算法的，在DBLP數據集上平均F1和平均NMI略低于SDCN的，這是因為SDCN算法得益于深度學習框架，并設計了一個傳遞操作，將自動編碼器學習到的表示傳遞到相應的GCN層，設計了一個雙重自監督機制，將這2種不同的深層神經結構統一起來，指導整個模型的更新。在規模最大的DBLP數據集上，SDCN的性能略優于本文OCDC算法的，表明沒有使用深度學習框架的算法也能產生與深度學習算法相當的性能。而在Amazon和Cora數據集上，OCDC的結果顯著優于其他未融合深度學習的對比算法，且略優于SDCN的，再次表明了OCDC的強大性能，以及種子替換策略和生成融合結構和屬性的轉移矩陣的重要性。總的來說，在人工網絡數據集和真實網絡數據集上，OCDC算法在16個結果中有14個取得了最佳性能。

5 結束語

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

Table 6 Average F1 and average NMI on five synthetic networks表6 5個人工網絡上的平均F1與平均NMI

Table 7 Average F1 and average NMI on real networks表7 真實網絡上的平均F1與平均NMI