基于成對約束的多標簽傳播重疊社區發現方法

丁建立，邵酉辰

(中國民航大學 計算機科學與技術學院，天津 300300)

0 引 言

標簽傳播社區發現算法[1-3]的時間復雜度為近似線性，是現今速度較快的方法。標簽傳播算法(label propagation algorithm，LPA)[4]綜合了復雜網絡的結構與傳播特性，提出標簽傳播算法(label propagation algorithm，LPA)，但該算法并不能應用于重疊社區檢測，且由于需要預先設定合適的參數以及在標簽傳播過程中具有隨機性導致該算法的魯棒性較差。多標簽傳播算法(community overlap pro-pagation algorithm，COPRA)[5]通過改進LPA算法實現重疊社區檢測，但該類算法也同時繼承了LPA算法隨機性強、魯棒性差的特點。基于標簽傳播增益的分層算法[6]，提高了COPRA算法的魯棒性和準確性，但同時也增加了算法的時間復雜度。優化標簽傳播過程的算法[7]，通過對節點預排序降低了算法的隨機性，又通過設置最大社區節點數提高了結果的穩定性。上述方法均為無監督算法，僅依賴于網絡結構來進行社區劃分，但是真實的網絡復雜度較高，社區結構較模糊，導致傳統方法在某些重疊度較高、社區結構不清晰的情況下檢測準確性很低。在非重疊社區發現領域已經有學者嘗試使用先驗知識來指導社區劃分，基于節點相似度的半監督社區發現算法[8]通過衍生規則對成對約束進行擴展，但其納入全部的成對約束信息，算法代價較大。基于主動學習的糾錯式半監督社區發現算法[9]，在聚類的過程中加入成對約束，通過糾正錯誤的劃分使網絡具有更明顯的塊結構，在保證算法精度的情況下大大降低了先驗信息的所需數量。

基于此，本文提出一種基于成對約束的多標簽傳播重疊社區發現方法(PCMLPA)，引入成對約束指導重疊社區發現的過程，提高算法的準確性；提出約束集生成策略用于查找和擴展約束，提高標記的利用效率；基于COPRA算法改進節點的更新順序，在保證算法較低時間復雜度的同時，解決COPRA魯棒性差的問題。實驗結果表明，本文方法在引入較少約束情形下具有更高的準確性，且魯棒性強。

1 相關方法概述

1.1 COPRA核心思想

多標簽傳播重疊社區發現算法(COPRA)[5]的核心思想為：一個節點的標簽由其鄰居節點決定，一個節點可以擁有多個標簽，迭代結束后對節點依據標簽進行社區劃分。為了避免所有節點經標簽傳播擁有全部的標簽混淆為一個共同的大社區，文獻[5]通過引入從屬系數b(belonging coefficient)來衡量節點x對社區(標簽)c的歸屬程度，公式表達為

(1)

其中，bt(c,x) 表示第t次迭代時節點x對于社區c的從屬系數，N(x) 表示x的鄰居節點集合， ∑y∈N(x)bt-1(c,y) 表示第t-1次迭代時x的全部鄰居節點的標簽及其從屬系數的組合。文獻[5]通過引入參數v(表示每個節點最多屬于v個社區)，在每次迭代傳播的過程中將從屬系數b小于閾值(1/v)的標簽刪除，若b均小于閾值則保留b最大的標簽，又若b最大值有多個則隨機選取保留其一。

1.2 LeaderRank算法內涵

LeaderRank算法[10]，通過添加與其它全部節點相連接的節點g(ground node)，將網絡轉化為強連接圖，從而可以得到唯一的排序結果。文獻[10]將節點LeaderRank值(LR值)更新策略用公式表達為

(2)

其中，si(t+1) 表示第t+1次迭代時節點i的LR值，N(i) 表示節點i的鄰居節點集合，kj表示節點j的度數，sj(t) 表示第t次迭代時節點j的LR值。收斂狀態下LR值S的計算公式表達為

(3)

其中，Si表示節點i收斂狀態下的LR值，si(tc) 表示收斂次數tc時的經式(2)算得的結果，sg(tc) 表示收斂狀態下節點g的LR值。

2 基于成對約束的多標簽傳播重疊社區發現方法

2.1 約束集生成過程

2.1.1 成對約束特征

給定復雜網絡G=(V，E)，V表示節點集，有節點vi∈V，E表示邊集，有eij∈E表示網絡中節點vi與節點vj的連邊。半監督成對約束通常采用以下兩種標記：

(1)must-link約束：標識兩個節點屬于同一社區。定義Cy表示must-link約束集，有 (vi,vj)∈Cy,i≠j表示節點vi與vj必須劃分給同一社區；

(2)cannot-link約束：標識兩個節點屬于不同社區。定義Cn表示cannot-link約束集，有 (vi,vj)∈Cn,i≠j表示節點vi與vj必須劃分給不同的社區。

成對約束在非重疊社區發現算法的應用中，must-link約束具有傳遞性，因而可以通過衍生關系規則[4]來對標記進行推理擴展，即3個節點vi,vj和vk，若存在 (vi,vj)∈Cy， (vi,vk)∈Cy則有 (vj,vk)∈Cy。 然而將成對約束引入重疊社區發現算法中，則不具有上述傳遞性，對于節點vi,vj和vk，存在 (vi,vj)∈Cy， (vi,vk)∈Cy， 無法推理得出 (vj,vk)∈Cy， 示例如圖1所示。

圖1 成對約束的衍生示例

圖1中m表示兩節點為must-link約束，從中可以看出在社區可重疊情況下，只給定 (vi,vj)∈Cy， (vi,vk)∈Cy， 并不能推理得出 (vj,vk)∈Cy。 當處理重疊度較高的網絡時，上述情況將會更加頻繁的發生，即使隨機引入更多的成對約束也未必能夠給算法帶來更好的效果。

2.1.2 約束集生成過程

定義開放三元組(open triad)，給定3個節點vi,vj和vk，若其中兩對節點有確定的must-link或cannot-link約束，剩余一對沒有約束，則稱節點vi,vj和vk構成開放三元組。

圖2 初始約束集擴展示例

令所需約束的數量m/對，其中， (vi,vj)∈Cy稱為一對約束。初始約束集的擴展示例如圖2所示，該策略可描述為：

步驟1 在原始約束集中隨機選擇兩個小型的初始約束集，包括must-link初始集合Cy和cannot-link初始集合Cn；

步驟2 將兩個小型初始約束集轉換為圖(約束為邊)，并在其中查找開放三元組，對于缺少邊的節點約束到PC_data中查找結果；

步驟3 將步驟2的查找結果添加到對應的must-link初始集合或cannot-link初始集合中；

步驟4 重復步驟2～步驟3，直至所選取的約束數量達到m，得到must-link選擇集合和cannot-link選擇集合。

2.2 改進多標簽傳播算法

為了優化COPRA算法社區劃分結果不穩定、魯棒性差的問題，對其標簽傳播細節提出以下3點改進：

(1)節點的更新順序(node update order，U)，采用1.2節介紹的LR值計算方法來衡量網絡中節點的重要性，并降序排列作為節點的更新順序；

(2)鄰居節點的遍歷順序(traversal order of neighbor nodes，T)，采用相似度降序排列作為鄰居節點的遍歷順序，節點相似度計算公式為

(4)

其中，δ(i)，δ(j) 分別表示節點i，j的所有鄰居節點和自身節點的集合， |δ(i)| 表示集合中的節點個數。

(3)標簽傳播概率，P(i,j) 表示節點j的標簽傳播到節點i的概率，P(i,j) 的值取決于節點相似度Sij和鄰接矩陣?(i,j)， 公式表達為

P(i,j)=Sij×?(i,j)

(5)

其中， ?是網絡的鄰接矩陣表示，若節點i與j間有連邊則?(i,j)=1， 反之為0。

為了優化COPRA算法社區劃分結果準確性不高的問題，提出基于成對約束的多標簽傳播重疊社區發現方法(PCMLPA)。結合2.1.2節方法所生成的約束集合，令單一節點所屬的最大社區數為v，本文提出的基于成對約束的多標簽傳播重疊社區發現方法(PCMLPA)具體步驟如下：

首先，初始化節點標簽(cx,1)，對于must-link約束標注的每對節點復制交換標簽并歸一化標簽的社區從屬系數，使得Σc∈label(x)b(c,x)=1； 其次，依據節點的更新順序U，依次選取當前節點，并識別該節點全部的鄰居節點，依據鄰居節點的遍歷順序T，依次據式(1)對該節點進行標簽傳播，更新節點的標簽數組label_array，其間添加所有來自must-link約束鄰居節點的標簽，刪除所有來自cannot-link約束鄰居節點的標簽；再次，每更新完一個節點的全部標簽，需對其進行過濾和歸一化處理，刪除從屬系數b<1/v的標簽，若該節點的所有標簽均被過濾，則保留當前b最大的標簽，后對其進行二次歸一化，完成一輪全部節點的更新表示經過一次標簽傳播迭代；最后，當最近兩次迭代的結果中標簽的分布不再變化時，迭代停止，相同標簽的節點劃分為同一社區，并將結果做去重、歸并處理，輸出社區劃分結果。

特別地，對于約束的處理機制有如下兩個方面：

(1)對于每對must-link約束的節點，應保證其從屬系數b最大的標簽相同，若不同則在不含cannnot-link約束的節點標簽情況下復制交換從屬系數b最大的標簽，并更新bt(c,x)；

(2)對于每對cannnot-link約束的節點，應保證二者不具有相同的標簽，若含有同一標簽則將該標簽于相應從屬系數較小的一方中移除，并更新bt(c,x)。

綜上所述，基于成對約束的多標簽傳播社區發現方法對應的處理流程如圖3所示。

圖3 PCMLPA流程

3 實驗與結果分析

本節旨在驗證本文提出的PCMLPA方法較現有無監督重疊社區發現算法具有更高性能，并通過實驗說明引入成對約束的量級對于重疊社區發現效果的影響。

3.1 數據集與實驗設置

實驗數據集選擇人工合成網絡和真實網絡兩種類型。

(1)人工合成網絡：使用LFR[11]基準網絡生成程序生成兩種不同大小的合成網絡LFR-1000和LFR-5000，參數設置見表1。

其中混合參數μ表示社區間邊與社區內邊的比值，值越大社區內連通性越弱，社區結構越模糊。通常不同的參數，如網絡大小、社區規模、混合參數和重疊節點所屬的社區數目(社區重疊度)等，會影響算法性能評估的結果。

(2)真實網絡：選取3個有社區標注的真實網絡(SNAP Datasets)：來自Amazon.com的共同購買網絡，來自YouTube的友誼網絡和來自DBLP的科學合作網絡，統計數據見表2。

表1 人工網絡的參數設置

表2 真實網絡的數據統計

其中經預處理消除極小社區，Amazon和YouTube刪除節點個數小于5的社區，DBLP刪除節點個數小于10的社區。

3.2 評價標準

由于實驗數據集中的社區結構已知，故使用歸一化互信息NMI[12]來驗證算法的準確性，NMI取值范圍為[0,1]，值越大表明社區發現的結果越準確，公式表達為

(6)

其中，x表示真實的社區結構，y表示實驗的社區劃分結果。

考慮到引入相同數量的成對約束，對于不同規模的網絡影響不同，故使用成對約束占總體可能組合的比重來度量引入約束的量級M，公式表達為

(7)

3.3 實驗結果與分析

選取COPRA[5]和兩種主流重疊社區發現方法OSLOM[13]、MOSES[14]作為基準算法，與本文PCMLPA方法在相同數據集上進行對比實驗。其中，OSLOM算法是基于局部擴展的重疊社區發現方法，MOSES算法是基于節點隸屬度的重疊社區發現方法。設置COPRA和本文PCMLPA的參數v=8。特別地，由于COPRA是非確定性算法，在實驗中的結果波動較大因而取10次COPRA的運行結果NMI的平均值，又本文PCMLPA(M>0)方法中初始小型約束集的選擇是隨機的故重復實驗取10次NMI的平均值。

人工合成網絡的實驗結果如圖4和圖5所示。

圖4 算法在LFR-1000上的NMI比較

圖5 算法在LFR-5000上的NMI比較

由圖4和圖5可得，①網絡大小方面：網絡中節點個數由1000增加到5000時，各算法性能均有所提升；②社區規模方面：本文方法準確性在社區規模較大(c:20-100)時較其它算法表現最佳，而另外3種基準算法則表現不一；③社區重疊度方面：伴隨著重疊度的遞增各算法的性能隨之下降，但與此同時本文方法的結果更穩定，在om=8時表現出了明顯的優勢；④混合參數方面：隨著μ值的增大，由于社區內的連通性變弱，各算法的NMI值均有所降低，但本文方法表現出了更高的穩定性和準確性。

真實網絡的實驗結果見表3。

表3 真實網絡的實驗結果

從表3中可以看出，本文PCMLPA方法在Amazon和DBLP網絡上具有較高的NMI表現，分析在YouTube網絡上NMI表現欠佳可能是由于該網絡的社區結構較為模糊所導致。對比COPRA、OSLOM、MOSES、PCMLPA(M=0%)4種無監督方法，在社區重疊度更高、結構更為模糊的YouTube網絡上，本文方法具有更加優秀的表現，在Amazon和DBLP兩個網絡上雖然結果不是最佳，但也幾乎不遜于其它3種算法。對于添加約束后的PCMLPA方法，隨著約束量級的增加(1%-5%)，實驗效果穩步上升，預測加入更多的約束這種趨勢會持續增長。

4 結束語

本文提出了一種基于成對約束的多標簽傳播重疊社區發現方法，通過引入編碼為成對約束的先驗知識來指導社區的劃分，討論了約束選擇在非重疊社區發現與重疊社區發現中應用的區別，并給出了解決方案；改進COPRA算法的節點選擇和標簽傳播更新過程，提高了算法魯棒性和社區劃分結果的準確度。實驗結果表明：一方面，本文方法在不引入成對約束的情況下，魯棒性更強，對于社區結構較為模糊的網絡劃分準確性較其它算法有明顯提升；另一方面，實驗結果驗證了使用半監督策略尋找重疊社區的潛力，本文方法在引入5%成對約束的情況下在人工合成網絡和真實網絡上均顯著優于現有其它無監督的重疊社區發現算法，且其性能會隨著成對約束數量的增加而繼續提高。在未來的工作中，將致力于應用主動學習的思想來更加充分、高效地利用盡量少的成對約束，減少相關標注的壓力的同時進一步提高算法的有效性和準確性。