基于成對(duì)約束的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法

丁建立，邵酉辰

(中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

0 引 言

標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[1-3]的時(shí)間復(fù)雜度為近似線性，是現(xiàn)今速度較快的方法。標(biāo)簽傳播算法(label propagation algorithm，LPA)[4]綜合了復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)與傳播特性，提出標(biāo)簽傳播算法(label propagation algorithm，LPA)，但該算法并不能應(yīng)用于重疊社區(qū)檢測(cè)，且由于需要預(yù)先設(shè)定合適的參數(shù)以及在標(biāo)簽傳播過(guò)程中具有隨機(jī)性導(dǎo)致該算法的魯棒性較差。多標(biāo)簽傳播算法(community overlap pro-pagation algorithm，COPRA)[5]通過(guò)改進(jìn)LPA算法實(shí)現(xiàn)重疊社區(qū)檢測(cè)，但該類算法也同時(shí)繼承了LPA算法隨機(jī)性強(qiáng)、魯棒性差的特點(diǎn)。基于標(biāo)簽傳播增益的分層算法[6]，提高了COPRA算法的魯棒性和準(zhǔn)確性，但同時(shí)也增加了算法的時(shí)間復(fù)雜度。優(yōu)化標(biāo)簽傳播過(guò)程的算法[7]，通過(guò)對(duì)節(jié)點(diǎn)預(yù)排序降低了算法的隨機(jī)性，又通過(guò)設(shè)置最大社區(qū)節(jié)點(diǎn)數(shù)提高了結(jié)果的穩(wěn)定性。上述方法均為無(wú)監(jiān)督算法，僅依賴于網(wǎng)絡(luò)結(jié)構(gòu)來(lái)進(jìn)行社區(qū)劃分，但是真實(shí)的網(wǎng)絡(luò)復(fù)雜度較高，社區(qū)結(jié)構(gòu)較模糊，導(dǎo)致傳統(tǒng)方法在某些重疊度較高、社區(qū)結(jié)構(gòu)不清晰的情況下檢測(cè)準(zhǔn)確性很低。在非重疊社區(qū)發(fā)現(xiàn)領(lǐng)域已經(jīng)有學(xué)者嘗試使用先驗(yàn)知識(shí)來(lái)指導(dǎo)社區(qū)劃分，基于節(jié)點(diǎn)相似度的半監(jiān)督社區(qū)發(fā)現(xiàn)算法[8]通過(guò)衍生規(guī)則對(duì)成對(duì)約束進(jìn)行擴(kuò)展，但其納入全部的成對(duì)約束信息，算法代價(jià)較大?；谥鲃?dòng)學(xué)習(xí)的糾錯(cuò)式半監(jiān)督社區(qū)發(fā)現(xiàn)算法[9]，在聚類的過(guò)程中加入成對(duì)約束，通過(guò)糾正錯(cuò)誤的劃分使網(wǎng)絡(luò)具有更明顯的塊結(jié)構(gòu)，在保證算法精度的情況下大大降低了先驗(yàn)信息的所需數(shù)量。

基于此，本文提出一種基于成對(duì)約束的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法(PCMLPA)，引入成對(duì)約束指導(dǎo)重疊社區(qū)發(fā)現(xiàn)的過(guò)程，提高算法的準(zhǔn)確性；提出約束集生成策略用于查找和擴(kuò)展約束，提高標(biāo)記的利用效率；基于COPRA算法改進(jìn)節(jié)點(diǎn)的更新順序，在保證算法較低時(shí)間復(fù)雜度的同時(shí)，解決COPRA魯棒性差的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，本文方法在引入較少約束情形下具有更高的準(zhǔn)確性，且魯棒性強(qiáng)。

1 相關(guān)方法概述

1.1 COPRA核心思想

多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)算法(COPRA)[5]的核心思想為：一個(gè)節(jié)點(diǎn)的標(biāo)簽由其鄰居節(jié)點(diǎn)決定，一個(gè)節(jié)點(diǎn)可以擁有多個(gè)標(biāo)簽，迭代結(jié)束后對(duì)節(jié)點(diǎn)依據(jù)標(biāo)簽進(jìn)行社區(qū)劃分。為了避免所有節(jié)點(diǎn)經(jīng)標(biāo)簽傳播擁有全部的標(biāo)簽混淆為一個(gè)共同的大社區(qū)，文獻(xiàn)[5]通過(guò)引入從屬系數(shù)b(belonging coefficient)來(lái)衡量節(jié)點(diǎn)x對(duì)社區(qū)(標(biāo)簽)c的歸屬程度，公式表達(dá)為

(1)

其中，bt(c,x) 表示第t次迭代時(shí)節(jié)點(diǎn)x對(duì)于社區(qū)c的從屬系數(shù)，N(x) 表示x的鄰居節(jié)點(diǎn)集合， ∑y∈N(x)bt-1(c,y) 表示第t-1次迭代時(shí)x的全部鄰居節(jié)點(diǎn)的標(biāo)簽及其從屬系數(shù)的組合。文獻(xiàn)[5]通過(guò)引入?yún)?shù)v(表示每個(gè)節(jié)點(diǎn)最多屬于v個(gè)社區(qū))，在每次迭代傳播的過(guò)程中將從屬系數(shù)b小于閾值(1/v)的標(biāo)簽刪除，若b均小于閾值則保留b最大的標(biāo)簽，又若b最大值有多個(gè)則隨機(jī)選取保留其一。

1.2 LeaderRank算法內(nèi)涵

LeaderRank算法[10]，通過(guò)添加與其它全部節(jié)點(diǎn)相連接的節(jié)點(diǎn)g(ground node)，將網(wǎng)絡(luò)轉(zhuǎn)化為強(qiáng)連接圖，從而可以得到唯一的排序結(jié)果。文獻(xiàn)[10]將節(jié)點(diǎn)LeaderRank值(LR值)更新策略用公式表達(dá)為

(2)

其中，si(t+1) 表示第t+1次迭代時(shí)節(jié)點(diǎn)i的LR值，N(i) 表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合，kj表示節(jié)點(diǎn)j的度數(shù)，sj(t) 表示第t次迭代時(shí)節(jié)點(diǎn)j的LR值。收斂狀態(tài)下LR值S的計(jì)算公式表達(dá)為

(3)

其中，Si表示節(jié)點(diǎn)i收斂狀態(tài)下的LR值，si(tc) 表示收斂次數(shù)tc時(shí)的經(jīng)式(2)算得的結(jié)果，sg(tc) 表示收斂狀態(tài)下節(jié)點(diǎn)g的LR值。

2 基于成對(duì)約束的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法

2.1 約束集生成過(guò)程

2.1.1 成對(duì)約束特征

給定復(fù)雜網(wǎng)絡(luò)G=(V，E)，V表示節(jié)點(diǎn)集，有節(jié)點(diǎn)vi∈V，E表示邊集，有eij∈E表示網(wǎng)絡(luò)中節(jié)點(diǎn)vi與節(jié)點(diǎn)vj的連邊。半監(jiān)督成對(duì)約束通常采用以下兩種標(biāo)記：

(1)must-link約束：標(biāo)識(shí)兩個(gè)節(jié)點(diǎn)屬于同一社區(qū)。定義Cy表示must-link約束集，有 (vi,vj)∈Cy,i≠j表示節(jié)點(diǎn)vi與vj必須劃分給同一社區(qū)；

(2)cannot-link約束：標(biāo)識(shí)兩個(gè)節(jié)點(diǎn)屬于不同社區(qū)。定義Cn表示cannot-link約束集，有 (vi,vj)∈Cn,i≠j表示節(jié)點(diǎn)vi與vj必須劃分給不同的社區(qū)。

成對(duì)約束在非重疊社區(qū)發(fā)現(xiàn)算法的應(yīng)用中，must-link約束具有傳遞性，因而可以通過(guò)衍生關(guān)系規(guī)則[4]來(lái)對(duì)標(biāo)記進(jìn)行推理擴(kuò)展，即3個(gè)節(jié)點(diǎn)vi,vj和vk，若存在 (vi,vj)∈Cy， (vi,vk)∈Cy則有 (vj,vk)∈Cy。 然而將成對(duì)約束引入重疊社區(qū)發(fā)現(xiàn)算法中，則不具有上述傳遞性，對(duì)于節(jié)點(diǎn)vi,vj和vk，存在 (vi,vj)∈Cy， (vi,vk)∈Cy， 無(wú)法推理得出 (vj,vk)∈Cy， 示例如圖1所示。

圖1 成對(duì)約束的衍生示例

圖1中m表示兩節(jié)點(diǎn)為must-link約束，從中可以看出在社區(qū)可重疊情況下，只給定 (vi,vj)∈Cy， (vi,vk)∈Cy， 并不能推理得出 (vj,vk)∈Cy。 當(dāng)處理重疊度較高的網(wǎng)絡(luò)時(shí)，上述情況將會(huì)更加頻繁的發(fā)生，即使隨機(jī)引入更多的成對(duì)約束也未必能夠給算法帶來(lái)更好的效果。

2.1.2 約束集生成過(guò)程

定義開(kāi)放三元組(open triad)，給定3個(gè)節(jié)點(diǎn)vi,vj和vk，若其中兩對(duì)節(jié)點(diǎn)有確定的must-link或cannot-link約束，剩余一對(duì)沒(méi)有約束，則稱節(jié)點(diǎn)vi,vj和vk構(gòu)成開(kāi)放三元組。

圖2 初始約束集擴(kuò)展示例

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

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

步驟2 將兩個(gè)小型初始約束集轉(zhuǎn)換為圖(約束為邊)，并在其中查找開(kāi)放三元組，對(duì)于缺少邊的節(jié)點(diǎn)約束到PC_data中查找結(jié)果；

步驟3 將步驟2的查找結(jié)果添加到對(duì)應(yīng)的must-link初始集合或cannot-link初始集合中；

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

2.2 改進(jìn)多標(biāo)簽傳播算法

為了優(yōu)化COPRA算法社區(qū)劃分結(jié)果不穩(wěn)定、魯棒性差的問(wèn)題，對(duì)其標(biāo)簽傳播細(xì)節(jié)提出以下3點(diǎn)改進(jìn)：

(1)節(jié)點(diǎn)的更新順序(node update order，U)，采用1.2節(jié)介紹的LR值計(jì)算方法來(lái)衡量網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，并降序排列作為節(jié)點(diǎn)的更新順序；

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

(4)

其中，δ(i)，δ(j) 分別表示節(jié)點(diǎn)i，j的所有鄰居節(jié)點(diǎn)和自身節(jié)點(diǎn)的集合， |δ(i)| 表示集合中的節(jié)點(diǎn)個(gè)數(shù)。

(3)標(biāo)簽傳播概率，P(i,j) 表示節(jié)點(diǎn)j的標(biāo)簽傳播到節(jié)點(diǎn)i的概率，P(i,j) 的值取決于節(jié)點(diǎn)相似度Sij和鄰接矩陣?(i,j)， 公式表達(dá)為

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

(5)

其中， ?是網(wǎng)絡(luò)的鄰接矩陣表示，若節(jié)點(diǎn)i與j間有連邊則?(i,j)=1， 反之為0。

為了優(yōu)化COPRA算法社區(qū)劃分結(jié)果準(zhǔn)確性不高的問(wèn)題，提出基于成對(duì)約束的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法(PCMLPA)。結(jié)合2.1.2節(jié)方法所生成的約束集合，令單一節(jié)點(diǎn)所屬的最大社區(qū)數(shù)為v，本文提出的基于成對(duì)約束的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法(PCMLPA)具體步驟如下：

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

特別地，對(duì)于約束的處理機(jī)制有如下兩個(gè)方面：

(1)對(duì)于每對(duì)must-link約束的節(jié)點(diǎn)，應(yīng)保證其從屬系數(shù)b最大的標(biāo)簽相同，若不同則在不含cannnot-link約束的節(jié)點(diǎn)標(biāo)簽情況下復(fù)制交換從屬系數(shù)b最大的標(biāo)簽，并更新bt(c,x)；

(2)對(duì)于每對(duì)cannnot-link約束的節(jié)點(diǎn)，應(yīng)保證二者不具有相同的標(biāo)簽，若含有同一標(biāo)簽則將該標(biāo)簽于相應(yīng)從屬系數(shù)較小的一方中移除，并更新bt(c,x)。

綜上所述，基于成對(duì)約束的多標(biāo)簽傳播社區(qū)發(fā)現(xiàn)方法對(duì)應(yīng)的處理流程如圖3所示。

圖3 PCMLPA流程

3 實(shí)驗(yàn)與結(jié)果分析

本節(jié)旨在驗(yàn)證本文提出的PCMLPA方法較現(xiàn)有無(wú)監(jiān)督重疊社區(qū)發(fā)現(xiàn)算法具有更高性能，并通過(guò)實(shí)驗(yàn)說(shuō)明引入成對(duì)約束的量級(jí)對(duì)于重疊社區(qū)發(fā)現(xiàn)效果的影響。

3.1 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)數(shù)據(jù)集選擇人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)兩種類型。

(1)人工合成網(wǎng)絡(luò)：使用LFR[11]基準(zhǔn)網(wǎng)絡(luò)生成程序生成兩種不同大小的合成網(wǎng)絡(luò)LFR-1000和LFR-5000，參數(shù)設(shè)置見(jiàn)表1。

其中混合參數(shù)μ表示社區(qū)間邊與社區(qū)內(nèi)邊的比值，值越大社區(qū)內(nèi)連通性越弱，社區(qū)結(jié)構(gòu)越模糊。通常不同的參數(shù)，如網(wǎng)絡(luò)大小、社區(qū)規(guī)模、混合參數(shù)和重疊節(jié)點(diǎn)所屬的社區(qū)數(shù)目(社區(qū)重疊度)等，會(huì)影響算法性能評(píng)估的結(jié)果。

(2)真實(shí)網(wǎng)絡(luò)：選取3個(gè)有社區(qū)標(biāo)注的真實(shí)網(wǎng)絡(luò)(SNAP Datasets)：來(lái)自Amazon.com的共同購(gòu)買網(wǎng)絡(luò)，來(lái)自YouTube的友誼網(wǎng)絡(luò)和來(lái)自DBLP的科學(xué)合作網(wǎng)絡(luò)，統(tǒng)計(jì)數(shù)據(jù)見(jiàn)表2。

表1 人工網(wǎng)絡(luò)的參數(shù)設(shè)置

表2 真實(shí)網(wǎng)絡(luò)的數(shù)據(jù)統(tǒng)計(jì)

其中經(jīng)預(yù)處理消除極小社區(qū)，Amazon和YouTube刪除節(jié)點(diǎn)個(gè)數(shù)小于5的社區(qū)，DBLP刪除節(jié)點(diǎn)個(gè)數(shù)小于10的社區(qū)。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

由于實(shí)驗(yàn)數(shù)據(jù)集中的社區(qū)結(jié)構(gòu)已知，故使用歸一化互信息NMI[12]來(lái)驗(yàn)證算法的準(zhǔn)確性，NMI取值范圍為[0,1]，值越大表明社區(qū)發(fā)現(xiàn)的結(jié)果越準(zhǔn)確，公式表達(dá)為

(6)

其中，x表示真實(shí)的社區(qū)結(jié)構(gòu)，y表示實(shí)驗(yàn)的社區(qū)劃分結(jié)果。

考慮到引入相同數(shù)量的成對(duì)約束，對(duì)于不同規(guī)模的網(wǎng)絡(luò)影響不同，故使用成對(duì)約束占總體可能組合的比重來(lái)度量引入約束的量級(jí)M，公式表達(dá)為

(7)

3.3 實(shí)驗(yàn)結(jié)果與分析

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

人工合成網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

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

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

由圖4和圖5可得，①網(wǎng)絡(luò)大小方面：網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)由1000增加到5000時(shí)，各算法性能均有所提升；②社區(qū)規(guī)模方面：本文方法準(zhǔn)確性在社區(qū)規(guī)模較大(c:20-100)時(shí)較其它算法表現(xiàn)最佳，而另外3種基準(zhǔn)算法則表現(xiàn)不一；③社區(qū)重疊度方面：伴隨著重疊度的遞增各算法的性能隨之下降，但與此同時(shí)本文方法的結(jié)果更穩(wěn)定，在om=8時(shí)表現(xiàn)出了明顯的優(yōu)勢(shì)；④混合參數(shù)方面：隨著μ值的增大，由于社區(qū)內(nèi)的連通性變?nèi)?，各算法的NMI值均有所降低，但本文方法表現(xiàn)出了更高的穩(wěn)定性和準(zhǔn)確性。

真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果見(jiàn)表3。

表3 真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

從表3中可以看出，本文PCMLPA方法在Amazon和DBLP網(wǎng)絡(luò)上具有較高的NMI表現(xiàn)，分析在YouTube網(wǎng)絡(luò)上NMI表現(xiàn)欠佳可能是由于該網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)較為模糊所導(dǎo)致。對(duì)比COPRA、OSLOM、MOSES、PCMLPA(M=0%)4種無(wú)監(jiān)督方法，在社區(qū)重疊度更高、結(jié)構(gòu)更為模糊的YouTube網(wǎng)絡(luò)上，本文方法具有更加優(yōu)秀的表現(xiàn)，在Amazon和DBLP兩個(gè)網(wǎng)絡(luò)上雖然結(jié)果不是最佳，但也幾乎不遜于其它3種算法。對(duì)于添加約束后的PCMLPA方法，隨著約束量級(jí)的增加(1%-5%)，實(shí)驗(yàn)效果穩(wěn)步上升，預(yù)測(cè)加入更多的約束這種趨勢(shì)會(huì)持續(xù)增長(zhǎng)。

4 結(jié)束語(yǔ)

本文提出了一種基于成對(duì)約束的多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)方法，通過(guò)引入編碼為成對(duì)約束的先驗(yàn)知識(shí)來(lái)指導(dǎo)社區(qū)的劃分，討論了約束選擇在非重疊社區(qū)發(fā)現(xiàn)與重疊社區(qū)發(fā)現(xiàn)中應(yīng)用的區(qū)別，并給出了解決方案；改進(jìn)COPRA算法的節(jié)點(diǎn)選擇和標(biāo)簽傳播更新過(guò)程，提高了算法魯棒性和社區(qū)劃分結(jié)果的準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明：一方面，本文方法在不引入成對(duì)約束的情況下，魯棒性更強(qiáng)，對(duì)于社區(qū)結(jié)構(gòu)較為模糊的網(wǎng)絡(luò)劃分準(zhǔn)確性較其它算法有明顯提升；另一方面，實(shí)驗(yàn)結(jié)果驗(yàn)證了使用半監(jiān)督策略尋找重疊社區(qū)的潛力，本文方法在引入5%成對(duì)約束的情況下在人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上均顯著優(yōu)于現(xiàn)有其它無(wú)監(jiān)督的重疊社區(qū)發(fā)現(xiàn)算法，且其性能會(huì)隨著成對(duì)約束數(shù)量的增加而繼續(xù)提高。在未來(lái)的工作中，將致力于應(yīng)用主動(dòng)學(xué)習(xí)的思想來(lái)更加充分、高效地利用盡量少的成對(duì)約束，減少相關(guān)標(biāo)注的壓力的同時(shí)進(jìn)一步提高算法的有效性和準(zhǔn)確性。