采用PageRank和節(jié)點聚類系數(shù)的標簽傳播重疊社區(qū)發(fā)現(xiàn)算法*

馬 健，劉 峰，李紅輝，樊建平

(北京交通大學 計算機與信息技術學院， 北京 100044)

社區(qū)結構(community)是復雜網絡所呈現(xiàn)的重要特征之一，從某種意義上說，整個網絡由若干社區(qū)構成，具有社區(qū)內部節(jié)點之間連接比較密集，不同社區(qū)節(jié)點之間連接比較稀疏的特點[1]。復雜網絡社區(qū)發(fā)現(xiàn)問題就是要揭示出復雜網絡中存在的各個社區(qū)。從社區(qū)之間是否重疊的角度來看,社區(qū)結構是可以重疊的。例如人類社會關系網中的一個人可以擁有多個朋友圈，Internet中，一個路由器可以連接不同的局域網，在神經網絡中，一個神經元可以屬于不同的神經系統(tǒng)。

重疊社區(qū)的發(fā)現(xiàn)算法可以分為：基于派系過濾算法(Clique Percolation Method, CPM)的重疊社區(qū)發(fā)現(xiàn)算法，它將網絡看作是完全連通子圖(clique)的集合[2-3]。基于優(yōu)化函數(shù)的重疊社區(qū)發(fā)現(xiàn)算法[4-5]，其中，Lancichinetti等[4]提出了LFM (Local Fitness Method)算法，該算法既可以發(fā)現(xiàn)層次社區(qū)又可以發(fā)現(xiàn)重疊社區(qū)。基于邊的重疊社區(qū)發(fā)現(xiàn)算法[6-7]，基于標簽傳播的社區(qū)發(fā)現(xiàn)算法，Gregory等[8]提出了重疊社區(qū)發(fā)現(xiàn)算法(Community Overlap PRopagation Algorithm， COPRA)。Wu等[9]提出了基于均衡多標簽傳播的重疊社團發(fā)現(xiàn)算法(Balanced Multi-Label Propagation Algorithm, BMLPA)算法，定義了粗糙核的概念對節(jié)點的標簽進行初始化，通過更改標簽更新時的參數(shù)改進算法。張昌理等[10]提出了多標簽傳播重疊社區(qū)發(fā)現(xiàn)算法COPRA-EP，算法利用節(jié)點信息熵和節(jié)點的局部相關性進行研究。Cui等[11]從網絡中發(fā)現(xiàn)所有最大子圖，然后通過兩個相鄰最大子圖的聚類系數(shù)來合并它們。Mohan等[12]提出了一個分布式和可擴展的模型來最大化信息的擴散，通過將圖劃分為社區(qū)并尋找每個社區(qū)中有影響的節(jié)點來檢測社區(qū)，模型使用PageRank算法在每個社區(qū)中尋找有影響的節(jié)點。孫道平等[13]提出了一種算法計算網絡節(jié)點的聚類系數(shù)，并選擇具有最大聚類系數(shù)的節(jié)點來更新其在傳播過程中的標簽。Chen等[14]提出了基于節(jié)點層次和標簽傳播增益的重疊社區(qū)發(fā)現(xiàn)算法，算法提出了新的多標簽更新規(guī)則，設計節(jié)點之間標簽傳播增益得到重疊社區(qū)。Xie等[15]提出了一種SLPA算法。

本文提出了一種基于PageRank和節(jié)點聚類系數(shù)的重疊標簽傳播算法(Community Overlap PRopagation Algorithm based on PageRank and Clustering coefficient,COPRAPC)。該算法在傳播節(jié)點的社區(qū)標簽時按節(jié)點影響力的大小進行排序，并且根據(jù)節(jié)點的聚類系數(shù)決定傳播的閾值，最后通過一系列實驗進行驗證，實驗結果表明所提出的重疊社區(qū)檢測算法是可行且有效的。

1 COPRA算法

1.1 COPRA算法描述

COPRA算法(見圖1)在標簽傳播算法(Label Propagation Algorithm， LPA)算法基礎上改進解決重疊社區(qū)發(fā)現(xiàn)的問題，每個節(jié)點擁有多個標簽(label)和隸屬度(belonging coefficients)，所有隸屬度的和等于1，標簽采用同步更新的方式，用每個節(jié)點的鄰居節(jié)點的標簽更新該節(jié)點，屬于相同社區(qū)標簽的隸屬度相加并標準化，如式(1)所示，隸屬度小于1/v的標簽將從標簽列表中刪除，閾值v用來控制一個節(jié)點所屬的社區(qū)數(shù)。COPRA標簽傳播算法的時間復雜度為O(vmlog(vm/n))，當v取較小值時，整個算法復雜度為線性時間復雜度。

(1)

(a) 第1次迭代(a) Iteration 1 (b) 第2次迭代(b) Iteration 2

(c) 第3次迭代(c) Iteration 3 (d) 第4次迭代(d) Iteration 4圖1 COPRA 算法Fig.1 COPRA algorithm

1.2 評價函數(shù)

Qov是Nicosia等將Q函數(shù)擴展提出的能夠評價重疊社區(qū)的評價函數(shù)[16]。Qov越大，社區(qū)結構越明顯。

(2)

其中，

δ(Ci,Cj,C)=F(αi,c,αj,c)

f(x)=2px-p,p=30

EQ是評估重疊社區(qū)的另一個度量標準，EQ值越大，社區(qū)的結構越明顯。表達式如下[3]：

(3)

Lancichinetti等將標準互信息(Normalized Mutual Information, NMI)擴展為能夠評價重疊社區(qū)的一種評價指標[2]。

(4)

2 COPRAPC算法

2.1 算法思想及描述

COPRAPC算法和其他重疊標簽傳播算法的不同之處在于算法采用不同的閾值來限制每個節(jié)點擁有最多標簽的數(shù)量值，每個節(jié)點可能出現(xiàn)在多個社區(qū)中，社區(qū)邊緣節(jié)點擁有較小聚類系數(shù)一般是重疊節(jié)點，社區(qū)內部節(jié)點擁有大聚類系數(shù)往往是非重疊節(jié)點，社區(qū)邊緣節(jié)點比社區(qū)內部屬于更多的社區(qū)。小的聚類系數(shù)做閾值可以保留節(jié)點更多的標簽，而大的聚類系數(shù)可以刪除節(jié)點更多的標簽，重疊的節(jié)點可以比非重疊的節(jié)點保留更多的標簽。此外，復雜網絡的小世界特性決定了節(jié)點具有較高聚類系數(shù)，從而避免了傳播過程中節(jié)點的標簽對過多的問題。

COPRAPC算法采用同步更新策略。對于同步策略來說，可以比異步方式提供更穩(wěn)定的結果，但是同步方案需要更多的迭代次數(shù)。

在COPRA算法中，每個節(jié)點都有一個標簽，在傳播過程中，節(jié)點標簽在沒有特定序列的情況下更新。這種隨機策略導致運行結果不穩(wěn)定。如圖1(c)中所示的COPRA算法中，在這次迭代之后，節(jié)點a、b、c和d已經形成了一個社區(qū)。如果算法選擇節(jié)點e或g，用節(jié)點a的標簽替換它的標簽，然后更新節(jié)點f的標簽，那么，所有節(jié)點都使用c作為它們的標簽，所有的節(jié)點將被劃分為一個社區(qū)，結果導致整個網絡在一個社區(qū)中。如果首先更新節(jié)點f的標簽，將得到正確的分區(qū)結果。

圖2顯示了兩個非重疊社區(qū)C1和C2迭代之后，如果節(jié)點d,e,f被分配到社區(qū)C2，此時更新節(jié)點g，將得到正確的社區(qū)分區(qū)，但如果更新節(jié)點b或c的標簽并選擇節(jié)點d和e作為它的標簽，所有節(jié)點將擁有相同的標簽，結果是所有節(jié)點被劃分到相同的社區(qū)。

圖2 COPRAPC算法實例Fig.2 Example of COPRAPC propagation

上述兩個例子說明COPRA算法對節(jié)點更新序列很敏感，不是所有這些節(jié)點都具有相同的優(yōu)先級。在社區(qū)之間的節(jié)點的影響力總是比社區(qū)內部的節(jié)點要低。PageRank值反映了這個特性，本文使用排名方法PageRank算法[17]對節(jié)點進行排序。首先，將無向圖轉換為有向圖，將無向圖中的邊轉換為具有兩個相反方向的弧。PageRank的較小值往往位于社區(qū)中心，PageRank值小的節(jié)點優(yōu)先于PageRank值較大的節(jié)點，即

(5)

其中，α參數(shù)為0.85，v′是節(jié)點v的鄰居，degress(v′)為節(jié)點v′的度。

節(jié)點的PageRank值:PR(a)=0.146 6,PR(b)=0.147 6,PR(c)=0.147 6,PR(d)=0.152 0,PR(e)=0.152 0,PR(f)=0.107 6,PR(g)=0.146 6。節(jié)點在以下序列中更新它們的標簽：f、a、g、b、c、d和e，可以很容易地得到正確的結果。

2.2 修改傳播門限參數(shù)

在COPRA算法中，使用標簽列表(c,b)表示每個節(jié)點擁有的標簽，其中c表示一個標簽(label)，b表示隸屬度。如果b<1/v，從節(jié)點標簽列表中刪除(c,b)。在重疊的社區(qū)中，每個節(jié)點可能屬于多個社區(qū)。參數(shù)v控制重疊的社區(qū)數(shù)目。也就是說，參數(shù)v限制節(jié)點所屬的社區(qū)最大數(shù)量。如果v太大，則可能導致網絡中節(jié)點的標簽對過少，節(jié)點容易被劃分到一個社區(qū)，如果v太小，則會導致網絡中節(jié)點的標簽對過多。參數(shù)v的選擇能夠影響標簽傳播算法重疊社區(qū)發(fā)現(xiàn)的準確性，由于每個節(jié)點所屬社區(qū)數(shù)目是不相同的，因此，本文提出了一種新的標簽傳播算法，根據(jù)不同的節(jié)點選擇不同的參數(shù)。

在網絡中，節(jié)點vi的鄰居節(jié)點之間實際存在的邊數(shù)和可能存在最多邊數(shù)的比值為節(jié)點vi的聚類系數(shù)[18]，每個節(jié)點vi鄰居節(jié)點之間可能最多是ki×(ki-1)/2條邊。節(jié)點vi的聚類系數(shù)如式(6)所示。

(6)

其中，Ei表示連接到節(jié)點vi的每個相鄰節(jié)點的邊數(shù)，ki表示節(jié)點vi所有相鄰節(jié)點的個數(shù)。聚類系數(shù)Ci總是在0至1之間。

COPRAPC算法允許社區(qū)重疊，每個節(jié)點可能出現(xiàn)在多個社區(qū)中。社區(qū)邊緣節(jié)點總是重疊節(jié)點，社區(qū)中間節(jié)點往往是非重疊節(jié)點，重疊節(jié)點聚類系數(shù)往往小于非重疊節(jié)點，重疊節(jié)點的聚類系數(shù)較小通常處在社區(qū)的邊緣，非重疊社區(qū)的節(jié)點都在社區(qū)中間聚類系數(shù)較大，換句話說，一個社區(qū)邊緣節(jié)點擁有小聚類系數(shù)可能比社區(qū)中間擁有大聚類系數(shù)屬于更多的社區(qū)。更高的閾值可以刪除節(jié)點更多的標簽，重疊的節(jié)點可以比非重疊的節(jié)點保留更多的標簽。

v是一個與節(jié)點無關的參數(shù)。相反，聚類系數(shù)參數(shù)是一個與節(jié)點相關的參數(shù)，算法設置參數(shù)μ，當節(jié)點的聚類系數(shù)大于μ，閾值設為節(jié)點的聚類系數(shù)，反之，使用先前的值1/v。這樣做的目的是聚類系數(shù)大的節(jié)點一般在社區(qū)內部，往往不是重疊節(jié)點，這樣的節(jié)點設置的門限高，可以去除較多的標簽，而聚類系數(shù)小的節(jié)點一般在社區(qū)的邊緣，容易成為重疊節(jié)點，設置的門限較低可以增加標簽的數(shù)量。但對于聚類系數(shù)非常小的節(jié)點，閾值過低容易產生空的標簽集合，這時就用原來的門限值1/v。

COPRAPC算法描述：

1)初始時，給每個節(jié)點賦予唯一的社區(qū)標簽(cx,1)。

2)對網絡中的節(jié)點按其PageRank值排序。

3)每個節(jié)點x通過最大鄰居的數(shù)量來更新它的標簽。屬于相同社區(qū)的標簽的隸屬度相加并標準化，為了避免最后所有節(jié)點都劃分到同一個社區(qū)，COPRAPC算法使用節(jié)點的聚類系數(shù)來限制每個節(jié)點擁有最多標簽的數(shù)量值。如果節(jié)點的聚類系數(shù)小于參數(shù)μ，仍然使用原來的1/v，如果一個節(jié)點的所有標簽隸屬度都小于傳播參數(shù)，那么隨機選擇一個最大值鄰居的標簽作為該節(jié)點的標簽。最后，當每個標簽包含的節(jié)點數(shù)不變，算法迭代結束，否則，重復步驟3。

4)將所有標簽相同的節(jié)點劃分為同一個社區(qū)。

5)將得到的社區(qū)進行刪除其他社區(qū)的子集，不相連的社區(qū)分裂成更小的社區(qū)。

COPRAPC算法的形式化語言如算法1和算法2所示。

算法1 計算節(jié)點的聚類系數(shù)

算法2 COPRAPC算法

2.3 復雜度分析

1)初始化標簽的時間復雜度為O(n)。

2)設計算單個節(jié)點PageRank值的迭代次數(shù)為t，矩陣相乘時間復雜度為O(n2)，所以計算單個節(jié)點的PageRank值的時間復雜度為O(n2×t)，計算網絡中所有節(jié)點的PageRank值的時間復雜度為O(n3×t)，根據(jù)節(jié)點排序更新序列的時間復雜度為O(n)。

3 實驗分析

為了驗證所提出的COPRAPC算法，將它與幾個重疊社區(qū)的發(fā)現(xiàn)算法進行比較:CPM, LFM, BMLPA和COPRA。

Lancichinetti的NMI已被廣泛用于發(fā)現(xiàn)重疊社區(qū)，因此本文在實驗中采用擴展的NMI作為度量標準。實驗獨立運行COPRA算法20次實驗數(shù)據(jù)，得到平均結果。COPRAPC算法由于標簽選擇的隨機性，本文獨立運行了10次數(shù)據(jù)集取平均結果。CPM算法，k=4, BMPLA 算法，p=0.75。

3.1 LFR基準網絡

LFR基準網絡，該網絡由Lancichinetti等提出，是一類更接近真實網絡的人工網絡，該網絡節(jié)點及社區(qū)模型度呈冪律分布，具有真實世界的網絡特性。N表示節(jié)點數(shù)目，d表示節(jié)點平均度數(shù)，k表示節(jié)點最大度，minc表示最小社區(qū)規(guī)模，maxc表示最大社區(qū)規(guī)模，t1表示節(jié)點度的冪率分布指數(shù)，t2表示社區(qū)規(guī)模的冪率分布指數(shù)，混合參數(shù)mu，on表示重疊節(jié)點的個數(shù)，om表示重疊節(jié)點所屬的社區(qū)個數(shù)，表1和表2為LFR基準網絡的參數(shù)。表1中的社區(qū)分別表示稠密小社區(qū)(Dense Small, DS)，稠密大社區(qū)(Dense Large, DL)，稀疏小社區(qū)(Sparse Small, SS)，稀疏大社區(qū)(Sparse Large, SL)。表1中實驗節(jié)點的聚類系數(shù)都較大，因此設置μ=0。

表1 重疊社區(qū)的LFR基準網絡參數(shù)

表2 非重疊社區(qū)的LFR基準網絡參數(shù)

圖3顯示該算法在實驗中表現(xiàn)良好。隨著參數(shù)on的增大，重疊節(jié)點的數(shù)量越來越多。COPRAPC性能較優(yōu)。

(a) DS網絡的NMI值(a) NMI identified by DS networks

(b) SS網絡的NMI值(b) NMI identified by SS networks

(c) DL網絡的NMI值(c) NMI identified by DL networks

(d) SL網絡的NMI值(d) NMI identified by SL networks圖3 CPM, LFM, COPRA, BMLPA and COPRAPC算法的NMI對比結果Fig.3 The NMI identified by CPM, LFM, COPRA, BMLPA and COPRAPC

表2中的實驗數(shù)據(jù)集節(jié)點的聚類系數(shù)較小，因此設μ=0.1。

上述是一個具有非重疊節(jié)點的社區(qū)網絡。隨著參數(shù)mu的增加，當值mu=0.4時社區(qū)的結構變得模糊，圖4顯示該算法在這些網絡中表現(xiàn)良好。

(a) Network a的NMI值(a) NMI identified by network a

(b) Network b的NMI值(b) NMI identified by network b圖4 CPM, LFM, COPRA, BMLPA and COPRAPC算法的NMI對比結果Fig.4 The NMI identified by CPM, LFM, COPRA, BMLPA and COPRAPC

3.2 真實世界網絡

本文在幾個真實世界復雜網絡上對算法進行測試，實驗采用的數(shù)據(jù)分別是：Newman提供的空手道俱樂部網絡(Zachary′s club network)、海豚網絡(dolphin social network)、美國大學足球聯(lián)盟網絡 (American college football)、爵士音樂網絡(Jazz music)、政治書籍(political books)和郵件網絡(the E-mail network of human interactions)。表3為實驗用到的真實網絡參數(shù)。實驗中，設置參數(shù)μ=0.2。表4和表5分別給出了解情況種算法在個真實世界網絡中的Qov和EQ值。

表3 真實世界網絡參數(shù)

在基準網絡和真實網絡的實驗中，算法的社區(qū)發(fā)現(xiàn)結果是穩(wěn)定的，基于此思想的算法相比其他標簽傳播重疊社區(qū)發(fā)現(xiàn)算法有明顯的提高，和其他重疊算法相比也有較好的挖掘結果，這也說明了基于PageRank和節(jié)點聚類系數(shù)的思路是可行的。

表4 CPM LFM, COPRA, BMLPA and COPRAPC算法的Qov值Tab.4 The Qov values identified by CPM, LFM, COPRA, and COPRAPC

表5 CPM, LFM, COPRA, BMLPA and COPRAC算法的EQ值Tab.5 The EQ values identified by CPM, LFM, COPRA, and COPRAPC

3.3 算法效率比較

改變LFR基準程序的參數(shù)，可以得到不同規(guī)模的人工網絡,在這些網絡上分別運行社區(qū)發(fā)現(xiàn)算法,可以得到算法運行時間的一般規(guī)律,從而能知道各個算法在效率上的差異。本節(jié)使用的LFR程序參數(shù)N=1000～10 000,k=20,kmax=50,cmin=20,cmax=100,t1=2,t2=2,on=0,om=2。圖5顯示了COPRA, BMLPA和COPRAPC算法的執(zhí)行時間，由于CPM，LFM算法的運行時間較長，本文不做比較。COPRAPC算法具有合理的時間復雜度。此外，算法的時間效率和時間復雜度方面，標簽傳播算法具有明顯的優(yōu)勢，本算法的時間在同類算法中也是可接受的。

圖5 算法運行效率對比的實驗結果 Fig.5 Experiment results of runtime efficiency

4 結論

本文提出了一種改進的重疊社區(qū)發(fā)現(xiàn)算法，即基于節(jié)點的PageRank值排序和節(jié)點的聚類系數(shù)標簽傳播算法。節(jié)點標簽的傳播不按隨機順序，而是按照指定節(jié)點的PageRank值的順序傳播，設定節(jié)點聚類系數(shù)閾值對標簽進行更新，進而實現(xiàn)對網絡社區(qū)結構的劃分和網絡重疊節(jié)點的發(fā)現(xiàn)。在許多人工網絡和真實世界網絡的實驗中，基于此思想的算法都取得了相比其他同類算法更好的效果，這也說明了該思路的可行性，同時該算法具有穩(wěn)定的社區(qū)發(fā)現(xiàn)結果。并且該算法的時間效率和復雜度也在可接受的范圍內。