一种基于节点相似度的标签传播算法

李卫疆+谢志勇+余正涛

摘 要：互联网技术的发展使诸如微博等社会网络的规模迅速增长，对这些网络进行挖掘分析，揭示网络特性对研究人们之间的联系具有重要意义。因此，发现高质量的网络社区结构是当前社会网络分析研究中的重要方向。传统的关系圈挖掘算法复杂度高，在大规模网络结构中性能下降。相比于传统社区发现算法，标签传播算法（LPA）具有时间复杂度上的巨大优势，而且其改进的SLPA还具有挖掘重叠社区的能力，但是标签传播算法内在的随机策略使得算法稳定性不高。针对标签传播算法的缺点，提出一种基于节点相似度的标签传播算法（NS-SLPA），根据节点相似度进行节点标签的初始化过程，以降低传播过程中的随机选择性。实验结果证明，NS-SLPA相比于SLPA，具有更高的稳定性和有效性。

关键词：社区发现；标签传播；社区重叠；节点相似

DOIDOI：10.11907/rjdk.172310

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）002-0063-05

0 引言

近年来，随着信息技术的高速发展，社会网络诸如微博、论坛等社会媒体迅速发展，成为人们交流感情、分享经验、传达信息的重要平台。

社会网络由社会活动中的个体及个体之间的关系所组成，社会网络通常被抽象成一个图G=（V，E）。其中，V表示顶点，代表社会网络中的个体；E表示顶点所在的边，表示个体之间的关系。而个体之间又组成各种大小不一的社区，社区结构一直是社区研究的热点问题之一。社区网络的社区概括而言是指社会网络中一组相似顶点构成的相互之间联系紧密的群体，而群体之间的联系相对较为稀疏[1]。例如某个人的朋友圈里有亲人、同学、朋友等小群体，亲人之间联系紧密，而亲人与同学之间联系甚少，而这是关系圈中普遍存在的现象。

对网络进行社区研究具有重要意义，如在人际关系圈中可以发现具有不同背景的社会团体，以方便进行不同的宣传策略；在社交媒体中，不同社区代表不同兴趣爱好的团体，可以为他们推荐好友，以更好地进行交流；在购物网络中，不同社区代表了具有不同购买力的人群，可以为他们推荐更适合的商品；在商品网络中，可以进行商品归类，对商品的价格、销售进行指导等。正是由于社区结构研究的重要意义，人们在社区网络的定义、发现与识别等方面作了大量研究，并提出了很多关于社区发现的算法。社区发现算法的出现为网络划分提供了很好的手段。以前很多社区发现算法都集中于研究如何对社区进行结构方面的划分，因此具有很大的局限性。因为社区网络不仅具有结构特性，还包括传播特性和节点间联系的紧密程度，而且这些算法未考虑到在大型网络上的应用要求，算法复杂度过高。近年来，研究人员主要考虑如何保证社区发现算法的效率和社區划分的准确性，并针对这些问题提出了很多经典算法，标签传播算法即是其中一种。

1 相关工作

下面通过介绍社区发现相关算法，引出本文的问题。

1.1 社区发现相关算法

Girvan和Newman[2]提出了GN算法，首先求解每条边的介数，然后将介数最大的边删去，再重新求解每条边新的介数，依此循环。但是求解介数时间复杂度高，在大图上并不实用；Pons和Latapy[3]提出一种基于随机游走策略的社区发现算法，该算法的基本思想是：首先用顶点相似性度量顶点间的距离，初始阶段每个节点都属于一个社区，然后根据某种策略进行游走，使顶点划分到其平方距离平均值最小的社区，而且每进行一步，都重新更新社区间的距离。但是该算法稳定性和效率不高；Radicchi等[4]提出另一种分裂的社区发现算法，该算法属于层次分裂算法，基本思路是将那些需要进行分离的树图进行迭代，找出符合定义的节点。该算法引入了一种称为边聚集系数的度量，边聚集系数定义为边所在的三角形个数与所有三角形的比值，并以此作为边移除的准则，但该方法时间复杂度过高；2007年Raghavan等[5]首先提出基于标签传播的社区发现算法（LPA），并在数据集上进行测试，结果显示LPA具有良好的社区结构测试效果。此后，LPA被不断改进。

1.2 基于标签传播的社区发现算法

算法基本步骤如下：

（1）节点标签初始化。在初始化阶段给每一个节点赋予一个节点标签。

（2）节点标签更新。对每个节点x，其邻居节点标签集合为N（y）={y1，y2，…，yk}，若N（y）中只有一个标签元素拥有最大重叠数，节点x则以此元素作为新标签；如果多个标签元素拥有最大重叠数，x随机选择一个最大的重叠元素作为新标签。重复以上操作，直到达到最大迭代次数T。

（3）社区划分。具有相同标签的节点属于同一社区。标签传播算法LPA时间复杂度低、算法简单、易于实现，且实用性强、分类效果好，因此迅速成为社区研究的热点，并得到了广泛应用，在网络结构分析和信息检索等方面取得了很多成果。但是标签传播算法存在自身的缺点，其标签在初始化和传播阶段都采用了一种随机选择策略，因此会产生很大的随机性，使划分结果不稳定。由于LPA算法存在的这些缺点，研究人员对该算法进行了很多改进，以期能高效地解决随机性问题，使其更加稳定、准确。

Barber等[6]在2009年提出了一种模块化标签传播算法（LPAm），该算法在RAK算法基础上引入了模块度最大化寻优目标函数，成功解决了LPA算法不稳定、易于产生大社区的问题；Liu等[7]结合LPAm与多步贪婪凝聚算法（MSG）提出了模块化专业化标签传播算法（LPAm+），解决了LPAm算法在模块空间中存在局部最大值的缺陷问题，使社区发现结果更加准确。此后，很多研究人员也针对标签传播算法LPA存在的问题对算法进行了改进，这些改进一定程度上解决了算法的随机性和不稳定性，但这些都属于非重叠社区发现算法，现实情况是在某个社区中的人可能和另外一些社区存在紧密关联，例如某些人既喜欢篮球又喜欢足球，那么他们可能既是篮球爱好者协会又是足球爱好者协会的会员，这些人的归属问题则不可忽略。因此，要求具有重叠社区挖掘能力的算法解决这些问题。endprint

针对重叠的网络结构，Gregory等[8]提出可识别重叠社区结构的COPRA算法。该算法基于LPA算法引入了社区从属系数，具备了重叠社区挖掘能力，但该算法并没有改变标签传播算法的随机选择问题，而且标签数量过多时，算法性能大幅降低；武志昊等[9]提出一种基于均衡多标签传播的重叠社团发现BMLPA算法。该算法对节点所属的社区个数没有限制，只要求同一节点的标签具有平衡的归属系数，但该算法的标签初始化策略使算法花费时间较长。

那有没有什么办法可以避免探测非重叠或重叠社区的时间复杂度问题，又能保持LPA算法的原有优点呢？针对该问题，Xie等[10]提出一种能够实现动态探测的重叠社区发现算法SLPA，SLPA 中引入了Listener和Speaker两个比较形象的概念。

SLPA设置了两个参数（T，r），T是最大迭代次数，r是过滤社区标签的阈值。与LPA相比，SLPA最大的特点在于它会记录每一个节点在刷新迭代过程中的历史标签序列（例如迭代T次，则每个节点将保存一个长度为T的序列）。当迭代停止后，对每一个节点历史标签序列中各互异标签出现的频率作统计。通过改变阈值r的值，可以去除那些概率较小的标签，只保留概率较大的标签。而且SLPA算法可以很容易地转换为LPA算法，当标签队列只能存储一个标签时，SLAP算法则退化为LPA算法，只能识别出非重叠社区。当r的值在0～0.5之间时，SLPA可以识别出重叠社区；当r的值大于0.5时，SLPA用于发现非重叠社区。

SLPA算法的实现步骤为：首先，在每一个节点的存储器中初始化一个唯一标签，然后重复以下步骤，直到达到最大迭代次数：①选择当前节点作为Listener；②当前节点的所有邻居节点根据一定的Speaking策略传递标签信息；③当前节点从邻居节点传播的标签信息集中，根据一定的Listener策略选择一个标签加载到自己的标签队列中，作为本次更新的标签。最后，后处理阶段根据节点的标签信息进行社区发现。

SLPA算法存在的问题包括：

（1）在标签初始化过程中，SLPA算法为每一个节点都分配一个唯一标签，对于复杂节点众多的复杂网络，标签分配会消耗大量资源。而且标签选择仍然存在随机性选择问题，因为第一次迭代时待更新标签会有多个候选标签，它会从邻居标签集合中随机选择一个作为新标签加载到自己的标签队列中。

（2）在标签传播过程中，Speaker策略是从邻居节点的标签队列中随机选择一个标签作为邻居节点标签集合的元素，而Listener策略是选择邻居节点标签集合中个数最多的那个标签作为当前节点的新标签，这种随机性选择造成了SLPA算法的随机性和不穩定性。

2 基于节点相似度的标签传播算法

由于SLPA的随机选择策略降低了算法的稳定性和准确性，因此本文提出一种基于节点相似度的标签传播算法NS-SLPA。本算法利用节点相似度改变标签的标签初始化过程，并在标签传播过程中降低SLPA的随机性选择。

2.1 节点相似度度量

2.1.1 基于共同邻居数的CN指标

从网络拓扑结构角度出发，考虑两个节点的共同邻居数，即Common Neighbors（CN）[11]。共同邻居CN是基于网络半结构信息定义相似度最简单的方法。两个节点拥有更多共同邻居，说明两个节点的联系更紧密，相似性也越大，因此越有可能归属于同一社区。例如，两个共同爱好篮球的人，他们彼此互不相识，但是两人有一些共同认识的喜欢篮球的人，如果他们相互认识的人很多，则两个人在同一地区或在同一个爱好者协会的可能性很大。

对于网络中某个节点Vx，其邻居节点集用Γ（x）表示，则任意两个节点Vx和Vy的相似度可表示为：

2.1.2 其它规范化指标

在CN指标的基础上增加节点度的影响，得到6 种规范的相似性指标，包括Salton指标[12]、Adamic-Adar指标[13]等，本文选用比较灵敏的Salton指标。Salton指标的定义是两个节点共同邻居数比上它们各自节点度之积的平方根，又称为余弦相似性：

2.2 基于节点相似度的标签传播算法NS-SLPA

本算法根据SLPA自身的特性，利用节点相似度改变标签的初始化过程，使节点初始化时按照节点度进行顺序排列，并给度最大的节点分配一个标签；然后计算当前节点和邻居节点的相似度，相似度大于与所有邻居的平均相似度时则分配与当前节点相同的标签；所有邻居判断完成后根据节点顺序重复以上操作，直到所有节点都有标签。标签传播过程若有多个最大重数标签时，则计算最大重数标签节点与待更新节点的平均相似度，待更新节点选择拥有最大平均相似度节点的标签进行更新。算法的全部描述如下：

输入：图G=（V，E）；

输出：各个社区C。

Begin

（1）为每个节点x提取出网络邻居集合N（x），并按照节点度进行排序。

（2）选取当前未处理的度最大的节点，为其分配唯一标签y。

（3）当前节点邻居集合为N（x），若当前节点与某个节点的相似度Sxy≥与所有邻居节点的平均相似度，则为其分配与当前节点相同的标签，并标记为已处理。

重复以上操作，直到所有节点x都有唯一的标签y。

（4）判断，t≤最大迭代次数T：①当前节点x作为Listener；②当前节点x的邻居根据Speaking策略，选择该节点在其存储器中出现频率最高的标签，进行标签传播；③当前节点x从邻居节点传播的标签信息集N（y）中选择最大重叠数标签y加载到自己的标签队列中，若有多个最大重叠数标签时，则计算拥有相同最大重叠数标签的节点与当前节点的平均相似度，选择与当前节点x拥有最大平均相似度节点的标签作为更新标签。

（5）节点更新完毕，令t=t+1。endprint

（6）当t>T时，根据阈值r划分节点x所属的社区C。

End

3 实验分析

3.1 实验结果评价指标

3.1.1 模块度Q

对复杂网络进行社区划分，需要有一些评价指标，以评判算法对网络划分结果的好坏优劣。Newman等提出了模块度Q函数，该函数被广泛应用于社会网络分析中衡量关系圈挖掘的好坏，是最常用的一种评价标准。其表示公式如下：

3.1.2 标准化互信息NMI

NMI是一种基于信息论理论的社区质量评价指标[14]，它通过计算已知社区结构和由算法得到的社区结构之间的相似度实现网络社区结构质量的测度。其值越大，说明算法结果社区与真实社区结构相一致的程度越高，具体公式如下：

3.2 实验结果分析

3.2.1 小规模数据集实验

选取“Social Analysis 973”区两个规模较小的数据集进行实验，分别是科学家合作网络和Enron电子邮件网络，科学家合作网络只选取相似度大于0.5的用户节点，用户若相互合作，则建立一条边。网络属性如表1所示。

从模块度Q、规范化互信息NMI角度衡量算法性能，如图1、图2所示。

从图1、图2中可以看出，在比较简单的网络中，NS-SLPA算法所获得的模块度和准确性都要高于SLPA算法。虽然模块度Q提升并不是很明显，但在准确度方面，NS-SLPA有着SLPA算法无可比拟的优势，使准确度有了较大程度的提升。

3.2.2 较大规模网络数据集实验

选用两个人工生成网络，人工网络是由网络数据生成器LFR模拟生成的，通过LFR提供的丰富接口可灵活设置网络节点、平均节点度与网络模块化度等参数，从而获得不同类型的网络数据。两个人工网络的网络属性如表2所示。

其中，μ是指网络中社区间的连接数占所有边总和的比例，实验结果如图3、图4所示。

从图3、图4可以看出，在迭代次数较小时，NS-SLPA算法的模块度和精确度明显高于SLPA算法；随着迭代次数增加，两种算法在模块度和准确度上都有增长趋势，但SLPA的波动幅度更大，且稳定性差，在大型网络中表现得尤为明显，而NS-SLPA算法更加稳定。

4 结语

本文针对社区发现算法SLPA的缺陷提出了一种基于节点相似度的标签传播算法NS-SLPA，通过在标签初始化阶段，让节点按节点度进行排序，并根据节点相似度对邻居节点赋予标签，大大简化了标签初始化过程中的资源消耗；在标签传播过程中，通过标签节点的平均相似度降低标签的随机行选择，增加了算法的稳定性与准确性。在多个数据集上进行实验，证明了NS-SLPA算法比SLPA算法拥有更高的准确性和稳定性，而且在较复杂的网络中表现更加明显。

参考文献：

[1] 王恒军.社团网络的有限时间聚类同步研究[D].南昌：江西师范大学，2016.

[2] NEWMAN ME， GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E，2004，69（2）：026113.

[3] P PONS， M LAPATY. Computing communities in large networks using random walks[J]. Journal of Graph Algorithms& Applications，2004，3733（2）：284-293.

[4] RADICCHI F， CASTELLANO C， CECCONI F， et al. Defining and identifying communities in Networks[J]. The National Academy of Sciences，2004，101（9）：2658-2663.

[5] U N RAGHAVAN， R ALBERT， S KUMARA. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E，2007，76（3）：036106.

[6] BARBERMJ， CLARKJW. Detecting network communities by propagating labels under constraint[J]. Physical Review E，2009，80（2）：129-139.

[7] LIU X， MURATA T. Advanced modularity-specialized label propagation algorithm fordetecting communities in networks[J]. Physical a Statistical Mechanics and Its Applications，2010，389（7）：1493-1500.

[8] GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics，2010，12（10）：103-123.

[9] 武志昊，林友芳，田盛丰，等.高度重叠社区的社区合并优化算法[J].北京交通大学学报，2011，35（3）：116-122.

[10] XIE J， SZYMANKI BK， LIU X. SLPA： uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]. 2011 11th IEEE International Conference on Data MiningWorkshops. IEEE Computer Society，2011：344-349.

[11] 郭婷婷，趙承业.基于共同邻居的链路预测新指标[J].中国计量学院学报，2016，27（1）：121-124.

[12] G SALTON， M J MCGILL. Introduction to modern information retrieval[M]. McGraw-Hill，1983，41（4）：305-306.

[13] LA ADAMIC，E ADAR. Friends and neighbors on the Web[J].Social Networks，2003，25（3）：211-230.

[14] 汪焱，黄发良，元昌安.基于标签影响力的半同步社区发现算法[C].计算机应用，2016，36（6）：1573-1578.endprint