基于成对约束的多标签传播重叠社区发现方法

丁建立，邵酉辰

(中国民航大学 计算机科学与技术学院，天津 300300)

0 引 言

标签传播社区发现算法[1-3]的时间复杂度为近似线性，是现今速度较快的方法。标签传播算法(label propagation algorithm，LPA)[4]综合了复杂网络的结构与传播特性，提出标签传播算法(label propagation algorithm，LPA)，但该算法并不能应用于重叠社区检测，且由于需要预先设定合适的参数以及在标签传播过程中具有随机性导致该算法的鲁棒性较差。多标签传播算法(community overlap pro-pagation algorithm，COPRA)[5]通过改进LPA算法实现重叠社区检测，但该类算法也同时继承了LPA算法随机性强、鲁棒性差的特点。基于标签传播增益的分层算法[6]，提高了COPRA算法的鲁棒性和准确性，但同时也增加了算法的时间复杂度。优化标签传播过程的算法[7]，通过对节点预排序降低了算法的随机性，又通过设置最大社区节点数提高了结果的稳定性。上述方法均为无监督算法，仅依赖于网络结构来进行社区划分，但是真实的网络复杂度较高，社区结构较模糊，导致传统方法在某些重叠度较高、社区结构不清晰的情况下检测准确性很低。在非重叠社区发现领域已经有学者尝试使用先验知识来指导社区划分，基于节点相似度的半监督社区发现算法[8]通过衍生规则对成对约束进行扩展，但其纳入全部的成对约束信息，算法代价较大。基于主动学习的纠错式半监督社区发现算法[9]，在聚类的过程中加入成对约束，通过纠正错误的划分使网络具有更明显的块结构，在保证算法精度的情况下大大降低了先验信息的所需数量。

基于此，本文提出一种基于成对约束的多标签传播重叠社区发现方法(PCMLPA)，引入成对约束指导重叠社区发现的过程，提高算法的准确性；提出约束集生成策略用于查找和扩展约束，提高标记的利用效率；基于COPRA算法改进节点的更新顺序，在保证算法较低时间复杂度的同时，解决COPRA鲁棒性差的问题。实验结果表明，本文方法在引入较少约束情形下具有更高的准确性，且鲁棒性强。

1 相关方法概述

1.1 COPRA核心思想

多标签传播重叠社区发现算法(COPRA)[5]的核心思想为：一个节点的标签由其邻居节点决定，一个节点可以拥有多个标签，迭代结束后对节点依据标签进行社区划分。为了避免所有节点经标签传播拥有全部的标签混淆为一个共同的大社区，文献[5]通过引入从属系数b(belonging coefficient)来衡量节点x对社区(标签)c的归属程度，公式表达为

(1)

其中，bt(c,x) 表示第t次迭代时节点x对于社区c的从属系数，N(x) 表示x的邻居节点集合， ∑y∈N(x)bt-1(c,y) 表示第t-1次迭代时x的全部邻居节点的标签及其从属系数的组合。文献[5]通过引入参数v(表示每个节点最多属于v个社区)，在每次迭代传播的过程中将从属系数b小于阈值(1/v)的标签删除，若b均小于阈值则保留b最大的标签，又若b最大值有多个则随机选取保留其一。

1.2 LeaderRank算法内涵

LeaderRank算法[10]，通过添加与其它全部节点相连接的节点g(ground node)，将网络转化为强连接图，从而可以得到唯一的排序结果。文献[10]将节点LeaderRank值(LR值)更新策略用公式表达为

(2)

其中，si(t+1) 表示第t+1次迭代时节点i的LR值，N(i) 表示节点i的邻居节点集合，kj表示节点j的度数，sj(t) 表示第t次迭代时节点j的LR值。收敛状态下LR值S的计算公式表达为

(3)

其中，Si表示节点i收敛状态下的LR值，si(tc) 表示收敛次数tc时的经式(2)算得的结果，sg(tc) 表示收敛状态下节点g的LR值。

2 基于成对约束的多标签传播重叠社区发现方法

2.1 约束集生成过程

2.1.1 成对约束特征

给定复杂网络G=(V，E)，V表示节点集，有节点vi∈V，E表示边集，有eij∈E表示网络中节点vi与节点vj的连边。半监督成对约束通常采用以下两种标记：

(1)must-link约束：标识两个节点属于同一社区。定义Cy表示must-link约束集，有 (vi,vj)∈Cy,i≠j表示节点vi与vj必须划分给同一社区；

(2)cannot-link约束：标识两个节点属于不同社区。定义Cn表示cannot-link约束集，有 (vi,vj)∈Cn,i≠j表示节点vi与vj必须划分给不同的社区。

成对约束在非重叠社区发现算法的应用中，must-link约束具有传递性，因而可以通过衍生关系规则[4]来对标记进行推理扩展，即3个节点vi,vj和vk，若存在 (vi,vj)∈Cy， (vi,vk)∈Cy则有 (vj,vk)∈Cy。 然而将成对约束引入重叠社区发现算法中，则不具有上述传递性，对于节点vi,vj和vk，存在 (vi,vj)∈Cy， (vi,vk)∈Cy， 无法推理得出 (vj,vk)∈Cy， 示例如图1所示。

图1 成对约束的衍生示例

图1中m表示两节点为must-link约束，从中可以看出在社区可重叠情况下，只给定 (vi,vj)∈Cy， (vi,vk)∈Cy， 并不能推理得出 (vj,vk)∈Cy。 当处理重叠度较高的网络时，上述情况将会更加频繁的发生，即使随机引入更多的成对约束也未必能够给算法带来更好的效果。

2.1.2 约束集生成过程

定义开放三元组(open triad)，给定3个节点vi,vj和vk，若其中两对节点有确定的must-link或cannot-link约束，剩余一对没有约束，则称节点vi,vj和vk构成开放三元组。

图2 初始约束集扩展示例

令所需约束的数量m/对，其中， (vi,vj)∈Cy称为一对约束。初始约束集的扩展示例如图2所示，该策略可描述为：

步骤1 在原始约束集中随机选择两个小型的初始约束集，包括must-link初始集合Cy和cannot-link初始集合Cn；

步骤2 将两个小型初始约束集转换为图(约束为边)，并在其中查找开放三元组，对于缺少边的节点约束到PC_data中查找结果；

步骤3 将步骤2的查找结果添加到对应的must-link初始集合或cannot-link初始集合中；

步骤4 重复步骤2～步骤3，直至所选取的约束数量达到m，得到must-link选择集合和cannot-link选择集合。

2.2 改进多标签传播算法

为了优化COPRA算法社区划分结果不稳定、鲁棒性差的问题，对其标签传播细节提出以下3点改进：

(1)节点的更新顺序(node update order，U)，采用1.2节介绍的LR值计算方法来衡量网络中节点的重要性，并降序排列作为节点的更新顺序；

(2)邻居节点的遍历顺序(traversal order of neighbor nodes，T)，采用相似度降序排列作为邻居节点的遍历顺序，节点相似度计算公式为

(4)

其中，δ(i)，δ(j) 分别表示节点i，j的所有邻居节点和自身节点的集合， |δ(i)| 表示集合中的节点个数。

(3)标签传播概率，P(i,j) 表示节点j的标签传播到节点i的概率，P(i,j) 的值取决于节点相似度Sij和邻接矩阵∂(i,j)， 公式表达为

P(i,j)=Sij×∂(i,j)

(5)

其中， ∂是网络的邻接矩阵表示，若节点i与j间有连边则∂(i,j)=1， 反之为0。

为了优化COPRA算法社区划分结果准确性不高的问题，提出基于成对约束的多标签传播重叠社区发现方法(PCMLPA)。结合2.1.2节方法所生成的约束集合，令单一节点所属的最大社区数为v，本文提出的基于成对约束的多标签传播重叠社区发现方法(PCMLPA)具体步骤如下：

首先，初始化节点标签(cx,1)，对于must-link约束标注的每对节点复制交换标签并归一化标签的社区从属系数，使得Σc∈label(x)b(c,x)=1； 其次，依据节点的更新顺序U，依次选取当前节点，并识别该节点全部的邻居节点，依据邻居节点的遍历顺序T，依次据式(1)对该节点进行标签传播，更新节点的标签数组label_array，其间添加所有来自must-link约束邻居节点的标签，删除所有来自cannot-link约束邻居节点的标签；再次，每更新完一个节点的全部标签，需对其进行过滤和归一化处理，删除从属系数b<1/v的标签，若该节点的所有标签均被过滤，则保留当前b最大的标签，后对其进行二次归一化，完成一轮全部节点的更新表示经过一次标签传播迭代；最后，当最近两次迭代的结果中标签的分布不再变化时，迭代停止，相同标签的节点划分为同一社区，并将结果做去重、归并处理，输出社区划分结果。

特别地，对于约束的处理机制有如下两个方面：

(1)对于每对must-link约束的节点，应保证其从属系数b最大的标签相同，若不同则在不含cannnot-link约束的节点标签情况下复制交换从属系数b最大的标签，并更新bt(c,x)；

(2)对于每对cannnot-link约束的节点，应保证二者不具有相同的标签，若含有同一标签则将该标签于相应从属系数较小的一方中移除，并更新bt(c,x)。

综上所述，基于成对约束的多标签传播社区发现方法对应的处理流程如图3所示。

图3 PCMLPA流程

3 实验与结果分析

本节旨在验证本文提出的PCMLPA方法较现有无监督重叠社区发现算法具有更高性能，并通过实验说明引入成对约束的量级对于重叠社区发现效果的影响。

3.1 数据集与实验设置

实验数据集选择人工合成网络和真实网络两种类型。

(1)人工合成网络：使用LFR[11]基准网络生成程序生成两种不同大小的合成网络LFR-1000和LFR-5000，参数设置见表1。

其中混合参数μ表示社区间边与社区内边的比值，值越大社区内连通性越弱，社区结构越模糊。通常不同的参数，如网络大小、社区规模、混合参数和重叠节点所属的社区数目(社区重叠度)等，会影响算法性能评估的结果。

(2)真实网络：选取3个有社区标注的真实网络(SNAP Datasets)：来自Amazon.com的共同购买网络，来自YouTube的友谊网络和来自DBLP的科学合作网络，统计数据见表2。

表1 人工网络的参数设置

表2 真实网络的数据统计

其中经预处理消除极小社区，Amazon和YouTube删除节点个数小于5的社区，DBLP删除节点个数小于10的社区。

3.2 评价标准

由于实验数据集中的社区结构已知，故使用归一化互信息NMI[12]来验证算法的准确性，NMI取值范围为[0,1]，值越大表明社区发现的结果越准确，公式表达为

(6)

其中，x表示真实的社区结构，y表示实验的社区划分结果。

考虑到引入相同数量的成对约束，对于不同规模的网络影响不同，故使用成对约束占总体可能组合的比重来度量引入约束的量级M，公式表达为

(7)

3.3 实验结果与分析

选取COPRA[5]和两种主流重叠社区发现方法OSLOM[13]、MOSES[14]作为基准算法，与本文PCMLPA方法在相同数据集上进行对比实验。其中，OSLOM算法是基于局部扩展的重叠社区发现方法，MOSES算法是基于节点隶属度的重叠社区发现方法。设置COPRA和本文PCMLPA的参数v=8。特别地，由于COPRA是非确定性算法，在实验中的结果波动较大因而取10次COPRA的运行结果NMI的平均值，又本文PCMLPA(M>0)方法中初始小型约束集的选择是随机的故重复实验取10次NMI的平均值。

人工合成网络的实验结果如图4和图5所示。

图4 算法在LFR-1000上的NMI比较

图5 算法在LFR-5000上的NMI比较

由图4和图5可得，①网络大小方面：网络中节点个数由1000增加到5000时，各算法性能均有所提升；②社区规模方面：本文方法准确性在社区规模较大(c:20-100)时较其它算法表现最佳，而另外3种基准算法则表现不一；③社区重叠度方面：伴随着重叠度的递增各算法的性能随之下降，但与此同时本文方法的结果更稳定，在om=8时表现出了明显的优势；④混合参数方面：随着μ值的增大，由于社区内的连通性变弱，各算法的NMI值均有所降低，但本文方法表现出了更高的稳定性和准确性。

真实网络的实验结果见表3。

表3 真实网络的实验结果

从表3中可以看出，本文PCMLPA方法在Amazon和DBLP网络上具有较高的NMI表现，分析在YouTube网络上NMI表现欠佳可能是由于该网络的社区结构较为模糊所导致。对比COPRA、OSLOM、MOSES、PCMLPA(M=0%)4种无监督方法，在社区重叠度更高、结构更为模糊的YouTube网络上，本文方法具有更加优秀的表现，在Amazon和DBLP两个网络上虽然结果不是最佳，但也几乎不逊于其它3种算法。对于添加约束后的PCMLPA方法，随着约束量级的增加(1%-5%)，实验效果稳步上升，预测加入更多的约束这种趋势会持续增长。

4 结束语

本文提出了一种基于成对约束的多标签传播重叠社区发现方法，通过引入编码为成对约束的先验知识来指导社区的划分，讨论了约束选择在非重叠社区发现与重叠社区发现中应用的区别，并给出了解决方案；改进COPRA算法的节点选择和标签传播更新过程，提高了算法鲁棒性和社区划分结果的准确度。实验结果表明：一方面，本文方法在不引入成对约束的情况下，鲁棒性更强，对于社区结构较为模糊的网络划分准确性较其它算法有明显提升；另一方面，实验结果验证了使用半监督策略寻找重叠社区的潜力，本文方法在引入5%成对约束的情况下在人工合成网络和真实网络上均显著优于现有其它无监督的重叠社区发现算法，且其性能会随着成对约束数量的增加而继续提高。在未来的工作中，将致力于应用主动学习的思想来更加充分、高效地利用尽量少的成对约束，减少相关标注的压力的同时进一步提高算法的有效性和准确性。