基于标签传播的重叠社区发现研究

姜浩

摘要：标签传播算法[1]的优点使其广泛应用。但是标签传播算法规则简单、随机性大的特点，使其鲁棒性较差。为了满足实际复杂网络的需要，该文引入了生活中的选举模式到算法中，将标签传播算法传播规则进行了改进，赋予全部節点传播规则，使节点在传播过程中能够自主的更新标签，使其能够发现复杂网络中的重叠社区。

关键词：标签传播算法；重叠社区

中图分类号：TP3 文献标识码：A 文章编号：1009-3044（2018）28-0250-03

在网络中，一个节点可能属于多个社区，使得重叠社区研究得到了关注。Lancichinetti等人[2]提出了重叠社区挖掘的局部算法。Palla等人[3]在基于k-派系的基础上提出了一种重叠社区挖掘的算法。在Newman提出的模块度基础上，Shen等人[4]提出了划分重叠社区效果的评价指标，然后通过优化这个评价指标，从而提出了一种重叠社区挖掘算法[5]。Gregory[6]提出了一种两阶段策略的重叠社区挖掘算法。Chen等人[7]提出了一种快速的重叠社区挖掘算法，算法起初从只有一个节点的社区原始社区出发，利用滚雪球的方式对社区进行扩展。

本文通过引入生活中的选举模式，给予每个节点传播规则，通过给每个节点一个标签序列，对传播过程中接触到的标签进行存储与传播，并控制传播距离防止全局社区产生，从而实现了重叠社区网络的划分。

1 相关工作

1.1 相关算法

Jierui Xie等人在标签传播算法基础上提出了SLPA（Speaker-listener Label Propagation Algorithm）一种重叠社区发现算法[8]。SLPA算法在网络结构特征明显的社区中有良好性能。但是SLPA算法需要人为的设置参数用于选择标签，而找到一个合适的值很难。所以在大规模的网络中SLPA算法得不到扩展。

1.2 定义

定义1（节点影响力）给定网络G=（V，E），节点的影响力表现为u与其他节点之间的连接度，一般地，节点的度越高则其影响力越大，该节点的重要性越显著。节点u的影响力度量方法可形式化为公式（1）。

[Influ=v∈Nvdeguw∈Nvdegw] （1）

节点u的影响力；节点u的度；和节点u和节点的邻居集合。

定义2（候选者）选举起初选取部分影响力较大的节点，给予这些候选者唯一的初始标签且拥有统计票数的计数器BCounter，令候选者的节点集合为Vh。

定义3（胜出者）实施优胜劣汰的选举机制，失败的候选者降为投票者，胜利则保存原标签，令胜利者的节点集合为Vs。

定义4（投票者）影响力低的节点为投票者，投票者仅具有投票的权利，根据候选者或者胜出者的标签来更新自身的标签，令投票者集合为Vt。

2 算法

2.1 候选者产生阶段

在初始阶段，节点初始为投票人，并计算影响力，根据影响力的大小从每个节点的邻居节点集合中选取比例为θ候选者，然后给予这些节点一个唯一的标签，并存储到多维标签序列；剩余的节点标记为投票者，无标签。如图1所示，节点u原始标签为lk，多维标签序列中每个标签信息包含标签L={l1，l2，…，lk}、票数P={p1，p2，…，pk}和传播距离D={d1，d2，…，dk}，k与标签号相对应。开始阶段，票箱中拥有自身标签lk，传播距离为1，票数为1。

2.2 选举阶段

候选者产生后，它们之间开始竞争，通过对原有标签的总票数或节点总影响力的比较而进行投票，败者投票给胜者，然后把标签序列分别保存。如图2（a）所示，候选者v和候选者u进行比较，候选者v票数为2大于u票数1，失败的候选者u则把票投给胜利的候选者v。如图2（b）所示， 候选者v中l1 和候选者u中l2为外来标签，在存储标签时传播距离D衰减为e-1，计算传播距离的公式如（2）所示：

[d'=e1d] （2）

d?为记录传播后距离，d为传播距离。

投票者初始无标签，按比例θ把票投给邻居票数多的候选者，并按照票数进行存储标签排序。规则是迭代一次仅有一次投票机会，可以投多个胜出者但不能重复投一个胜出者。如图3所示，当投票者v投票候选者u时，投票者v把候选者u的标签信息保存到自身的标签序列中。

在此算法中，候选者的竞争主要包括2个阶段：

阶段1：候选者通过对节点总影响力或原有标签的总票数的比较而进行投票，败者投票给胜者，然后把标签序列分别保存。候选者u竞争的胜出者计算公式（3）的Vic（u）。

[VIcu=argmaxInflvif Inflv-Influ>0u otherwise] （3）

Infl（v）：节点v的影响力；N（u）：节点u的邻居。

阶段2：胜出者再进行比较选出新的胜出者，新胜出者的标签将存放在失败者本身的标签前（包括该失败者的投票者），重复如上操作，直到迭代数最大或票数稳定。阶段2通过公式（4） 迭代生成新胜出者。

[Vicu=argmaxv.BCounterif v.BCounter>u.BCounterv∈Nu∧v∈Vxu otherwise]（4）

u.BCounter表示节点u的票数。

每次投票结束，胜出者在下一轮选举前会先统计票数，公式如下：

[u.BCounter=u.Bbox+v∈Nuv.Bboxδlu，lv] （5）

u.Bbox：票箱Bbox中节点u的票数；u.BCounter：相邻节点与节点u同标签总票数。

2.3 调整阶段

在稳定后需要把支持率低或票数过低的胜出者筛选出去，然后再确定每个节点所属的社区。胜出者支持率Support（u）的计算公式如下所示：

[Supportu=v∈Vuδlu，lvdegu] （6）

deg（u）：节点u的邻居个数；：节点u同标签的节点数。过滤掉票数低于总票10%的胜出者和低于50%支持率的胜出者并降级。

2.4算法描述

算法为三个阶段：候选者产生阶段、选举阶段和整理阶段。步骤如下：

Step1：节点影响力的计算；

Step2：按比例θ将节点影响力高的选为候选者，并给予唯一标签。影响力低的为投票者，没有标签；

Step3；候选者u与邻居节点影响力大的候选者v比较，如果候选者u影响力大，则候选者u标签变为Lu={（lu，2），（lv，1）}并票数加1。反之同理；

Step4：竞争是相邻的候选者u和候选者v进行票数比较，若双方不含有对方标签需要比较后再存储。如果含有只需更新票数即可；

Step5：投票者按比例θ把票投给邻居节点中票数最多的胜出者，并将胜出者的标签保存到自身的标签序列中；

Step6：重复步骤4和步骤5，直到无投票行为；

Step7；调整阶段，过滤掉支持率低和票数少的胜出者，更新标签。

假设社区节点为n和边为m，则该算法的时间复杂度分析为：如果一个节点的影响力计算为O（m），则总的影响力为O（nm）；排序标签序列为O（KlogK），重叠社区最大数和K有关；迭代一次的时间复杂度为O（m+KlogK*n）。因此循环时间复杂度为O（P*（m+ KlogK*n））， 迭代的次数为P。所以，时间复杂度为O（P*（m+ KlogK*n））O（KlogK*n）即时间复杂度跟网络的重叠率相关。重叠率与K成正比，当K=1时，即为非重叠网络。

3 实验

运行的环境为Intel（R） Core（TM）i5-7200U CPU@2.50GHz 2.71GHz内存8G；软件环境为Windows10，Myeclipse（Version：10.7.1）；编程语言：JAVA。为验证算法的性能，采用了三类真实网络数据集，并选择SLPA算法进行效果对比。

3.1 实验数据

本文选取了3种常用的真实数据集，具体参数如表1所示。

3.2 实验评估方法

模块度是由Newman和Girvan于2004年[10]提出的，但是只針对于不重叠社区的情况。为了能研究重叠社区，一些学者对Newman提出的模块度进行扩展，从而使模块度得到发展。本文采用的是重叠社区的模块度指标Q0函数，由文献[14]提出，如公式7所示。

[Q0=12mc∈Pu，vacuacvAuv-kukv2m] （7）

A是网络的临界矩阵，若u和v 之间存在一条连边，那么Auv=1，否则Auv=0；m是网络的总边数；P是对应划分的社区集合；ku和kv分别是节点u和v的度；acu是节点隶属于社区的程度[10]。

3.3 实验结果分析

有效性分析。为了验证算法的有效性，分别对两种算法运行50次的Q0平均值进行汇总，具体如表2所示。

4 结论

本文提出了基于选举模式的标签传播重叠社区发现算法。其思想是，节点选取影响力大的邻居节点参加选举，候选者竞争逐步形成社区核心，投票者投票追随影响力大的核心，形成了以核心社区为主的社团。在真实网络实验中，表明该算法在重叠率低的社区网络中有良好的表现。

参考文献：

[1] Zhu X， Ghahramani Z. Learning from labeled and unlabeled date with label propagation[R]. Technical Report CMU-CALD-02-107，Carnegie Mellon University，2002.

[2] Lancichinetti A， Fortunato S， Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics，2009，11（3）：19-44.

[3] Palla G， Derényi I， Farkas I， et al. Uncovering thr overlapping community structure of complex networks in nature and society[J]. Nature，2005，435：814-818.

[4] Shen H W， Cheng X Q， Guo J F. Quantifying and identifying the overlapping community structure in networks[J]. Journal of Statistical Mechanics： Theory and Experiment，2009：07042.

[5] Shen H W， Cheng X Q， Cai K， et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A： Statistical Mechanics and its Applications，2009，388：1706-1712.

[6] Gregory S. Finding overlapping communities using disjoint community detection algorithms[J]. Studies in Computational Intelligence，2009，207：47-61.

[7] Chen D B， Shang M S， Lv Z， et al. Detecting overlapping communities of weighted networks via a local algorithm[J]. Physical A： Statistical Mechanics and its Applications，2010，389：4177-4187.

[8] Xie J， Szymanski B K， Liu X. SLPA： Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process[C]//2011 11th IEEE International Conference on Data Mining Workshops. IEEE Computer Society，2011：344-349.

[9] W.W. Zachary. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research， 1977，33（4）：452-473.

[10] Newman M E J. Finding community structure in networks using the eigenvectors of matrices. Phys[C]//Rev. E. 2006：036104.

[11] Newman M E J.A symmetrized snapshot of the structure of the Internet at the level of autonomous systems[EB/OL]. （2006-07-22）[2017-02-18]. http：//www-personal.umich.edu/～mejn/netdata.

[12] Lázár A， ábel D， Vicsek T. Modularity measure of networks with overlapping communities[J]. Europhysics Letters，2010，90：18001.

[13] Nepusz T， Petróczi A， Négyessy L， et al. Fuzzy communities and the concept of bridgeness in complex network[J]. Physical Review E， 2008，77：016107.

[14] Shang M S， Chen D B， Zhou T. Detecting overlapping communities based on community cores in complex networks[J]. Chinese Physics Letters， 2010，27：058901.

【通聯编辑：代影】