融合結構與屬性視圖的可重疊社區發現算法*

昌 陽，馬慧芳,2

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

1 引言

社區發現算法是發現社區內部結構和組織原則的基本工具，在多個領域發揮著重要作用，如生物網絡的新陳代謝網絡分析、社交網絡中的社區劃分等。許多真實世界的網絡不僅包含結構信息[1]，節點上還附加了豐富的屬性，但僅考慮一類信息源不足以確定社區結構，原因有2個：一是結構通常是稀疏和嘈雜的，若僅使用結構信息來執行聚類，通常會導致不好的劃分結果；二是若僅使用屬性信息進行聚類，不相關的屬性信息也可能會導致非最優的聚類結果。

傳統的社區發現算法僅針對結構和屬性之一進行挖掘，或是將兩者線性疊加再進行挖掘，故不能有效進行信息源的融合[2 - 4]。Whang等人[5]提出的NEO-K-Means(Non-Exhaustive Overlapping K-Means)和Jing等人[6]提出的EWKM(Entropy Weighting K-Means)都是對K-Means的擴展，前者考慮了類簇之間的重疊性和離群點的情況，但未考慮結構和屬性信息，后者考慮了子空間和節點屬性，未考慮結構信息。與上述不同，部分社區檢測算法同時考慮了節點間的屬性和結構信息。例如，Yang等人[7]提出的CESNA(Communities from Edge Structure and Node Attributes)算法考慮了2種信息源，但相對重要性無法自動計算；Chen等人[8]提出的TW-K-Means(Two-level variable Weighting K-Means)算法未考慮可重疊的情況；Ruan等人[9]提出的CODICIL(COmmunity Discovery Inferred from Content Information and Link-structure)算法使用屬性為每個節點找到最近的鄰居，然后通過將每個節點與其相鄰點相連來保留圖屬性信息對圖進行重構；Cohn等人[10]以實驗方式調整每個信息源的重要性，簡單地將所有節點權重固定為特定值。然而，并非所有待聚類的節點的結構和屬性信息在決定節點的隸屬關系時都具有相同的重要性。此外，作為傳統聚類算法在高維空間中的延伸，基于子空間的聚類算法認為每個類簇是由屬性子集標識的一組數據，且不同類簇可以用不同屬性子集表示。故此，本文設計了一種計算類簇子空間的算法，在算法每輪迭代過程中更新各類簇的屬性子空間。通過定義合理的目標函數約束條件對傳統的K-Means聚類算法進行修正，從而計算每個類簇中各個維度的權重，使用權重值來標識不同類簇中維度的相對重要性。

綜上，本文提出了一種融合結構與屬性視圖的可重疊社區發現COCD(Combination structure and attribute view for Overlapping Community Detection algorithm)算法,同時考慮了網絡中的結構和屬性信息，可以自動計算兩者的相對重要性以及社區中特定屬性的權重并揭示子空間。

2 準備工作

2.1 問題定義

給定屬性網絡G=(V,E,F)，其中V={v1,v2,…,vn}是n個節點集合；E是邊集，且|E|=m；F={f1,f2,…,fr}是r個屬性的集合；A表示鄰接矩陣，若節點vi和vj間有邊，則Aij=1，否則為0。假設將圖劃分為k個社區，C={c1,c2,…,ck}。表1總結了本文用到的重要符號。

Table 1 Several important mathematical notations表1 本文所用到的符號

2.2 雙視圖的構建

將圖G分別表示為屬性視圖G1和結構視圖G2，其中G1用屬性矩陣AF=[fij]∈Rn×r表示，fij為節點vi在第j維上的屬性；G2用結構矩陣As=[Bij]∈Rn×d表示，Bij為節點vi在第j維上的結構嵌入值。

2.2.1 屬性視圖的構建

對于屬性圖中的每一個節點，它與r維向量表示的屬性相關聯。每個向量中的元素是節點的屬性值。屬性值可以是單個單詞、標簽等，取決于給定網絡的上下文。給定數據點矩陣X=[Xij]∈Rn×m，每個數據點上附著各自的屬性{f1,f2,…,fr}，由此形成屬性矩陣。

2.2.2 結構視圖的構建

構建結構視圖旨在將信息網絡嵌入低維空間，可將每個節點都表示為一個低維向量。經典的圖嵌入算法之一如DeepWalk[11]，通過對圖隨機游走得到一些序列，把序列當句子，利用word2vec就可以得到每一個“詞”的向量。node2vec[12]可以看作是對 DeepWalk 的一種更廣義的抽象，主要是對DeepWalk的隨機游走策略進行了改進，因為普通的隨機游走不能很好地保留節點的局部信息，所以node2vec增加了2個參數來對節點鄰居加以控制，以獲取鄰域信息和更復雜的依賴信息。Graph2vec[13]直接對整個圖進行嵌入，原理與DeepWalk類似。近期提出的用于隨機塊模型的不同的隱私鄰接譜嵌入算法ASE(Adjacency Spectral Embedding)[14]，通過鄰接譜嵌入估計接近于Frobenius范數的潛在位置，并在模擬網絡和真實網絡中達到與期望參數相當的高精度，來有效地進行圖嵌入。LINE(Large-scale Information Network Embedding)[15]作為圖嵌入的經典算法，融合了一階與二階相似度，可以有效地將大規模網絡嵌入到低維向量空間，其適用性廣泛，這也是本文選擇LINE進行嵌入的原因。

定義1(結構相似度) 節點對(vi,vj)的結構相似度是其鄰居網絡結構之間的相似度，ui是vi被視為節點時的表示，u′i是vi被視為其他節點特定“上下文”時的表示。若無節點同時和vi與vj連接，則vi和vj的結構相似度是0。結構相似度計算公式如下所示：

(1)

(2)

O=-∑(vi,vj)∈ESijlogp(vj|vi)

(3)

與LINE算法[15]類似，通過學習n個節點作為節點的向量表示{ui|i=1,2,…,n}和作為“上下文”的向量表示{u′i|i=1,2,…,n}，使式(3)最小化，能夠用d維向量ui表示每個節點vi。

3 COCD算法

3.1 COCD目標函數

現有的基于視圖的維度加權聚類算法如TW-K-Means[8]可以執行子空間聚類任務。與在整個數據集的維度上分配權重不同，子空間聚類算法為每個類簇中的每一維度分配權重，因此，不同的類簇具有不同的權重值集合，為了保持可擴展性，在這些新的子空間聚類算法中采用了K-Means 的聚類過程。在每次迭代中，不僅能同時計算視圖和維度的權重，還能為視圖中的每個維度分配權重。本文融合節點間的屬性和結構信息改進了TW-K-Means算法，將固有的子空間聚類算法集成到重疊社區發現的框架中，不僅能自適應地計算2個視圖的相對重要性，還能挖掘可重疊的社區及子空間。將數據點X進行預處理后，構建結構視圖和屬性視圖，再聚類為k個簇的過程建模為以下目標函數的最小化：

(4)

其中,U是指示矩陣，表示節點和簇的隸屬關系；Z表示簇中心矩陣；w是一個2×1且元素都初始化為1/2的列向量，表示視圖的相對重要性；h是m×1的列向量，表示視圖下每一維屬性的相對重要性。右側第1項是簇內分散程度的總和，l表示簇編號;i表示節點編號；j表示每一個視圖的維度，j=1時表示結構視圖，j=2時表示屬性視圖;t表示視圖編號,t=1,2;G1和G2分別是結構視圖維度和屬性視圖維度的集合。第2項和第3項是2個負熵權，λ和η是2個正參數。約束于：

其中,α控制聚類之間的重疊度，0≤α≤(k-1)。算法流程圖如圖1所示。

Figure 1 Flowchart of the overlapping community detection algorithm combing structure with attribute view圖1 融合結構和屬性視圖的可重疊社區發現算法流程圖

如圖1所示，首先，對數據進行預處理后，獲取社區發現算法所需的雙視圖。一方面，從原始屬性圖上獲取屬性矩陣；另一方面，利用結構相似度方法將圖嵌入到低維空間，轉換成低維向量之后得到結構矩陣。由此獲得算法需要的原始數據矩陣。其次，隨機初始化簇中心矩陣、視圖權重以及每一個視圖中的每一維權重；再計算數據點與簇中心的加權距離矩陣，根據加權距離矩陣，將數據點分配給距離最近的簇，得到指示矩陣。然后，利用指示矩陣和數據矩陣對每個簇中的數據每一維度求平均值，更新簇中心矩陣。再次，子空間聚類算法為每個類簇中的每一維度分配權重，再更新視圖權重向量和視圖上屬性的維度權重向量，即揭示子空間。最后，計算目標函數的值，查看目標函數值是否收斂，若已收斂，結束算法，得到指示矩陣；若仍未收斂，迭代上述過程，直到目標函數收斂或者達到最大迭代次數，結束算法。此外，目標函數給出了關于算法重疊度的約束條件，使得算法可以檢測網絡中的重疊社區。

3.2 模型優化

通過迭代求解以下最小化問題來最小化式(4)：

優化目標函數的方法是對U、Z和w以及h進行部分優化。通過迭代算法使得目標函數趨于局部極小值，優化部分每一步都是嚴格遞減的，故算法收斂于局部最小值。對于固定U、Z和h，根據w對目標函數進行最小化時，本文與文獻[8]類似使用如下函數更新目標函數。視圖權重wt和視圖下維度權重hj的計算公式如下所示:

當且僅當給定U、Z和h，下式成立：

(5)

證明對于hj，最小化目標函數式(4)，若j=1，hj表示第1個視圖上第j維的重要性，若j=2，hj表示第2個視圖上第j維的重要性。對于t=1,2，存在約束∑j∈Gthj=1,0≤hj≤1,t=1,2，通過隔離包含{h1,h2,…,hm}的項,并添加合適的拉格朗日乘數得到形式化后的拉格朗日函數：

η∑j∈Gthjloghj+γt(∑j∈Gthj-1)]

(6)

其中,Qj是在固定U、Z、w時第j維的雙視圖權重，

對于γt和hj，將L{h1,h2,…,hm}的梯度設置為0，得到：

?L{h1,h2,…,hm}/?γt=∑j∈Gthj-1=0

(7)

?L{h1,h2,…,hm}/?vj=Qj+η(1+loghj)+γt=0

(8)

由式(8)得到：

hj=exp[(-Qj-γt-η)/η]=

exp[(-Qj-η)/η]exp(-γt/η)

(9)

將式(9)代入式(6)得到：

(10)

故

exp(-γt/η)=1/∑j∈Gtexp[(-Qj-η)/η]

(11)

將式(11)代入式(9)得到：

hj=exp(-Qj/η)/∑m∈Gtexp(-Qm/η)

同上可得：

當且僅當給定U、Z和w，下式成立：

hj=exp(-Qj/η)/∑m∈Gtexp(-Qm/η)

(12)

3.3 COCD算法偽代碼

根據上述最小化過程總結COCD算法總結如算法1所示。

算法1COCD算法

Input：數據點矩陣X，簇個數k，控制重疊的參數α，正參數η，λ。

Output：U,Z,h,w。

1.隨機選取k個簇中心Z;

2.fort=1to2do

3.wt=1/2;

4.forallj∈Gtdo

5.hj=1/|Gt|;

6.endfor

7.endfor

8.r←0;

9.repeat

10. 計算每一個數據點與所有簇中心的加權距離矩陣[djl]n×k;

11. 初始化全為0指示矩陣U;

12. 初始化T=φ,p=0;

13.whilep<(n+αn)do

15.endwhile

16. 更新簇中心矩陣Z,根據式(5)更新w,根據式(6)更新h;

17.r←r+1;

18.until目標函數值到達局部最小值或達到迭代次數

在算法1中，X是進行預處理之前的n個數據點矩陣；k是輸入簇的個數；α是控制重疊程度的參數，η，λ是2個正參數；T表示存放節點被分配到簇的集合，集合中的元素是節點和簇的二元組，表示該節點被劃分到了相應的簇；p是確定重疊度的參數。1～7行是初始化過程，初始化簇中心矩陣Z、視圖權重向量w、視圖下維度權重向量h。第10行是計算加權距離矩陣。第11、12行初始化一些參數。第13～15行用來判斷重疊度是否達到要求，若未達到要求，繼續分配數據，否則停止分配，第13行進行(1+α)n次賦值，保證目標函數滿足第1個約束條件。第16行更新簇中心矩陣Z、視圖權重向量w、視圖下維度的權重向量h。第18行判斷目標函數是否收斂。

COCD算法涉及到的主要計算步驟有以下3步，運行時復雜度可以分析如下：

(1)劃分：將數據分類為k個可重疊的類簇，計算加權距離矩陣，復雜度為O(nk)；再根據加權距離矩陣將數據點進行劃分時，時間復雜度為O((n+αn)×nk)，由于α經常比較小，故復雜度為O(n2k)。

(2)更新簇中心：給定指示矩陣U，更新簇中心就是在同一個類簇中找到數據對象的均值。因此，對于k個類簇，這一步的計算復雜度是O(nk(|G1|+|G2|))。

(3)更新視圖權重w及視圖維度權重h：給定U，Z與h，根據式(5)更新w，只需遍歷整個數據集一次來更新h，因此此步驟的復雜度為O(nk(|G1|+|G2|));給定U,Z與w，根據式(5)更新h，同理，只需遍歷整個數據集一次來更新h，因此此步驟的復雜度為O(nk(|G1|+|G2|))。

如果聚類過程需要td次迭代才收斂，則該算法的總計算復雜度為max(O(tdnk(|G1|+|G2|)),O(tdn2k))。COCD算法使目標函數值單調下降，直到其收斂到局部最小值。

4 實驗

為了全面評估COCD的有效性和效率，本節分別在人工和真實數據集上設計了2組實驗。首先描述實驗所用數據集；其次觀察不同參數值對實驗結果的影響，選擇適宜的參數；然后分析算法的可擴展性；最后選取4個典型的社區發現算法及未經3.2節優化的本文低階算法COCD(Naive)與本文算法在人工網絡和在真實網絡上對比算法性能。

4.1 數據集與評價指標

4.1.1 人工網絡數據集

具有基準社區的人工網絡是基于LFR基準[17]生成的，其具有與真實世界網絡類似的特征。通過設置人工網絡的一些重要參數，最終生成了具有5個基準社區結構的人工網絡(syn1～syn5),如表2所示。

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

4.1.2 真實網絡數據集

對已有文獻中所廣泛應用的網絡數據集進行了收集和整理，具體有：Flickr數據集[18]是圖像共享網絡，節點表示用戶，邊是友誼關系，屬性為用戶的圖像標簽，用戶有此標簽屬性給1，否則給0。Amazon數據集來自產品共同購買網絡，可從斯坦福大型網絡數據集獲得，其中節點是產品，共同購買的產品通過邊連接，屬性為產品具有的特征，每個節點都包含多種類型的屬性。Cora是一個論文數據集，本文采用常振超等人[19]的方法，對原始Cora數據集進行精簡，去除了在論文中詞頻統計小于10的單詞，其中，邊是論文之間的引用關系，至少引用一次，兩者之間相互引用均記為一條連接關系，文檔所有者之間相互引用均記為一條連接關系，以文檔所出現的單詞作為文檔的節點屬性。3個真實網絡數據集總結如表3所示。

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

4.1.3 評價指標

本文采用與文獻[2]和文獻[4]中相同的對經典F1分數和NMI(Normalized Mutual Informaiton)分數的改進評價指標平均F1分數和平均NMI分數來進行評估。

4.2 實驗結果與分析

4.2.1 參數設置

COCD算法包括3個重要參數α，η和λ，本小節討論如何在實驗中設置這3個重要參數。參數α是直觀的，允許指定類簇的重疊程度，參數η和λ可以通過實驗來驗證其最優值。用戶可以用經驗知識來估計參數α，如果從經驗知識中獲取不到，也可以通過使用以下討論的啟發式來估計α值。

圖2a和圖2b分別顯示了COCD算法在5個人工數據集上取不同η和λ值時對聚類結果的影響。由于篇幅限制，且使用NMI分數的量化結果與F1分數的一致，故僅將使用F1分數量化的結果表示出來。從圖2能看出，η和λ從0.5變為6的過程中，F1分數的波動不大，即聚類精度對這2個參數不敏感。結果表明COCD算法對參數η和λ具有魯棒性。

4.2.2 可擴展性分析

通過測量在不斷增大規模的人工網絡上的運行時間來評估COCD的可擴展性。為了進行評估，考慮6類基線社區檢測方法：(1)僅使用網絡結構的方法—BIGCLAM(CLuster Affiliation Model for BiG networks)[3]；(2)僅使用節點屬性的方法—MAC(Multi-Assignment Clustering)[6]；(3)將兩者結合的方法—CESNA[7]；(4)考慮了節點屬性以及子空間的算法—EWKM[5]；(5)多視圖聚類算法(不能檢測重疊社區)—TW-K-Means[8]；(6)未經過3.2節優化的算法—COCD(Naive)。

圖3顯示了算法的運行時間與網絡規模的關系。總的來說，本文算法COCD是最快的算法，一小時左右的時間可以處理約30萬個節點；MAC是最慢的，而BIGCLAM比CESNA快，因為它使用與CESNA類似的優化過程，但沒有考慮節點屬性。對于小型網絡(最多17萬個節點)，BIGCLAM比COCD(Naive)更快，但是當網絡規模變大時，COCD(Naive)會更快。此外，COCD(Naive)是沒有經過迭代優化的算法，時間復雜度一般情況下比COCD的小，但對式(4)中帶有約束的目標函數進行最小化時，會形成一類非線性優化問題，使得目標函數的解是未知的，所以本文對指示矩陣U、簇中心矩陣Z以及視圖的相對重要性向量w和視圖下每一維屬性的相對重要性h進行部分優化,達到目標函數最小化的目的。最終通過迭代方法使得目標函數趨于局部極小值。故運行時間會比COCD的長。

Figure 3 Algorithm running time comparison圖3 算法運行時間比較

4.2.3 人工網絡和實際網絡結果分析

與4.1.1節所提出的對比算法一致，比較本文算法與5個對比算法在5個由LFR基準生成的人工網絡數據集和3個真實網絡數據集上的平均F1分數與平均NMI值。結果如表4和表5所示。

Table 4 Average F1-scores and average NMI-scores of algorithms on five synthetic datasets表4 5個人工數據集上各算法的平均F1分數與平均NMI分數

Table 5 Average F1-scores and average NMI-scores of algorithms on real datasets表5 真實數據集上各算法的平均F1分數與平均NMI分數

表4顯示了人工網絡數據集上的實驗結果，COCD在10個案例上有8個都得到了最佳的性能。表5顯示了在真實網絡數據集上的實驗結果，將COCD與沒有節點屬性的BIGCLAM進行比較，注意到COCD得到了更好的性能，因為它結合了來自節點屬性和網絡的信息。同樣，COCD也優于MAC，因為后者只關注節點屬性。自然地，COCD絕不會比僅使用單一信息源的最先進算法表現更差。注意到本文基線算法TW-K-Means在人工數據集和真實網絡數據集上的表現不如CESNA和COCD，這是因為TW-K-Means在進行社區發現時未考慮重疊度的問題，而真實網絡中社區是自然重疊的，故當社區存在重疊情況時檢測效果不佳。此外，在將COCD的性能與同時考慮網絡結構和節點屬性的算法(CESNA)和考慮節點屬性以及子空間的算法(EWKM)和COCD(Naive)的性能進行比較時，也能再次觀察到COCD的強大性能。

COCD在人工數據集上的NMI值和F1分數優于真實數據集上的值，這是無可厚非的。此外，對于真實網絡數據集，COCD在內容共享網絡(如Flickr)上相比社交網絡上性能增益更佳。例如，在Flickr網絡上與除本文算法外性能最佳的算法相比，COCD在平均F1分數和平均NMI分數中分別獲得15%和13%的相對增益，可能的解釋是，在內容共享網絡中，節點的屬性(內容)在連接生成中起著更大的作用。總的來說，在16個案例中,COCD在12個案例上性能最佳。

5 結束語

本文提出了一種新的社區發現算法——COCD算法，融合了2種信息源來對屬性圖進行聚類。該算法可以自適應計算2個視圖的相對重要性，并且還為對應視圖中的每個維度分配權重以及挖掘子空間。這是一種可擴展的算法，用于大型復雜網絡中的重疊社區檢測。實驗表明，在人工網絡數據集和實際網絡數據集上，與之前經典的社區發現算法相比，本文提出的COCD算法都顯示了較好的性能，提高了社區發現的有效性和高效性。