基于隨機(jī)游走相似度矩陣的改進(jìn)標(biāo)簽傳播算法

宋　琛　張賢坤　費(fèi)　松　莢　佳　劉　棟

(天津科技大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院　天津 300222)

?

基于隨機(jī)游走相似度矩陣的改進(jìn)標(biāo)簽傳播算法

宋琛張賢坤費(fèi)松莢佳劉棟

(天津科技大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院天津 300222)

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

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

0　引　言

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

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

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

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

1　標(biāo)簽傳播算法

1.1標(biāo)簽傳播算法描述

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

(1) 初始化社區(qū)，為圖中的每個(gè)節(jié)點(diǎn)隨機(jī)分配唯一的標(biāo)簽，用標(biāo)簽代表節(jié)點(diǎn)所在社區(qū)。

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

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

(4) 劃分社區(qū)，標(biāo)簽相同的節(jié)點(diǎn)歸屬同一社區(qū)。

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

圖1　標(biāo)簽傳播過程

1.2標(biāo)簽傳播算法存在的問題

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

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

2　基于隨機(jī)游走相似度矩陣的標(biāo)簽傳播算法

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

2.1隨機(jī)游走相似度矩陣的計(jì)算

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

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

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

(1)

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

(2)

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

(3)

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

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

(4)

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

(5)

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

(6)

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

圖3　存在多個(gè)頻率最高相鄰標(biāo)簽的簡(jiǎn)單網(wǎng)絡(luò)圖

圖4　相似度矩陣

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

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

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

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

2.2改進(jìn)算法描述

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

(1) 初始化社區(qū)，為圖中的每個(gè)節(jié)點(diǎn)隨機(jī)分配唯一的標(biāo)簽，用標(biāo)簽代表節(jié)點(diǎn)所在社區(qū)。

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

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

(4) 劃分社區(qū)，標(biāo)簽相同的節(jié)點(diǎn)歸屬同一社區(qū)。

3　實(shí)驗(yàn)及分析

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

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

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

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

(7)

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

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

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

4　結(jié)　語

本文對(duì)社區(qū)發(fā)現(xiàn)的常用算法進(jìn)行了介紹，并基于隨機(jī)游走的相似度矩陣對(duì)標(biāo)簽算法做出改進(jìn)。實(shí)驗(yàn)證明，RWLPA的效果優(yōu)于原始LPA算法。但算法對(duì)重疊社區(qū)考慮不足，同時(shí)矩陣的計(jì)算占用較多的資源，在未來可以對(duì)重疊社區(qū)進(jìn)行研究，改進(jìn)矩陣運(yùn)算方法，適應(yīng)現(xiàn)實(shí)網(wǎng)絡(luò)大規(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] 康旭彬,賈彩燕.一種改進(jìn)的標(biāo)簽傳播快速社區(qū)發(fā)現(xiàn)方法[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版,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] 石夢(mèng)雨,周勇,邢艷.基于LeaderRank的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法[J].計(jì)算機(jī)應(yīng)用，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)新資金項(xiàng)目(12ZXCXGX33500)。宋琛，碩士生，主研領(lǐng)域：社會(huì)網(wǎng)絡(luò)分析。張賢坤，教授。費(fèi)松，碩士生。莢佳，碩士生。劉棟，副教授。

TP3

A

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