基于随机游走相似度矩阵的改进标签传播算法

宋　琛　张贤坤　费　松　荚　佳　刘　栋

(天津科技大学计算机科学与信息工程学院　天津 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