APP下载

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

2018-01-04姜浩

电脑知识与技术 2018年28期
关键词:候选者投票者票数

姜浩

摘要:标签传播算法[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.

【通聯编辑:代影】

猜你喜欢

候选者投票者票数
我能猜到你心里的数字
我能猜到你心里的数字
2017年度河南省武术“十大杰出贡献人物”评选前50名榜单
微信投票乱局与治道变革
英国人家有空房少拿养老金
塔利班割鼻惩罚投票者
无用的工作
专家和读者评荐 本刊编委会评定 1989年《军事历史》优秀论文(按评荐票数多少的顺序排列)