基于標簽傳播的重疊社區發現研究

姜浩

摘要：標簽傳播算法[1]的優點使其廣泛應用。但是標簽傳播算法規則簡單、隨機性大的特點，使其魯棒性較差。為了滿足實際復雜網絡的需要，該文引入了生活中的選舉模式到算法中，將標簽傳播算法傳播規則進行了改進，賦予全部節點傳播規則，使節點在傳播過程中能夠自主的更新標簽，使其能夠發現復雜網絡中的重疊社區。

關鍵詞：標簽傳播算法；重疊社區

中圖分類號：TP3 文獻標識碼：A 文章編號：1009-3044（2018）28-0250-03

在網絡中，一個節點可能屬于多個社區，使得重疊社區研究得到了關注。Lancichinetti等人[2]提出了重疊社區挖掘的局部算法。Palla等人[3]在基于k-派系的基礎上提出了一種重疊社區挖掘的算法。在Newman提出的模塊度基礎上，Shen等人[4]提出了劃分重疊社區效果的評價指標，然后通過優化這個評價指標，從而提出了一種重疊社區挖掘算法[5]。Gregory[6]提出了一種兩階段策略的重疊社區挖掘算法。Chen等人[7]提出了一種快速的重疊社區挖掘算法，算法起初從只有一個節點的社區原始社區出發，利用滾雪球的方式對社區進行擴展。

本文通過引入生活中的選舉模式，給予每個節點傳播規則，通過給每個節點一個標簽序列，對傳播過程中接觸到的標簽進行存儲與傳播，并控制傳播距離防止全局社區產生，從而實現了重疊社區網絡的劃分。

1 相關工作

1.1 相關算法

Jierui Xie等人在標簽傳播算法基礎上提出了SLPA（Speaker-listener Label Propagation Algorithm）一種重疊社區發現算法[8]。SLPA算法在網絡結構特征明顯的社區中有良好性能。但是SLPA算法需要人為的設置參數用于選擇標簽，而找到一個合適的值很難。所以在大規模的網絡中SLPA算法得不到擴展。

1.2 定義

定義1（節點影響力）給定網絡G=（V，E），節點的影響力表現為u與其他節點之間的連接度，一般地，節點的度越高則其影響力越大，該節點的重要性越顯著。節點u的影響力度量方法可形式化為公式（1）。

[Influ=v∈Nvdeguw∈Nvdegw] （1）

節點u的影響力；節點u的度；和節點u和節點的鄰居集合。

定義2（候選者）選舉起初選取部分影響力較大的節點，給予這些候選者唯一的初始標簽且擁有統計票數的計數器BCounter，令候選者的節點集合為Vh。

定義3（勝出者）實施優勝劣汰的選舉機制，失敗的候選者降為投票者，勝利則保存原標簽，令勝利者的節點集合為Vs。

定義4（投票者）影響力低的節點為投票者，投票者僅具有投票的權利，根據候選者或者勝出者的標簽來更新自身的標簽，令投票者集合為Vt。

2 算法

2.1 候選者產生階段

在初始階段，節點初始為投票人，并計算影響力，根據影響力的大小從每個節點的鄰居節點集合中選取比例為θ候選者，然后給予這些節點一個唯一的標簽，并存儲到多維標簽序列；剩余的節點標記為投票者，無標簽。如圖1所示，節點u原始標簽為lk，多維標簽序列中每個標簽信息包含標簽L={l1，l2，…，lk}、票數P={p1，p2，…，pk}和傳播距離D={d1，d2，…，dk}，k與標簽號相對應。開始階段，票箱中擁有自身標簽lk，傳播距離為1，票數為1。

2.2 選舉階段

候選者產生后，它們之間開始競爭，通過對原有標簽的總票數或節點總影響力的比較而進行投票，敗者投票給勝者，然后把標簽序列分別保存。如圖2（a）所示，候選者v和候選者u進行比較，候選者v票數為2大于u票數1，失敗的候選者u則把票投給勝利的候選者v。如圖2（b）所示， 候選者v中l1 和候選者u中l2為外來標簽，在存儲標簽時傳播距離D衰減為e-1，計算傳播距離的公式如（2）所示：

[d'=e1d] （2）

d?為記錄傳播后距離，d為傳播距離。

投票者初始無標簽，按比例θ把票投給鄰居票數多的候選者，并按照票數進行存儲標簽排序。規則是迭代一次僅有一次投票機會，可以投多個勝出者但不能重復投一個勝出者。如圖3所示，當投票者v投票候選者u時，投票者v把候選者u的標簽信息保存到自身的標簽序列中。

在此算法中，候選者的競爭主要包括2個階段：

階段1：候選者通過對節點總影響力或原有標簽的總票數的比較而進行投票，敗者投票給勝者，然后把標簽序列分別保存。候選者u競爭的勝出者計算公式（3）的Vic（u）。

[VIcu=argmaxInflvif Inflv-Influ>0u otherwise] （3）

Infl（v）：節點v的影響力；N（u）：節點u的鄰居。

階段2：勝出者再進行比較選出新的勝出者，新勝出者的標簽將存放在失敗者本身的標簽前（包括該失敗者的投票者），重復如上操作，直到迭代數最大或票數穩定。階段2通過公式（4） 迭代生成新勝出者。

[Vicu=argmaxv.BCounterif v.BCounter>u.BCounterv∈Nu∧v∈Vxu otherwise]（4）

u.BCounter表示節點u的票數。

每次投票結束，勝出者在下一輪選舉前會先統計票數，公式如下：

[u.BCounter=u.Bbox+v∈Nuv.Bboxδlu，lv] （5）

u.Bbox：票箱Bbox中節點u的票數；u.BCounter：相鄰節點與節點u同標簽總票數。

2.3 調整階段

在穩定后需要把支持率低或票數過低的勝出者篩選出去，然后再確定每個節點所屬的社區。勝出者支持率Support（u）的計算公式如下所示：

[Supportu=v∈Vuδlu，lvdegu] （6）

deg（u）：節點u的鄰居個數；：節點u同標簽的節點數。過濾掉票數低于總票10%的勝出者和低于50%支持率的勝出者并降級。

2.4算法描述

算法為三個階段：候選者產生階段、選舉階段和整理階段。步驟如下：

Step1：節點影響力的計算；

Step2：按比例θ將節點影響力高的選為候選者，并給予唯一標簽。影響力低的為投票者，沒有標簽；

Step3；候選者u與鄰居節點影響力大的候選者v比較，如果候選者u影響力大，則候選者u標簽變為Lu={（lu，2），（lv，1）}并票數加1。反之同理；

Step4：競爭是相鄰的候選者u和候選者v進行票數比較，若雙方不含有對方標簽需要比較后再存儲。如果含有只需更新票數即可；

Step5：投票者按比例θ把票投給鄰居節點中票數最多的勝出者，并將勝出者的標簽保存到自身的標簽序列中；

Step6：重復步驟4和步驟5，直到無投票行為；

Step7；調整階段，過濾掉支持率低和票數少的勝出者，更新標簽。

假設社區節點為n和邊為m，則該算法的時間復雜度分析為：如果一個節點的影響力計算為O（m），則總的影響力為O（nm）；排序標簽序列為O（KlogK），重疊社區最大數和K有關；迭代一次的時間復雜度為O（m+KlogK*n）。因此循環時間復雜度為O（P*（m+ KlogK*n））， 迭代的次數為P。所以，時間復雜度為O（P*（m+ KlogK*n））O（KlogK*n）即時間復雜度跟網絡的重疊率相關。重疊率與K成正比，當K=1時，即為非重疊網絡。

3 實驗

運行的環境為Intel（R） Core（TM）i5-7200U CPU@2.50GHz 2.71GHz內存8G；軟件環境為Windows10，Myeclipse（Version：10.7.1）；編程語言：JAVA。為驗證算法的性能，采用了三類真實網絡數據集，并選擇SLPA算法進行效果對比。

3.1 實驗數據

本文選取了3種常用的真實數據集，具體參數如表1所示。

3.2 實驗評估方法

模塊度是由Newman和Girvan于2004年[10]提出的，但是只針對于不重疊社區的情況。為了能研究重疊社區，一些學者對Newman提出的模塊度進行擴展，從而使模塊度得到發展。本文采用的是重疊社區的模塊度指標Q0函數，由文獻[14]提出，如公式7所示。

[Q0=12mc∈Pu，vacuacvAuv-kukv2m] （7）

A是網絡的臨界矩陣，若u和v 之間存在一條連邊，那么Auv=1，否則Auv=0；m是網絡的總邊數；P是對應劃分的社區集合；ku和kv分別是節點u和v的度；acu是節點隸屬于社區的程度[10]。

3.3 實驗結果分析

有效性分析。為了驗證算法的有效性，分別對兩種算法運行50次的Q0平均值進行匯總，具體如表2所示。

4 結論

本文提出了基于選舉模式的標簽傳播重疊社區發現算法。其思想是，節點選取影響力大的鄰居節點參加選舉，候選者競爭逐步形成社區核心，投票者投票追隨影響力大的核心，形成了以核心社區為主的社團。在真實網絡實驗中，表明該算法在重疊率低的社區網絡中有良好的表現。

參考文獻：

[1] Zhu X， Ghahramani Z. Learning from labeled and unlabeled date with label propagation[R]. Technical Report CMU-CALD-02-107，Carnegie Mellon University，2002.

[2] Lancichinetti A， Fortunato S， Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics，2009，11（3）：19-44.

[3] Palla G， Derényi I， Farkas I， et al. Uncovering thr overlapping community structure of complex networks in nature and society[J]. Nature，2005，435：814-818.

[4] Shen H W， Cheng X Q， Guo J F. Quantifying and identifying the overlapping community structure in networks[J]. Journal of Statistical Mechanics： Theory and Experiment，2009：07042.

[5] Shen H W， Cheng X Q， Cai K， et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A： Statistical Mechanics and its Applications，2009，388：1706-1712.

[6] Gregory S. Finding overlapping communities using disjoint community detection algorithms[J]. Studies in Computational Intelligence，2009，207：47-61.

[7] Chen D B， Shang M S， Lv Z， et al. Detecting overlapping communities of weighted networks via a local algorithm[J]. Physical A： Statistical Mechanics and its Applications，2010，389：4177-4187.

[8] Xie J， Szymanski B K， Liu X. SLPA： Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process[C]//2011 11th IEEE International Conference on Data Mining Workshops. IEEE Computer Society，2011：344-349.

[9] W.W. Zachary. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research， 1977，33（4）：452-473.

[10] Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Phys[C]//Rev. E. 2006：036104.

[11] Newman M E J.A symmetrized snapshot of the structure of the Internet at the level of autonomous systems[EB/OL]. （2006-07-22）[2017-02-18]. http：//www-personal.umich.edu/～mejn/netdata.

[12] Lázár A， ábel D， Vicsek T. Modularity measure of networks with overlapping communities[J]. Europhysics Letters，2010，90：18001.

[13] Nepusz T， Petróczi A， Négyessy L， et al. Fuzzy communities and the concept of bridgeness in complex network[J]. Physical Review E， 2008，77：016107.

[14] Shang M S， Chen D B， Zhou T. Detecting overlapping communities based on community cores in complex networks[J]. Chinese Physics Letters， 2010，27：058901.

【通聯編輯：代影】