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

宋　琛　張賢坤　費　松　莢　佳　劉　棟

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

?

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

宋琛張賢坤費松莢佳劉棟

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

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

隨機游走標簽傳播社區(qū)發(fā)現(xiàn)相似度劃分

0　引　言

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

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

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

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

1　標簽傳播算法

1.1標簽傳播算法描述

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

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

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

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

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

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

圖1　標簽傳播過程

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

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

圖2　社區(qū)吞并現(xiàn)象

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

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

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

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

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

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

(1)

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

(2)

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

(3)

其中|E|是網(wǎng)絡中節(jié)點間的連接總數(shù)。

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

(4)

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

(5)

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

(6)

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

圖3　存在多個頻率最高相鄰標簽的簡單網(wǎng)絡圖

圖4　相似度矩陣

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

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

圖5μ=0.6時不同步數(shù)對NMI的影響

圖6　μ=0.65時不同步數(shù)對NMI的影響

2.2改進算法描述

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

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

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

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

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

3　實驗及分析

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

圖7　LPA算法劃分社區(qū)示意圖

圖8　RWLPA算法劃分社區(qū)示意圖

為了更好的證明，使用Newman提出的社區(qū)發(fā)現(xiàn)模塊度Q[18]作為實驗的評價指標。

(7)

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

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

表1　真實數(shù)據(jù)集結(jié)果

4　結(jié)　語

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

[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] 康旭彬,賈彩燕.一種改進的標簽傳播快速社區(qū)發(fā)現(xiàn)方法[J].合肥工業(yè)大學學報：自然科學版,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的標簽傳播社區(qū)發(fā)現(xiàn)算法[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。天津市科技型中小企業(yè)創(chuàng)新資金項目(12ZXCXGX33500)。宋琛，碩士生，主研領域：社會網(wǎng)絡分析。張賢坤，教授。費松，碩士生。莢佳，碩士生。劉棟，副教授。

TP3

A

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