基于隨機游走相似度矩陣的改進標簽傳播算法

宋　琛　張賢坤　費　松　莢　佳　劉　棟

(天津科技大學計算機科學與信息工程學院　天津 300222)

?

基于隨機游走相似度矩陣的改進標簽傳播算法

宋琛張賢坤費松莢佳劉棟

(天津科技大學計算機科學與信息工程學院天津 300222)

基于標簽傳播的社區發現算法因其時間效率高而得到廣泛關注。針對該算法因標簽傳播的隨機性導致其社區劃分準確度難以保證的問題，提出一種基于隨機游走的改進算法。首先，引入隨機游走思想，計算得到一種衡量網絡節點間相似度的矩陣；其次，在標簽傳播過程中，當鄰居節點中標簽出現頻率存在多個最高時，不是隨機選擇一個，而是選擇相似度最高的鄰居節點所擁有的標簽來更新，避免了標簽在社區之間的任意傳播；最后，用不同的真實網絡進行測試，結果表明在社區發現中該算法比原始標簽傳播算法取得更好的表現。

隨機游走標簽傳播社區發現相似度劃分

0　引　言

實際工作生活中，各類信息構成不同的網絡，如微博社交網絡，蛋白質網絡，疾病網絡等。根據網絡節點的連接關系可以將其劃分為若干社區，社區內部節點連接相對緊密，社區間連接則較為稀疏。社區發現對于網絡輿情監測、安全預警、電子商務等有非常重要的應用價值。如聊天軟件推薦的好友都歸屬同一社區，購物網站向不同社區的用戶推薦不同風格的商品，公安系統監測邪教社區 “游行”等詞語頻率升高時立即采取行動。對社區發現的研究，可以獲取大量可靠有價值的信息。

社區發現的研究近年來取得了相當大的進展，很多學者提出了新理論和新方法。這些方法主要可以分為四類：圖分割方法、W-H算法、層次聚類法以及標簽傳播算法。圖分割方法通常應用于計算機領域，它基于迭代對分技術：每次劃分都將網絡分為最優的兩個子圖，子圖再繼續迭代對分，直至數量達到要求。圖分割法大體可以分為兩類：基于拉普拉斯矩陣的譜平分法[5,6]和Kerninghan-Lin算法[4]。其缺點是每次只能將網絡對分，為了獲取結果需要不斷迭代。為解決這一問題，Wu和Huberman提出了W-H算法[7]：選取不同社區的兩個節點，分別設為電壓為1的初始點和電壓為0的終結點，將每條邊阻值設為1，其他節點會得到不同的電壓值。將電壓值相似的節點劃分到同一社區。W-H算法缺點是在劃分前必須知道社區結構的部分先驗信息，以保證初始點和終結點不在同一社區。層次聚類法是根據節點間的連接關系和相似程度來劃分社區，該方法又可以分為凝聚法和分裂法。代表算法分別為G-N算法[8]和Newman快速算法[9]，但由于社區中存在很多相似度極低的點，層次聚類法往往忽略這些節點，最終結果難以令人滿意。標簽傳播算法LPA(Label Propagation Algorithm)[10]與前幾類方法相比，不需要知道網絡結構或者先驗社區結構，僅依賴于網絡的傳播特性，具有線形的時間復雜度，社區劃分效率很高。引起了國內外學者的廣泛關注。

標簽傳播算法準確高效，但傳播過程中，當節點鄰居中標簽出現頻率存在多個最高時，會平等的對待每一個節點，隨機選取一個最高標簽，這種隨機性導致標簽在不同社區之間的傳播，針對標簽傳播算法的缺點，國內外學者提出了許多改進方法。文獻[11]通過計算節點潛在影響力，生成一個具有k個強影響力節點的初始集合，為集合中節點賦予初始標簽，節點的影響力越強，標簽的傳播速度越快。但該算法無法準確界定k值，如果k取值少于實際社區數目，算法無論如何運算都不會得到正確的社區劃分。Lin等依據節點的權重排序，按照先后順序依次更新節點標簽[1]。康旭彬和賈彩燕通過分析節點之間的拓撲關系為節點賦予權值[12]，打破節點原本的平等關系。Zhang等提出了基于邊聚集系數的標簽算法[2]。另外還有基于反饋控制[3]、目標函數[13]、LeaderRank[14]、圈子[21]等進行標簽傳播的社區發現改進算法。

本文從抑制標簽傳播的隨機性入手，引入隨機游走思想，基于隨機游走的距離公式定義了一種新的相似度計算方法，構建節點間的相似度矩陣。在標簽傳播的過程中，當節點鄰居中標簽頻率出現多個最高時，不再隨機選定，而是選擇最相似的節點所擁有的標簽進行更新，有效防止了節點在社區之間的任意傳播，提高了社區劃分的準確度。

1　標簽傳播算法

1.1標簽傳播算法描述

將網絡視為一個有n個節點的無向圖G={V,E}，V表示節點的集合，E表示節點間聯系的集合。標簽傳播算法可簡述如下：

(1) 初始化社區，為圖中的每個節點隨機分配唯一的標簽，用標簽代表節點所在社區。

(2) 標簽更新，計算節點x的鄰接節點中各標簽出現頻率，將x的標簽更新為：出現頻率最高的標簽，若標簽頻率存在多個最高，則隨機選取一個。

(3) 判斷是否滿足停止條件：達到規定的迭代次數或者若干次迭代后標簽值達到穩定。

(4) 劃分社區，標簽相同的節點歸屬同一社區。

圖1為單個社區標簽傳播的過程，首先為4個節點分配a、b、c、d四個不同的標簽，而后隨機選取節點3進行更新，節點3在3個鄰居標簽中隨機更新為標簽b。繼續選擇節點4，節點4的鄰居節點中只有一個頻率最高的標簽b，其標簽更新為b，隨后節點1也更新為標簽b。所有節點屬于同一社區，劃分結束。

圖1　標簽傳播過程

1.2標簽傳播算法存在的問題

標簽傳播算法簡單、高效，但準確率還有待提高。其最大的原因是平等的對待了每一個節點，導致標簽在社區之間很容易傳播，在更大范圍上形成了社區的吞并，如圖2所示，該圖原本應當劃分為兩個社區。但若節點3更新標簽時，在四個相鄰標簽中，隨機的選擇了節點4的標簽，隨后上半部分3個節點都將擁有節點4的標簽，上社區被吞并，整個網絡最終將劃分為同一個社區。這是標簽算法所暴露出的最大缺點：節點鄰居中標簽出現頻率存在多個最高時做出的選擇是隨機的。

圖2　社區吞并現象

2　基于隨機游走相似度矩陣的標簽傳播算法

標簽傳播算法最大的缺點是其隨機選擇標簽而導致結果不穩定，為解決這一問題，我們提出基于隨機游走[19]相似度矩陣的改進標簽傳播算法RWLPA(Label Propagation Algorithm Based on the Similarity Matrix Using Random Walk)。

2.1隨機游走相似度矩陣的計算

改進的標簽傳播算法在社區劃分過程中，當節點的鄰居節點中標簽頻率存在多個最高時，能作出正確的選擇，更新為最有可能處于同一社區的節點擁有的標簽。為控制選擇方向，引入基于隨機游走的相似度矩陣。節點每次更新標簽都選擇與自己相似度最大的節點所擁有的標簽。

借助相似度矩陣，我們可以很好對標簽傳播方向進行選擇，對于圖3中節點4來說，共有4個鄰接節點，即4個更新時可選擇的標簽。查找圖4的相似度矩陣，節點4與節點1,2,3的相似度為4.189，與節點5的相似度為1.791，因此節點4應當在節點1,2,3中選擇標簽更新，實際上無論選擇這三個中的哪個節點，左社區都會得到正確劃分。

目前對于隨機游走相似度的衡量有幾種不同的標準。最先得到使用的是平均通勤時間ACT[15]和平均首次穿越時間MFTP[16]。這兩種衡量方式易于理解，但是復雜度高。本文基于文獻[17]中介紹的方法，定義一種新的距離進行衡量。算法初始時將隨機游走的walker放置在圖中任選的節點，使其按照馬爾科夫性質[20]隨機選擇下一個位置。隨機游走可以用遞推的方式來描述。用Pxy表示一步之內walker從節點x走到y的概率。πxy(t)表示walker行走t步時，從節點x出發到達y的概率。πx(t)是π(t)矩陣第x列的列矩陣。

(1)

πx(t)=PTπx(t-1)

(2)

如果節點x與y之間有連接，則axy=1，若二者無連接則axy=0，kx表示節點x的出度。PT是矩陣P的轉置。

(3)

其中|E|是網絡中節點間的連接總數。

但隨機游走同樣存在問題。其缺點在于walker的行走遵循馬爾科夫性質。假如x和y是同一社區中相近的兩個節點，相似度很高，而walker卻可能游走到距離較遠的節點或者到其他社區中，從而測定的x和y之間的相似度很低。為了解決這一問題，可以連續多次釋放walker，降低這種可能對算法的影響，然后對LRW相似度進行疊加，這樣就降低了在某次游走時可能出現的特殊情況對算法造成的影響。疊加后距離公式為：

(4)

對于一個固定的網絡來說，其總邊數，即|E|是固定的，因此在計算過程中，2|E|被忽略。產生一種新的相似度，稱其為OLRW相似度(Omitted Similarity Based on Local Random Walk)。

(5)

以Δt=1連續不停釋放t個walker，直至最后一個walker步數為1，此時首次開始行走的walker步數為t。相應的OSRW相似度(Omitted Similarity Based on Superposed Random Walk)計算公式為：

(6)

計算過程中，使用新的OSRW相似度計算節點之間的相關程度，生成相似度矩陣，圖3為具有8個節點的簡單網絡圖，圖4為釋放4個walker計算得到的該圖OSRW相似度矩陣。

圖3　存在多個頻率最高相鄰標簽的簡單網絡圖

圖4　相似度矩陣

在隨機游走的過程中，依次釋放walker。步數t不同，walker數量也就不同，求得的相似度矩陣也不同。步數t的選取對于算法效果十分重要，我們通過實驗確定t的取值。試驗中選取節點數為500的基準網絡為數據集，采用準確度NMI作為評價值。混合參數μ表示社區之間的混合程度(μ取值為0到1)，μ取值較小時，社區結構清晰，容易劃分，算法準確度接近于1；μ取值較大時，社區結構不明顯，準確度為0。因此我們取準確度變化幅度較大的μ=0.6和0.65進行測試。

這里僅對較少步數(t≤10)進行試驗。當步數過高時，算法過于復雜，且相似度會逐漸趨向于一種穩定狀態[17]，取極限(t→+∞)，此時節點x與y之間的相似度不依賴于其他參數，僅與節點x的度相關，即：πxy(t)=kx/2|E|。因此并非t取值越高，相似度矩陣越精確。通過圖5和圖6，我們可以看出3≤t≤8時，實驗結果更為精確，所求得社區的NMI更高。這是由于t過小，walker數量少、行走步數小，求得矩陣的準確率不高，而t過大，相似度則趨于穩定。本文選取步數t=4計算相似度矩陣。

圖5μ=0.6時不同步數對NMI的影響

圖6　μ=0.65時不同步數對NMI的影響

2.2改進算法描述

依據前文對標簽算法的介紹，結合隨機游走算法，RWLPA算法過程表述如下：

(1) 初始化社區，為圖中的每個節點隨機分配唯一的標簽，用標簽代表節點所在社區。

(2) 標簽更新，計算節點x的鄰接節點中各標簽出現頻率，將x的標簽更新為：出現頻率最高的標簽，若標簽頻率存在多個最高，則選取相似度最高的節點所擁有的標簽，若存在多個相似度最高的節點，則隨機選取一個。

(3) 判斷是否滿足停止條件：達到規定的迭代次數或者若干次迭代后標簽值達到穩定。

(4) 劃分社區，標簽相同的節點歸屬同一社區。

3　實驗及分析

為驗證算法的準確性，本文采用Zachary’s karate club、Lusseau’s Dolphin、PolBooks等廣泛應用于社區發現評價體系的數據集進行測試。每次實驗運行100次，以盡量消除算法的隨機性。下面以Zachary’s karate club數據集[3]為例，進行介紹。該數據集包括美國一個空手道俱樂部中的34個成員，78個成員聯系。這34個成員由于兩位領導相互之間的矛盾產生了分裂，成為兩個派別。圖7為原始LPA算法劃分結果，從圖中可以看出，LPA算法對小社區很敏感。比較LPA算法與RWLPA算法，可以看到圖8中 RWLPA算法中節點5與節點26被劃分到大社區中，從直觀上來看，節點5與大社區中1、11有連接，小社區中僅與7有連接。節點26的鄰接節點24、25，24與大社區的聯系也遠多于25與小社區的聯系。直觀上來說，5、26應當劃分到大社區中。

圖7　LPA算法劃分社區示意圖

圖8　RWLPA算法劃分社區示意圖

為了更好的證明，使用Newman提出的社區發現模塊度Q[18]作為實驗的評價指標。

(7)

式中|E|代表無向圖總邊數，Aij為鄰接矩陣，ki為節點i的度數，節點i與j在同一社區時δ=1，反之δ=0。

表1中模塊度計算的結果，證明針對Zachary’skarateclub數據集，RWLPA算法的結果優于LPA算法。為了更好的驗證，我們同時選取Lusseau’sDolphin、PolBooks等公開測試數據集對進行實驗。為提高實驗結果的可靠性，對每個數據集分別用兩個算法各運行100次求得平均值，如表1所示。表中數據表明，對于4個真實數據集，RWLPA算法劃分的社區模塊度均高于LPA算法。這主要是因為在標簽傳播的過程中，相似度矩陣很好地抑制了傳播過程中的隨機性，節點每次都選擇最可能與自身處于同一社區的節點標簽進行更新，使社區劃分結果更穩定、更接近于真實情況。

表1　真實數據集結果

4　結　語

本文對社區發現的常用算法進行了介紹，并基于隨機游走的相似度矩陣對標簽算法做出改進。實驗證明，RWLPA的效果優于原始LPA算法。但算法對重疊社區考慮不足，同時矩陣的計算占用較多的資源，在未來可以對重疊社區進行研究，改進矩陣運算方法，適應現實網絡大規模重疊社區的發現需要。

[1] Lin Zhen,Zheng Xiaolin,Xin Nan,et al.CK-LPA:Efficient community detection algorithm based on label propagation with community kernel[J].General Information,2014,416(C):386-399.

[2] Zhang X,Tian X,Li Y,et al.Label propagation algorithm based on edge clustering coefficient for community detection in complex networks[J].International Journal of Modern Physics B,2014,28(30):1450216.

[3] Li Yakun,Wang Hongzhi,Li Jianzhong,et al.Efficient community detection with additive constrains on large networks[J].Knowledge-Based Systems,2013,52(6):268-278.

[4] Kernighan BW,Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,1970,49(2):291-307.

[5] Newman M E J.Detecting Community Structure in Networks [J].Europe Physical Journal B,2004,38(2):321- 330.

[6] Pothen A,Simon H D,Liou K P.Partitioning sparse matrices with eigenvectors of graphs [J].SIAM Journal on Matrix Analysis and Applications,1990,11(3):430-452.

[7] Wu Fang,Huberman Bennardo A.Finding communities in linear time:a physics approach[J].Physics of Condensed Matter,2004,38(2):331-338.

[8] Girvan M,Newman M E J.Community structure in social and biological networks [J].PNAS,2002,99(12):7821-7826.

[9] Newman M E J.Fast Algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):279-307.

[10] Nandini R U,Albert R,Kumara S.Near linear timealgorithm to detect community structures in large-scale networks[J].Physical Review E,Statistical,nonlinear,and soft matter physics,2007,76(3):36106.

[11] Zhao Zhuoxiang,Wang Yitong,Tian Jiatang，et al.A novel algorithm for community discovery in social networkd based on label propagation[J].Journal of Computer Research and Development,2011,48(Sup.):8-16.

[12] 康旭彬,賈彩燕.一種改進的標簽傳播快速社區發現方法[J].合肥工業大學學報：自然科學版,2013,36(1):43-47.

[13] Barber M J.Detecting network communities by propagating labels under constraints[J].Physical Review E,2009,80(2):283-289.

[14] 石夢雨,周勇,邢艷.基于LeaderRank的標簽傳播社區發現算法[J].計算機應用，2015，35(2)：448-451，455.

[15] Yen Luh,Fouss Francois,Decaestecker Christine,et al.Graph nodes clustering with the sigmoid commute-time kernel:A comparative study[J].Data & Knowledge Engineering,2009,68(3):338-361.

[16] Zhou Haijun.Distance,dissimilarity index,and network community structure[J].Physical Review E,2003,67(6)：061901.

[17] Liu Weiping,Lü Linyuan.Link prediction based on local random walk [J].Europhys Letters,2010,89(5):58007-58012.

[18] Newman M E J,Grivan M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):292-313.

[19] Pons Pascal,Latapy Matthieu.Computing communities in large networks using random walks[C]//Computer and Information Sciences-ISCIS 2005.2005:284-293.

[20] Schaub M T,Delvenne J C,Yaliraki S N,et al.Markov dynamics as a zooming lens for multiscale community detection:non clique-like communities and the field-of-view limit[J].Plos One,2012,7(2):e32210.

[21] Ma Qianli,Zhang Junhao.A Local Strengthened Multi-label Propagation Algorithm for Community Detection[J].Computer Engineering,2014,40(6):171-174.

AN IMPROVED LABEL PROPAGATION ALGORITHM BASED ON RANDOM WALK SIMILARITY MATRIX

Song ChenZhang XiankunFei SongJia JiaLiu Dong

(CollegeofComputerScienceandInformationEngineer,TianjinUniversityofScienceandTechnology,Tianjin300222,China)

Community detection algorithm based on label propagation attracts widespread concerns because of its high time efficiency.But it is difficult for the algorithm to guarantee the accuracy of community partition as the label propagates randomly.In response to the problem,in this paper we propose a random walk-based improved label propagation algorithm.First,we introduce the random walk idea to get a matrix measuring the similarity among various nodes of the network through calculation.Secondly,during the process of label propagation,when a neighbour node has more than one label with the highest occurrence frequency,we will not randomly select one label of a neighbour node but will choose the label owned by a neighbour node having highest similarity and update it.This avoids the random label propagation among communities.Finally,we test the label propagation algorithm and the improved label propagation algorithm in different real networks.Results show that in community detection the improved algorithm has better performance than the primitive label propagation algorithm.

Random walkLabel propagationCommunity detectionSimilarityDivision

2015-03-25。天津市科技型中小企業創新資金項目(12ZXCXGX33500)。宋琛，碩士生，主研領域：社會網絡分析。張賢坤，教授。費松，碩士生。莢佳，碩士生。劉棟，副教授。

TP3

A

10.3969/j.issn.1000-386x.2016.08.060