基于标签传播的重叠社区检测算法

陈 旭 张 俊 曲贤菲 田朝霞

(大连海事大学信息科学技术学院 辽宁 大连 116026)

0 引 言

现实世界中包括社会科学、生物信息、计算机等许多领域的网络都可以用复杂网络来表示，社区结构是复杂网络的重要特性[1]，揭示网络中存在的社区结构有利于从网络中挖掘出有实际意义的模块或层次结构，有助于理解和分析网络的拓扑结构和功能特性，具有重要的研究价值。早期对于社区检测的研究主要关注网络中非重叠社区结构，即假设每个节点仅属于单个社区，而在现实网络中，往往存在一些节点同时属于多个社区的情况，即社区间会存在交叉重叠现象而非彼此独立，这类社区结构被称为重叠社区[2]。从网络中检测出重叠社区更具现实意义。

当前针对重叠社区检测问题提出的算法大致分为基于派系过滤的方法、基于线图与边分割的方法、基于局部扩展与优化的方法、基于模糊检测的方法和基于标签传播的方法等[3]。随着网络数据规模的增长，近线性时间复杂度的标签传播算法(Label Propagation Algorithm，LPA)[4]在社区检测领域得到很大发展，Raghavan等[5]提出的RAK算法是首次将LPA算法应用到社区检测的方法，其基本思想：为每个节点设置一个唯一标签，节点的标签按照该节点的邻居节点中标签频率最高的标签进行更新，带有相同标签的节点被划分到同一社区。然而基于LPA的算法虽然简单高效，但其随机性造成检测结果的不稳定，也无法检测到重叠社区结构，为此提出了很多基于LPA的改进算法。Gregory[6]在LPA的基础上提出基于标签传播的重叠社区检测算法(Community Overlap Propagation Algorithm，COPRA)，首次将标签传播应用到重叠社区检测，该算法引入归属系数，允许每个节点保留多个标签实现重叠社区发现，但运行结果同样存在随机性的问题，并且需要预设节点所属的最大社区数，该参数的选择在真实未知的网络中是很难把握的。刘世超等[7]基于COPRA算法改进了网络的传播特性，固定节点的更新顺序提高算法的稳定性，同时考虑节点属性和历史标签信息对传播的影响，提高结果的准确性，但仍要预设节点所属的最大社区数；Xie等[8]提出的SLPA算法是基于Speaker-Listener的信息传播过程。该算法随机选择一个节点作为Listener接收作为Speaker的邻居发送的标签，算法根据成对交互规则在节点之间传播标签。该算法会将历史标签考虑在内，为每个节点提供内存存储每轮迭代选择的标签，最后对标签进行后处理输出重叠社区。另外SLPA不需要预先设置社区数量，但在交互规则上仍然存在随机性导致算法结果的不稳定。赵雨露等[9]针对SLPA选择Listener节点时的随机性给所有节点排序更新标签来降低算法结果的不稳定性，但忽略了节点自身属性和历史标签影响力会随时间衰减的要素。

本文针对现有标签传播算法存在的一些不足，提出一种新的重叠社区检测算法SLPA-TD：计算节点的影响力，固定节点标签的更新顺序，以此增强算法的稳定性；设计新的标签传播的Speaker-Listener规则，考虑节点标签的影响随时间衰减，并结合节点属性和邻域结构信息更新标签，进一步提高检测结果的质量。

1 算法相关描述

1.1 相关定义

定义1重叠度(Overlap Degree,OD)。网络图G=(V,E)，C={C1,C2,…,Ck}是网络G中节点的一个划分，每个集合Ci代表一个社区，社区Ci和Cj的节点数分别为|Ci|和|Cj|，则社区之间的重叠度定义如下：

(1)

若OD(Ci,Cj)=0，则社区Ci和Cj互不相交；若OD(Ci,Cj)=1，则社区Ci(Cj)包含于另一个社区Cj(Ci)之中；若0

定义2重叠社区。重叠社区的定义由上述重叠度进一步给出，当0

定义3邻域相似度(Neighborhood Similarity,NS)。

(2)

式中：Γ(X)为节点X及其邻居节点的集合；K(X)为节点X的度。

定义4属性相似度(Attribute Similarity,AS)。采用余弦相似度方法比较节点属性值计算相似度，该过程与计算文本相似度类似。将节点的属性进行词频向量化得到节点X和节点Y的属性词频向量分别为A=(a1,a2,…,am)和B=(b1,b2,…,bm)，则节点X和节点Y的属性相似度表示为：

(3)

定义5节点相似度(Similarity,S)。

(4)

节点间的邻域相似度越高意味着这两个节点共享的邻居越多，节点在同一个社区的概率越大。同理，属性相似度代表着节点之间的相关性，属性相似度越高，表明两节点在同一个社区的可能性越高[10]。

1.2 节点影响力排序

本文利用综合考虑节点邻居数和聚类系数影响的排序算法ClusterRank[11]计算节点的影响力，按此排序固定节点标签的更新顺序，从而增强算法的稳定性。该算法在有向和无向网络都可使用。

本文采用无向版本，节点i的ClusterRank得分Si定义为：

(5)

f(ci)=10-ci

(6)

式中：ci为节点i的局部聚类系数，Γi为节点i的邻居节点的集合，kj表示节点j的度数，f(ci)表明节点i的聚类系数对信息传播的影响，由于局部聚类起负面作用，因此f(ci)与ci呈负相关[12]。

1.3 标签时间衰减

标签时间衰减表示节点历史标签的重要性随时间衰减，这里的随时间衰减实际是指随迭代次数的衰减。基于标签传播的算法是在一次次的迭代中标签逐渐趋于收敛和稳定的过程，也就是说迭代后期比迭代前期节点存储的标签更有影响力，因此节点在最近一次迭代中保存的标签的重要性在该节点的当前标签中是最大的，即节点历史标签的重要性随时间衰减。

本文受牛顿冷却定律思想的启发，即物体的冷却速度与其当前温度与室温之间的温差成正比，将其中包含的指数衰减的思路应用到历史标签影响随时间衰减的计算过程中进行标签选择。

由牛顿冷却定律的一阶微分方程可以推导出温度和时间的关系函数，由此得到温度随时间呈指数衰减的过程，即某温度的下降速度和该温度值成比例。将指数衰减扩展到一般化过程的数学公式为：

N(t)=N0·e-αt

(7)

式中：N(t)为某个量N在t时刻的数值，N0为N在0时刻的初始数值，即N开始指数衰减时的最初也是最大值，t为衰减时间，α为衰减常数，也就是N的衰减速率，通常根据实际情况自行选择合适的数值。

回到本文的历史标签重要性随时间衰减问题，在标签更新过程中，每迭代一次，节点内存就添加一个标签，内存中的所有标签的重要性在整个迭代周期内进行时间衰减，在这里用Score表示标签重要性(Score越大，标签越重要)，在每轮迭代中，计算节点内存中的全部标签的Score，同一节点内存中的相同标签的Score累加作为该标签当前对于该节点的重要性，节点各标签的Score在迭代更新过程中进行标签选择时会发挥作用。

Score=e-λ·Δt

(8)

式中：λ为衰减因子，这里取迭代周期T的倒数1/T，Δt为时间间隔，以迭代次数为单位，Δt=T+1-T′，T′为迭代次序。

下面举例说明，为简化计算过程，设迭代周期T为5次，λ为1/5，节点a内存中的标签从第0次迭代(初始化)到第5次迭代依次为[a,b,c,b,d,c]，默认节点自身id作为初始化标签。

初始化：标签a的Score=e-0.2(5+1-0)≈0.301；内存中的标签：(a，0.301)。

第1次迭代：标签b的Score=e-0.2(5+1-1)≈0.368；内存中的标签：(a，0.301)，(b，0.368)。

第2次迭代：标签c的Score=e-0.2(5+1-2)≈0.449；内存中的标签：(a，0.301)，(b，0.368)，(c，0.449)。

第3次迭代：标签b的Score=e-0.2(5+1-3)≈0.549；内存中的标签：(a，0.301)，(b，0.368)，(c，0.449)，(b，0.549)。

第4次迭代：标签d的Score=e-0.2(5+1-4)≈0.670；内存中的标签：(a，0.301)，(b，0.368)，(c，0.449)，(b，0.549)，(d，0.670)。

第5次迭代：标签c的Score=e-0.2(5+1-5)≈0.819；内存中的标签：(a，0.301)，(b，0.368)，(c，0.449)，(b，0.549)，(d，0.670)，(c，0.819)。

上述过程使得节点历史标签的重要性随时间衰减，不再与最新标签等同，遵循标签重要性随时间衰减的思想更加合理。

1.4 设计Speaker-Listener规则

Speaker-Listener规则是节点的标签传播过程要遵循的规则，当前要更新标签的节点为Listener，该节点的邻居节点为Speaker。

Speaker-Listener规则分为Speaker规则和Listener规则两部分。

1) Speaker规则为Speaker节点向Listener节点发送标签时遵循的传播规则，即具体如何选择自身内存的标签进行传播。本文提出的Speaker规则如下：

(1) 计算Speaker节点内存中当前各标签的Score，并将同一节点下相同标签的Score累加。

(2) Speaker节点选择各自内存中Score累计值最大的标签发送给Listener节点。

2) Listener规则为Listener节点从Speaker节点发送的众多标签中选择一个标签存储到自身内存所遵循的规则。本文提出的Listener规则如下：

(1) Listener节点将收到的标签中相同标签的Score分别累加，选择Score最大的标签。

(2) 若Score最大的标签有多个可选，计算出Listener节点和各个发送最大Score标签的Speaker节点的节点相似度S，选择与Listener节点的节点相似度最大的节点发送的标签。

先前大多数算法的Speaker规则都是在Speaker节点内存中选择出现频率最高的标签发送给Listener节点，不但忽略了历史标签的时间衰减影响，还很容易出现标签频率相同而随机选择的状况，考虑到时间衰减的影响后可以很好地避免这样的情况发生。另外，加入了节点相似度的Listener规则进一步降低了算法在标签选择过程的随机性。

1.5 迭代次数和阈值

基于SLPA的算法一般采用固定迭代次数的方式结束算法，经验表明[8]，当T>20时，算法的输出相对稳定，与网络的大小与结构无关。当然，如果条件允许，适当增加迭代次数更能保证输出结果的稳定。阈值r用来筛选算法结束后得到的节点内存的标签，比较节点内存各标签比重与阈值r，删除比重小于阈值r的标签，带有多个标签的节点即为重叠节点，表明该节点同时属于多个社区。由于本文侧重于重叠社区的检测，阈值r的取值范围设为[0,0.5]，当r超过0.5时，该算法输出非重叠社区。阈值r取值越小产生的社区数越多，可以根据实际情况进行调整。

1.6 SLPA-TD算法

SLPA-TD算法伪代码如算法1所示。

算法1SLPA-TD

输入: T, r

输出: overlapping communities

1. Initialization:

2. for i=1:n

3. Nodes(i).memory[0]=i

4.Si=Nodes(i).clusterRank()

5. sortSiin descending order

6. Updating labels:

7. for t=1:T

8. for each node i in updating order

9. Listener=Nodes(i)

10. Speakers=Nodes(i).getNeibs()

11. LabelList={}

12. for j in Speakers

13. l=Speakers(j).speakerRule()

14. LabelList.addLabel(l)

15. label=Listener.listenerRule()

16. Nodes(i).memory[t]=label

17. Post-processing:

18. for i=1:n

19. remove labels in Nodes(i).memory with probability

20. Output overlapping communities

该算法共分为三个部分：节点初始化，为每个节点分配内存储存标签，用节点自身id作为初始化标签存入节点内存，用ClusterRank算法计算节点影响力，由大到小作为节点标签更新顺序；开始标签更新过程，直到达到最大迭代次数T：按更新顺序选择一个节点作为Listener，分配一个临时内存存放该节点在其邻居节点(即Speaker)接收到的标签，每个Speaker节点按照Speaker规则在其内存中选择一个标签发送给Listener节点，Listener节点在接收的多个标签中按照Listener规则选择一个标签存入自身内存中；根据阈值r处理节点内存中的标签，删除小于阈值的标签，将具有相同标签的节点划分到同一社区，输出重叠社区。

1.7 算法时间复杂度

设网络有n个节点和m条边，迭代次数为T(用户设置，本文T=50)：节点内存的标签初始化需要O(n)；计算节点影响力和排序得到节点的标签更新顺序需要O(nlogn)；标签传播更新过程需要O(Tm)；处理标签和划分社区需要O(Tn)；因此算法整体的时间复杂度为O(nlogn)。

2 实验与评估

本文分别在基准数据集和真实数据集上进行实验，对于已知社区结构的基准网络上的实验，采用标准互信息(Normalized Mutual Information,NMI)作为评估指标，而在真实数据集上的实验使用扩展模块度(Extended Modularity,EQ)来检验算法结果。选择经典的重叠社区检测算法SLPA算法和基于SLPA的改进算法SLPA-CM与本文算法进行比较，验证本文算法的有效性和准确性。

本文的实验配置为Windows 7操作系统、Intel(R) Core(TM) i5- 4590 3.30 GHz处理器和8.00 GB内存，所有的算法都由Python实现。

2.1 评估指标

(1) 标准互信息(NMI)。标准互信息是适用于已知网络社区真实结构的经典评估指标，是由Lancichinetti等[14]基于先前非重叠指标NMI[13]提出的用于衡量重叠社区检测结果的扩展NMI，该指标实际是在比较检测结果和真实结构的相似度。NMI值介于0到1之间，值越大表示检测结果和真实结构越接近。

(9)

式中：X、Y分别代表用于比较的两种划分C1和C2，H(X|Y)norm为X相对于Y的标准化条件熵。

(2) 扩展模块度(EQ)。对于网络结构未知的真实数据集，本文采用Shen等[15]提出的扩展模块度EQ进行评价，EQ是模块度Q[16]的扩展，是常用的用于网络结构未知的重叠社区检测的评估指标。EQ值范围为[0,1]，EQ值越大表明社区划分质量越好。当网络中无重叠时，EQ退化为Q。

(10)

2.2 基准数据集实验

表1 两种基准网络LFR1和LFR2的主要参数

本文比较的3个算法SLPA、SLPA-CM、SLPA-TD的参数设置：T=50，r=(0.05,0.5)，其中对于参数r取值不确定的情况，每次增加0.05，选择使得NMI值取最大的数值作为参数r的取值；SLPA-CM控制最大社区节点数的参数按文献[9]设置Maxc=0.4n。

图1和图2为各算法的NMI值分别在网络的On=10%和On=50%的情况下随Om变化的对比图。各NMI值为3个算法运行20次的平均值。

图1 On =10%时的NMI值

图2 On =50%时的NMI值

如图1和图2所示，当On从10%变为50%时各算法的NMI值呈显著下降趋势，并且无论是在网络的On=10%还是On=50%的情况下，3个算法的NMI值都随Om的增加而降低，这说明随着网络重叠节点数量的增加和重叠程度的加深，社区检测的难度也加大了。总体看来，本文算法下的NMI值始终高于SLPA算法和SLPA-CM算法，其在Om各个取值下的NMI表现与SLPA算法和SLPA-CM算法比较平均提高了15%和10%，验证了本文算法的有效性，同时表明考虑到历史标签影响力随时间衰减的该算法能够进一步提高检测结果的质量。

2.3 真实数据集实验

本文选取了5个不同规模的真实数据集进行实验，表2为各个数据集的基本信息。

表2 真实数据集基本信息

本文所有实验均是在无向网络中进行，个别算法要求数据集节点带有属性，故以上为处理后的数据集，其中一些数据集的节点属性信息无法获取，当需要计算节点相似度时只考虑其结构相似度。

图3为各个算法在5个真实网络上划分重叠社区得到的EM值，各算法的参数设置同基准网络实验时一样，EM值为各算法运行20次的平均值。从图中可以看到SLPA-TD算法的划分结果最好，其EM值始终高于其他两个算法，平均提高了17%和9%。尤其是在带有节点属性的两个数据集上的表现，考虑了节点相似度的SLPA-TD算法的优势更加明显。

图3 真实网络划分结果的EM值

3 结 语

本文基于标签传播的思想，针对现有标签传播算法存在的一些不足进行改进，提出一种新的重叠社区检测算法SLPA-TD，计算节点的影响力固定节点标签的更新顺序，设计新的节点标签的传播规则，考虑节点历史标签随时间衰减的影响，结合节点相似度更新标签。实验验证了本文算法的有效性，与之前算法相比，不仅大大降低结果的随机性，还提高了社区划分的质量，尤其是在具有节点属性信息的网络上。但这些仅是该算法在静态网络中的表现，未来工作会考虑将该算法应用到动态网络上。