基于標簽傳播的重疊社區(qū)發(fā)現(xiàn)研究

姜浩

摘要：標簽傳播算法[1]的優(yōu)點使其廣泛應(yīng)用。但是標簽傳播算法規(guī)則簡單、隨機性大的特點，使其魯棒性較差。為了滿足實際復(fù)雜網(wǎng)絡(luò)的需要，該文引入了生活中的選舉模式到算法中，將標簽傳播算法傳播規(guī)則進行了改進，賦予全部節(jié)點傳播規(guī)則，使節(jié)點在傳播過程中能夠自主的更新標簽，使其能夠發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)。

關(guān)鍵詞：標簽傳播算法；重疊社區(qū)

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

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

本文通過引入生活中的選舉模式，給予每個節(jié)點傳播規(guī)則，通過給每個節(jié)點一個標簽序列，對傳播過程中接觸到的標簽進行存儲與傳播，并控制傳播距離防止全局社區(qū)產(chǎn)生，從而實現(xiàn)了重疊社區(qū)網(wǎng)絡(luò)的劃分。

1 相關(guān)工作

1.1 相關(guān)算法

Jierui Xie等人在標簽傳播算法基礎(chǔ)上提出了SLPA（Speaker-listener Label Propagation Algorithm）一種重疊社區(qū)發(fā)現(xiàn)算法[8]。SLPA算法在網(wǎng)絡(luò)結(jié)構(gòu)特征明顯的社區(qū)中有良好性能。但是SLPA算法需要人為的設(shè)置參數(shù)用于選擇標簽，而找到一個合適的值很難。所以在大規(guī)模的網(wǎng)絡(luò)中SLPA算法得不到擴展。

1.2 定義

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

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

節(jié)點u的影響力；節(jié)點u的度；和節(jié)點u和節(jié)點的鄰居集合。

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

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

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

2 算法

2.1 候選者產(chǎn)生階段

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

2.2 選舉階段

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

[d'=e1d] （2）

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

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

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

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

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

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

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

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

u.BCounter表示節(jié)點u的票數(shù)。

每次投票結(jié)束，勝出者在下一輪選舉前會先統(tǒng)計票數(shù)，公式如下：

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

u.Bbox：票箱Bbox中節(jié)點u的票數(shù)；u.BCounter：相鄰節(jié)點與節(jié)點u同標簽總票數(shù)。

2.3 調(diào)整階段

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

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

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

2.4算法描述

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

Step1：節(jié)點影響力的計算；

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

Step3；候選者u與鄰居節(jié)點影響力大的候選者v比較，如果候選者u影響力大，則候選者u標簽變?yōu)長u={（lu，2），（lv，1）}并票數(shù)加1。反之同理；

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

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

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

Step7；調(diào)整階段，過濾掉支持率低和票數(shù)少的勝出者，更新標簽。

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

3 實驗

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

3.1 實驗數(shù)據(jù)

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

3.2 實驗評估方法

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

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

A是網(wǎng)絡(luò)的臨界矩陣，若u和v 之間存在一條連邊，那么Auv=1，否則Auv=0；m是網(wǎng)絡(luò)的總邊數(shù)；P是對應(yīng)劃分的社區(qū)集合；ku和kv分別是節(jié)點u和v的度；acu是節(jié)點隸屬于社區(qū)的程度[10]。

3.3 實驗結(jié)果分析

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

4 結(jié)論

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

參考文獻：

[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.

【通聯(lián)編輯：代影】