基于标签传播的社区发现新算法.pdf

《基于标签传播的社区发现新算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、DesignandResearch设计与研究基于标签传播的社区发现新算法Anewalgorithmofdetectingcommunitybasedonlabelpropagation李俊郭洪(福州大学数学与计算机科学学院福建福州350108)摘要：基于标签传播的社区发现算法是社区发现的一类算法，该算法为网络中的每一个结点分配一个唯一的初始标签，通过标签传播来发现社区。由于其过程中存在很多随机性，易造成结果的不稳定，加之用于评价的属性比较单一。使算法结果有偏差。本文引入社区模块度来评价结果，对该算法加以改进。得到一个新的基于

2、标签传播的社区发现算法。经过社会网络社区发现标准数据集的验证。结果表明新算法的稳定性和适应性有所加强。关键词：在线社会网络。社区发现。标签传播中图分类号：TP3191引言签稳定。4)将具有相同标签的结点划分成一个社区。博客，微博等社交网站是当下流行的在线社会该算法具有接近线性的时间复杂度，为结点分网络。在这些网络中，用户与用户之间存在着一些配标签的时间复杂度为O(n)，每次迭代更新时间为诸如好友、关注等等的关系。在社交网站中，越来O(m)，找出所有社区的复杂度为O(m+n)。Raghavan越多的用户，因为现实生活中的好友关

3、系、相同的等人通过实验认为只要经过5次迭代就能将95％以上兴趣、或者其他各种联系，逐渐形成了一些规模不的顶点正确分类，因此整个迭代过程有接近0(m+n)一的团体，即社会网络中的社区结构。在线社会网的时间复杂度。络研究通常用图表示网络、图中的结点表示用户、2．2模块化度量边表示关系。通过对社区的划分，可以获得一些有Newman和Girva提出一个评价社区质量的指价值的信息。高效地得到高质量的社区已成为在线标，称为模块化度量(modularitymeasure)。模块度社会网络中的一项研究热点。Q的计算公式表达如下：2基于标签传

4、播的社区发现算法Q嚣(警一)(1)2．1算法步骤其中I是标签为C的社区中两端都在社区内的边该算法从一个全新的视角来看待社区发现，其的数量，0是标签为C的社区中一端在社区内另一端的主要步骤如下：在社区外的边的数量，E是这个网络中边的数量。1)为所有结点分配一个唯一的标签(1abe1)，3基于标签传播的社区发现新算法用于标签传播和社区的界定，每个特定的标签就代表一个社区。3．1模块度贡献及评价函数2)遍历所有结点，计算每个结点的邻居中不同为了得到高的模块度，在更新结点标签的时标签的出现次数并进行比较，选中其中个数最多的候，参考模

5、块度贡献，模块度贡献定义为结点标签标签作为目标结点的新标签，个数相同的情况下，更新前后模块度的差值。原目标结点x的标签为e，随机选取一个标签来更新。将它的标签更新为c’的模块度贡献为：3)重复步骤2)的迭代过程，直到各结点的标Mk嚣q(c)4-q(c，)一(c)’一q(c’y(2)木工机床2015No．1l7设计与研究DesignandResearch的前2+N期，运用d1)作为标签选择的评价q(c)=一)(3)函数时，出现重复的几率较大。因此，当出现重复的时候，再引入一个评价函数neiD(c’)，neiD(c’)目q(c)

6、，=(等一)(4)标结点邻居中标签为C’的结点邻居结点度数的总q(c)为标签为c的社区在节点x更新前的模块度，和，当有不同标签的评价函数出现相同值时，选择q(c)’为标签为e的社区在节点x更新后的模块度，neiD(e’1大的标签，这样函数的随机性再次减小。q(c’)以及q(e’)’同理。在计算模块度贡献的时3．4算法伪代码候，节点x的标签值并没有更新，只是计算如果更新综上所述，新算法的伪代码可以表示如下：成邻居中的各节点时产生的模块度贡献。Input：G(V，E)从结构上考虑社区发现，还需要考虑图结构上11为每一个结点设置一

7、个初始标签值。的一些特征。因此在标签的选择上除了模块度贡献2)将结点按照结点度从小到大排序。还考虑了结点度的因素，得到最后的评价函数：31设置记录迭代次数的参数i=0。)M(1一)(5)41根据结点度从小到大的顺序，遍历每个结其中di)是结点邻居中标签为c’的结占的点，并更新标签度数和，av。D为整个网络中结点的平均度，0i)i(i<2))llbel∞；m艘d(cf))在公式f(c’)中起辅助作用，当Mcc’值差距较小l曲心<=armmax(ndD(c'T~时，后者发挥作用。分母中的aveD起到e1seif(i>=2))∞羽

8、gl掰Ⅸ(c))控制作用，使得l一雨值的差距缩小，最l抽H

9、l∞(ne蠹

10、)(嘞后结点X的标签更新为：5)if(每个结点的标签值有更新){i+=1；goto4)；瑚，el∞趣1溅(6)}else{算法结束3．2特殊的迭代周期在前几次迭代周期中，社区的规模还比较小，4实验社区结构还不明显，因