基于LeaderRank和節(jié)點相似性的多標簽傳播重疊社團挖掘算法①

王 林,饒仁杰

(西安理工大學 自動化與信息工程學院,西安 710048)

近年來,隨著科技的快速發(fā)展,對復雜網(wǎng)絡的研究不斷深入,社團結構作為復雜網(wǎng)絡中的重要屬性也逐漸得到人們的重視.所謂社團結構就是：同一社團內(nèi)節(jié)點之間連接緊密,而不同社團內(nèi)節(jié)點之間連接稀疏[1,2].社團挖掘是為了探索和發(fā)現(xiàn)復雜網(wǎng)絡的社團結構,有助于分析網(wǎng)絡的結構和功能,從而發(fā)現(xiàn)網(wǎng)絡中隱含的內(nèi)在規(guī)律,因此社團挖掘具有重要的理論意義和廣泛的應用前景.

隨著研究的不斷深入,許多社團挖掘算法被廣大研究者相繼提出,如基于節(jié)點分裂的GN算法[3],基于模塊度優(yōu)化的FN算法[4]和BGLL算法[5],基于標簽傳播的LPA算法[6]等.其中,LPA算法因為其簡單、高效等優(yōu)勢,得到了人們的普遍關注.但是該算法僅僅只能用于非重疊網(wǎng)絡中,并且該算法存在穩(wěn)定性差和隨機性高的缺陷.然而在真實網(wǎng)絡中社團通常是相互重疊的,如圖1所示,網(wǎng)絡中的陰影節(jié)點同屬于兩個社團,那么這兩個社團就是重疊的,陰影節(jié)點即為重疊節(jié)點.為了能夠挖掘重疊社團結構,Steve在LPA算法的基礎上進行延伸,提出了多標簽傳播COPRA算法[7],該算法允許每個節(jié)點攜帶v個標簽,其繼承了LPA算法的優(yōu)勢,但用于未知網(wǎng)絡時無法預估網(wǎng)絡中節(jié)點所屬的社團個數(shù),假設節(jié)點所屬社團個數(shù)分布不均時,就很難找到一個合適的參數(shù)v,使得算法難以準確的得到社團結構,且COPRA算法同時也繼承了LPA算法的隨機性缺陷,使得劃分的結果非常不穩(wěn)定.Xie等人基于標簽傳播的思想提出SLPA算法[8],算法通過記錄每一個節(jié)點在刷新迭代過程中的歷史標簽序列,利用概率閾值刪除出現(xiàn)頻率小的標簽最終得到社團結構,但該算法仍需要一個合適的概率閾值參數(shù),并且采用的隨機策略將導致結果存在隨機性.

圖1 重疊社團的網(wǎng)絡結構

為了改善現(xiàn)有的基于多標簽傳播算法的因采用隨機策略導致結果不穩(wěn)定,以及需要輸入額外的參數(shù)問題,本文提出一種基于LeaderRank和節(jié)點相似性的多標簽傳播算法,該算法引入LeaderRank算法[9]來衡量網(wǎng)絡中節(jié)點重要性,根據(jù)重要性大小確定節(jié)點的更新序列,并重新設計了標簽的更新策略,使得到的劃分結果更加穩(wěn)定,且該算法無需輸入額外的參數(shù).實驗表明本文算法較現(xiàn)有的多標簽傳播算法相比能夠較準確的得到重疊社團結構.

1 基于LeaderRank和節(jié)點相似性的多標簽傳播重疊社團挖掘算法

本文利用LeaderRank算法對網(wǎng)絡中的節(jié)點的更新順序進行排序,并結合節(jié)點的相似性重新設計了標簽的更新策略提出了基于LeaderRank和節(jié)點相似性的多標簽傳播重疊社團挖掘算法.

1.1 LeaderRank排序算法

由于先更新的節(jié)點影響傳播的較遠,很多重要性較小的節(jié)點在傳播時會反過來影響一些重要性較大的節(jié)點,這樣就造成了標簽的逆向傳播.雖然算法在后續(xù)的迭代過程中可以修正結果,但耗費了大量的時間和更新操作.因此,本文利用LeaderRank排序算法對節(jié)點的更新順序進行排序減少算法不必要的更新和標簽逆流現(xiàn)象.

算法通過在原網(wǎng)絡中加入一個背景節(jié)點(ground node),將其與網(wǎng)絡中的所有節(jié)點相連,得到一個有N+1個節(jié)點的強連接網(wǎng)絡.

首先,給除背景節(jié)點以外的所有節(jié)點分配1單位的LR值,然后將這1單位的LR值分配給其鄰居節(jié)點,不斷重復這一過程,直到達到穩(wěn)定狀態(tài),即公式所示：

其中,N(x)表示節(jié)點x的鄰居節(jié)點集合,kj表示節(jié)點j的度,sj(t)表示第t次迭代節(jié)點j的LR值.

達到穩(wěn)定狀態(tài)[9]后,此時再將背景節(jié)點的LR值分配給其他所有節(jié)點,因此,最終的LR值定義為：

其中,tc表 示收斂次數(shù),sg(tc)表示穩(wěn)定狀態(tài)下節(jié)點g的LR值.

在計算出所有節(jié)點LR值之后,將LR值進行降序排序,LR值越大說明節(jié)點的重要性越大,從而得到了節(jié)點的更新順序.

1.2 標簽更新策略

在COPRA算法中,更新節(jié)點的標簽時算法簡單地認為每個節(jié)點與其鄰居節(jié)點之間的關系是相等的,顯然這與現(xiàn)實生活中的情況不符合.比如a有b,c,d,e四個鄰居節(jié)點,但如果鄰居節(jié)點b與節(jié)點a的關系更加親密,那么節(jié)點a更加容易接收來自節(jié)點b的標簽.因此,本文重新設計了標簽的更新策略進行標簽更新.首先給出如下定義：

定義1.節(jié)點間的相似性：

其中表示節(jié)點x的鄰居節(jié)點.

定義2.領導標簽：節(jié)點的標簽集合中具有最大從屬系數(shù)的標簽.

結合定義1與定義2給出了新的標簽更新策略,如下式所示：

根據(jù)以上定義,標簽的更新策略描述如下：首先給每個節(jié)點分配一個唯一的標簽,并且標簽的從屬系數(shù)為1.然后為了對標簽進行更新,利用公式(3)計算出節(jié)點與其所有鄰居節(jié)點的相似性,當更新節(jié)點x時,節(jié)點x只接收來自其鄰居節(jié)點中從屬系數(shù)最大的領導標簽,隨后將節(jié)點x從鄰居節(jié)點接收到的最大從屬系數(shù)乘以對應鄰居節(jié)點的相似性,得到節(jié)點x更新后的標簽集合Lx,設定閾值其中b表示節(jié)點x的標簽集合Lx中所有標簽的從屬系數(shù),n表示節(jié)點x的標簽數(shù)量,當b

1.3 終止條件

初始時,標簽數(shù)量等于節(jié)點數(shù)量,隨著標簽更新過程而減少,最后達到最小值,即為最終的社團數(shù)量.定義i t為第t次迭代的標簽數(shù)量(社團數(shù)量),如果當時,算法停止,可能導致輸出結果不準確,雖然此時標簽數(shù)量不變,但是每個社團內(nèi)的節(jié)點數(shù)量可能在幾次迭代后發(fā)生變化.因此,終止條件不僅要滿足還要注意每個社團內(nèi)節(jié)點數(shù)量的變化情況.第t次迭代時,社團c的節(jié)點數(shù)量可以表示如下：

擁有標簽c的節(jié)點數(shù)量會在迭代過程中發(fā)生變化,本文觀測擁有標簽c的最小節(jié)點數(shù)的變化,當時,

否則只要滿足算法停止.

1.4 算法描述

本文算法的主要過程可以分為3個階段：初始化、確定節(jié)點更新順序和標簽傳播.首先初始化每個節(jié)點,給每個節(jié)點分配一個獨特的標簽,并且該標簽的從屬系數(shù)為1.然后為了減少算法的迭代次數(shù)并避免標簽的逆流現(xiàn)象,利用LeaderRank算法對每個節(jié)點進行排序,確定標簽的更新順序.再根據(jù)本文提出的標簽更新策略進行標簽更新,直到達到標簽傳播的終止條件結束迭代過程.最后將具有相同標簽的節(jié)點歸為一個社團,如果節(jié)點有多個標簽那么該節(jié)點為重疊節(jié)點.

算法具體描述如下：

1) 計算網(wǎng)絡中所有節(jié)點的LR值,并按降序排序.2) 計算網(wǎng)絡中所有節(jié)點之間的相似性,得到相似性矩陣.3) 初始化,給每個節(jié)點的標簽初始化為.4) 節(jié)點x接收每個鄰居節(jié)點的領導標簽以及對應的從屬系數(shù).5) 利用公式(5)更新節(jié)點x的標簽從屬系數(shù).6) 設定閾值,刪除小于閾值的標簽,最后對剩余標簽的從屬系數(shù)進行標準化.7) 重復4)-6)步驟,直到達到迭代條件,算法停止.8) 輸出社團,具有多個標簽的節(jié)點則為重疊節(jié)點.

1.5 復雜度分析

設網(wǎng)絡中包括n個節(jié)點,k為節(jié)點的平均度,m為邊的數(shù)量,L為節(jié)點平均包含的標簽個數(shù).

利用LeaderRank算法對網(wǎng)絡中的節(jié)點進行排序需要其中l(wèi)為LeaderRank算法收斂時的迭代次數(shù).初始化標簽需要 O(n),計算相似性矩陣需要 O(m),更新標簽時每次迭代需要 O(Lmlog(Lm/n)),假設共需要迭代T次,所以整個標簽更新過程需要O (TLmlog(Lm/n)),故算法的總復雜度為 O(ml+m+n+TLmlog(Lm/n)),由于L通常非常小,且T遠小于m,所以最終的算法復雜度為

2 實驗分析

為了測試本文提出的算法的性能,將算法應用于真實網(wǎng)絡和人工網(wǎng)絡數(shù)據(jù)集進行驗證分析,并與COPRA算法[7]、SLPA算法[8]、BMLPA算法[10]進行對比分析,以驗證算法的有效性.

2.1 評價指標

為了評價算法性能,本文利用標準互信息和擴展模塊度EQ來衡量重疊社團結構的劃分結果.

1) 擴展模塊度(EQ)

模塊度Q[11]是評價社團質量的主要評價指標,然而它只能用于評價非重疊社團質量,并不能夠準確評價重疊社團質量.因此,本文引入擴展模塊度EQ[12]作為重疊社團質量的評價指標.EQ的取值范圍是0到1之間,值越大說明重疊結構越好.

其中,m表示網(wǎng)絡中邊的個數(shù)表示節(jié)點i屬于社團的數(shù)量,di表示節(jié)點i的度表示如果節(jié)點i和節(jié)點j在同一個社團則值為1,否則為0.

2) 標準互信息(NMI)

由于人工網(wǎng)絡的社團結構是已知的,因此采用標準互信息NMI(Normalized Mutual Information)[13]作為社團挖掘的評價指標.NMI的取值范圍是0到1之間,算法劃分的社團結構越準確,NMI值越大;否則NMI值越小.

其中,x和y分別表示真實的社團結構和實驗產(chǎn)生的社團結構.

2.2 真實網(wǎng)絡實驗

為了驗證本文算法在真實網(wǎng)絡數(shù)據(jù)集上的有效性,將其應用于3種真實網(wǎng)絡數(shù)據(jù)集上,表1列出了用于測試的3種真實網(wǎng)絡數(shù)據(jù)集.

表1 真實網(wǎng)絡數(shù)據(jù)集

由于COPRA算法和SLPA算法具有隨機性,每個數(shù)據(jù)集均采取運行20次的方式獲取COPRA算法和SLPA算法的平均實驗結果.而本文算法以及BMLPA算法由于算法的穩(wěn)定性只需本別對數(shù)據(jù)集進行一次實驗.實驗中COPRA算法的參數(shù)v設為2,SLPA算法的概率閾值設為0.2,BMLPA的標簽過濾閾值設為0.75.

從表2中可以得出,本文算法在選取的3個真實網(wǎng)絡數(shù)據(jù)集上得出的社團結構重疊模塊度較其他算法相比均有所提高,因此本文算法可以有效提高重疊社團挖掘的重疊模塊度,得到的社團結構質量更高.

2.3 人工網(wǎng)絡實驗

為了生成LFR人工網(wǎng)絡,使用LFR基準程序[16]生成了如表3所示的4種類型的人工網(wǎng)絡.其中N是網(wǎng)絡的節(jié)點數(shù),k是節(jié)點的平均度數(shù),maxk是節(jié)點的最大度數(shù),maxc是一個社團的最大節(jié)點數(shù),minc是一個社團的最小節(jié)點數(shù),on是重疊節(jié)點的個數(shù),om是重疊節(jié)點屬于的社團個數(shù),mu是節(jié)點與社團外部連接的邊數(shù)與該節(jié)點度數(shù)的比值,取值范圍是0到1之間,值越大說明網(wǎng)絡的社團結構越不明顯,所以mu取值從0.1到0.6.

表2 真實網(wǎng)絡數(shù)據(jù)集上的EQ值比較

表3 人工網(wǎng)絡的參數(shù)設置

實驗中,針對R1和R2網(wǎng)絡,COPRA算法的參數(shù)v取值2,針對R3和R4網(wǎng)絡,COPRA算法的參數(shù)v取值2～6.在4種網(wǎng)絡中SLPA算法的概率閾值r均取值0.2,BMLPA算法的標簽過濾閾值設為0.75.

圖2為本文算法與COPRA算法、SLPA算法以及BMLPA算法在4種類型人工網(wǎng)絡上的NMI值對比圖.可以看出,本文算法僅在R2網(wǎng)絡的mu=0.4時未取得最優(yōu)值,這是因為本文算法運用在該網(wǎng)絡中產(chǎn)生了過多的重疊節(jié)點,因此影響了社團的質量,其他網(wǎng)絡所得的NMI值都大于對比算法.因此,在人工網(wǎng)絡中,本文算法能夠挖掘出高質量的重疊社團結構.

3 結論與展望

本文針對現(xiàn)有的多標簽傳播算法在挖掘重疊社團時,穩(wěn)定性較差以及需要輸入額外參數(shù)的問題,提出了一種穩(wěn)定的且無需任何參數(shù)的多標簽傳播算法.該算法利用LeaderRank算法衡量節(jié)點重要性確定更新順序,在進行標簽更新時,節(jié)點只接收來自鄰居節(jié)點的領導標簽,并且考慮了節(jié)點與鄰居節(jié)點之間相似性不同的特點,使得更新過程更加穩(wěn)定.通過在真實網(wǎng)絡和人工網(wǎng)絡上進行實驗,結果表明本文算法較現(xiàn)有的基于多標簽傳播的重疊社團挖掘算法得到的社團質量更高.

圖2 算法在4種網(wǎng)絡的NMI比較

1 Fortunato S.Community detection in graphs.Physics Reports,2010,486(3-5)：75-174.[doi：10.1016/j.physrep.2009.11.002]

2 羅明偉,姚宏亮,李俊照,等.一種基于節(jié)點相異度的社團層次劃分算法.計算機工程,2014,40(1)：275-279.

3 Girvan M,Newman MEJ.Community structure in social and biological networks.Proceedings of the National Academy of Sciences of the United States of America,2002,99(12)：7821-7826.[doi：10.1073/pnas.122653799]

4 Newman MEJ.Fast algorithm for detecting community structure in networks.Physical Review E,Statistical,Nonlinear,and Soft Matter Physics,2004,69(6)：066133.[doi：10.1103/PhysRevE.69.066133]

5 Blondel VD,Guillaume JL,Lambiotte R,et al.Fast unfolding of community hierarchies in large networks.Journal of Statistical Mechanics：Theory and Experiment,2008.[doi：10.1088/1742-5468/2008/10/P10008]

6 Raghavan UN,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks.Physical Review E,Statistical,Nonlinear,and Soft Matter Physics,2007,76(3)：036106.[doi：10.1103/Phys RevE.76.036106]

7 Gregory S.Finding overlapping communities in networks by label propagation.New Journal of Physics,2010,12(10)：103018.[doi：10.1088/1367-2630/12/10/103018]

8 Xie J,Szymanski BK,Liu X.SLPA：Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process.Proceedings of the IEEE 11th International Conference on Data Mining Workshops.Vancouver,Canada.2011.344-349.

9 Lü LY,Zhang YC,Yeung CH,et al.Leaders in social networks,the Delicious case.PLoS One,2011,6(6)：e21202.[doi：10.1371/journal.pone.0021202]

10 Wu ZH,Lin YF,Gregory S,et al.Balanced multi-label propagation for overlapping community detection in social networks.Journal of Computer Science and Technology,2012,27(3)：468-479.[doi：10.1007/s11390-012-1236-x]

11 Newman MEJ,Girvan M.Finding and evaluating community structure in networks.Physical Review E,Statistical,Nonlinear,and Soft Matter Physics,2004,69(2)：026113.[doi：10.1103/PhysRevE.69.026113]

12 Shen HW,Cheng XQ,Guo JF.Quantifying and identifying the overlapping community structure in networks.Journal of Statistical Mechanics：Theory &Experiment,2009,(7)：07042.

13 Lancichinetti A,Fortunato S,Kertész J.Detecting the overlapping and hierarchical community structure in complex networks.New Journal of Physics,2009,11(3)：033015.[doi：10.1088/1367-2630/11/3/033015]

14 Zachary WW.An information flow model for conflict and fission in small groups.Journal of Anthropological Research,1977,33(4)：452-473.[doi：10.1086/jar.33.4.3629752]

15 Lusseau D,Schneider K,Boisseau OJ,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations.Behavioral Ecology and Sociobiology,2003,54(4)：396-405.[doi：10.1007/s002 65-003-0651-y]

16 Lancichinetti A,Fortunato S,Radicchi F.Benchmark graphs for testing community detection algorithms.Physical Review E,Covering Statistical,Nonlinear,Biological,and Soft Matter Physics,2008,78(4)：046110.