具有对偶约束的半监督重叠社区发现方法

许小媛，李海波，于本成，刘 芳

(1.江苏开放大学信息工程学院，江苏 南京 210017； 2.中国矿业大学计算机科学与技术学院，江苏 徐州 221116)

0 引 言

在机器学习领域，许多应用不能完全精准地区分有监督学习和无监督学习[1]，所提供的背景知识亦十分有限。监督通常采用成对约束的形式，这种约束描述了数据对象之间的关系，已被用于指导和提高聚类算法的有效性,半监督学习的概念扩展到了网络分析领域。社区发现等任务可能受益于引入来自单个领域专家或群智的有限监督，这类知识通常被编码为约束，表明一对节点应始终分配给同一社区或始终不分配给同一个社区。通过这些知识，可以潜在地发现在分析大型或嘈杂网络时难以识别的节点社区。

最初社区发现的研究工作集中在开发产生不相交群的算法，其中的每一个节点属于一个社区[2]。然而，在许多实际网络中，节点将自然地属于多个社区。无论是在线社交网络还是离线社交网络，都可以观察到无处不在的重叠，其中个人属于高度重叠的社交群体[3]。最近，已有重叠社区的发现算法应用于这些真实网络[2，4]。与此相反，在半监督的重叠社区发现方面，继续侧重于那些相互独立的情况。

本文提出一种基于贪心策略的局部扩展[5]半监督社区查找方法，并将其称为基于对偶约束的局部扩展(半监督重叠社区发现)算法PC-GCE(Pairwise Constrained Greedy Clique Expansion)。在进程的初始化阶段和子社区扩展过程中引入必须链接和不可能链接的约束。对基准合成网络的实验评估表明，引入相对较小的约束数可以提高正确发现这些网络中潜在社区的能力。

1 相关工作

1.1 社区发现

发现非重叠社区。在此背景下，算法可以大致分为3种类型。1)层次算法。基于网络拓扑结构构建社区树。这些算法可以是2种类型之一：分裂算法[6]或凝聚算法[7]。2)基于模块化的算法。对已知的模块化目标函数进行优化，并发现网络[8]中的社区。3)其他算法。这类算法包括基于标签传播方法的算法，利用拉普拉斯矩阵或标准矩阵特征向量的谱算法，以及基于统计模型[9]的方法。

发现重叠社区。在此背景下，现有的算法可以分为4大类。1)节点种子和局部扩展算法。这种算法从一个节点或一组节点开始检测社区，然后使用质量函数将它们扩展到一个社区。OSLOM[10]就是这种算法的一个例子，它使用一个统计函数来计算节点值，并将其扩展到一个社区。另一个例子是MOSES[11]，它是一个基于统计模型的算法，使用目标函数作为贪心策略的优化技术。2)集群扩张算法。这种方法使用一组称为clique(集群)的全链接节点作为展开的起点。CFinder[1]和贪心集群扩张算法(GCE)[12]就是这种算法的例子。3)链接聚类。这类算法通过分割链接而不是节点[13-16]来检测一致性。4)标签传播。该策略根据相邻节点的相似性将每个节点划分为一个社区。COPRA算法[11]就是一个例子。

1.2 半监督学习

通过已有的几种形式的先验知识来指导社区的决策过程。最广泛使用的是成对约束(必须链接或不能链接)，其含义表示2个节点必须在同一个社区中，或者必须在不同的社区中。这种约束已经在几种算法中实现，包括基于模块的方法[17]、光谱分析方法[5,12]和基于矩阵分解的方法[18-19]。其他算法利用节点标签作为先验知识，代替约束，改进了社区检测[20]的过程。在文献[21-22]中，作者提出了一种根据节点标签和负信息的半监督标签传播算法。

在这一领域，绝大多数半监督算法的目标是检测不相交的社区，而许多现实世界的网络是包含重叠社区的。据笔者所知，在寻找重叠社区方面人们所做的工作很少。在文献[8]中，使用了一小组称为种子的节点，将这些节点与社区的亲缘关系作为先验知识来推断网络中其他节点的亲缘关系。以下，本文重点讨论半监督社区寻找适合于包含重叠社区网络的应用程序的问题。

2 算法使用

2.1 贪心集群扩张算法(GCE)

GCE[16]社区搜索算法首先将最大的群体作为种子，然后通过优化局部适应度函数，贪心地将这些种子扩展为更大的群体。给定网络G，用户指定的最小小圈子大小为k，最小社区距离为ε，GCE算法包括以下步骤：

1)找到种子，这些种子都是G中具有至少k个节点的最大团体。

2)选择最大的未扩展种子，并通过使用社区适应度函数FS贪婪地将其扩展到候选社区C′，直到添加任何节点不会增加适应度值。

3)测试C′与所有先前接受的社区之间的距离。如果C′与现有社区C之间的距离小于给定的阈值ε，则认为C和C′无限接近，因此舍弃C′，否则，保留C′。

4)重复步骤2和步骤3，直到不再有种子。

GCE定义了适应度函数[14]来扩展每个种子，函数描述了给定社区S中节点k的入度和出度，公式如下：

(1)

其中，参数α通常采用[0.9,1.5]范围内的值。可以使用适应度函数FS总结贪心策略的扩展步骤如下：

1)对于给定种子S边界中的每个节点v，计算v的适应度值。例如，如果将节点v添加到S，则S的社区适应度将改变。

2)选择具有最大适应度值的节点vmax。

3)如果适应度值vmax为正，则将节点v插入S并返回步骤1，否则，终止并返回S。

为了在GCE算法的步骤4中丢弃近似重复的社区，本文提出使用基于重叠的2个社区之间的距离度量：

(2)

鉴于2个社区S和S′中，公式(2)的测量包括较小社区中的节点，忽略了较大社区的节点。对于给定的一组社区集合，离给定社区S的距离小于给定的阈值的所有社区都被判定为S的重叠社区。

2.2 社区检测中的成对约束

给定包含一组节点v的网络，半监督的成对约束通常采用2种可能的形式：

1)必然连接(must-link)约束指定2个节点属于同一簇类。令CML为must-link约束集，对于∀vi,vj∈v，当i≠j，(vi,vj)∈CML表示必须将2个节点vi和vj分配给同一社区。

2)不可能连接(cannot-link)约束指定2个节点必须属于不同簇类。令CCL为cannot-link约束集，对于∀vi,vj∈v，当i≠j，(vi,vj)∈CCL表示必须将2个节点vi和vj分配给不同社区。

3)选择这种约束形式最简单的方法是随机选择一对节点(vi,vj)，并查询权威数据判断应该采用must-link还是cannot-link约束。重复该过程以选择所需数量的约束或直到部分监督预算用完。在非重叠的社区查找中，must-link约束具有传递属性，其中第3个must-link关系可以从其他2个关联的must-link约束对推断出来。所以，如果(vi,vj)∈CML，且有(vj,vk)∈CML，那么也可以推断出(vi,vk)∈CML。如图1所示，在非重叠的情况下，传递属性允许从2个现有的must-link约束推断出第3个must-link约束。

图1 非重叠社区

但是，这并不会自动适用于重叠的情况，其中存在2种可能的情况。由于传递属性不再成立，将约束纳入重叠社区则更具挑战性。

图2 重叠社区

如图2所示，具体来说，如果(vi,vj)∈CML，且(vj,vk)∈CML那么(vi,vk)有2种可能的情况，要么(vi,vk)∈CML，要么(vi,vk)∈CCL。这是因为重叠节点vj具备节点vi和vk的must-link约束，但这2个节点分属于2个不同的社区。但也有可能，这3个节点实际上是位于同一社区中。除非在算法中明确(vi,vk)是must-link约束还是cannot-link约束，否则无法有效区分这2种情况。网络若具有高度重叠的社区，那么这种有问题的情况将更频繁地发生。如果单纯地试图将成对约束结合起来，而不考虑这种情况，那么在社区发现的过程中，即使增加约束，社区发现的结果并不令人满意。

要解决此问题，在选择成对约束之后，需要检测从任意2个must-link链接对中派生出的cannot-link对，并将其插入到cannot-link集中。但是，这将显著增加无链接约束的集合。例如，如果只想提供5个成对约束，每个约束如图3所示，插入所需的cannot-link对将使cannot-link集的大小加倍。在下一节中，将介绍解决此问题的方法。

图3 扩展5个约束对的情况

2.3 半监督的GCE

本文提出的方法是有限的监督下的重叠社区发现，称为成对约束GCE或对偶约束GCE (PC-GCE)方法。该方法由2个阶段组成：第1个阶段包括选择和预处理约束，解决了重叠社区中must-link约束缺乏传递性的问题；第2个阶段为GCE算法提供约束，以便在社区检测过程中处理这些约束。具体描述如下：

阶段1：选择和预处理约束。在这个阶段，可以将成对约束集视为一个新集，如果它们共享成对约束(must-link或cannot-link)，则在原始网络的2个节点之间存在邻接点。然后在must-link集涉及的节点中寻找所有可能的禁用三元组。给定3个节点A、B、C，当A连接到B和C时发生禁用三元组(或开放三元组)，但B和C之间不存在邻接点。在预处理步骤中，寻找这样的情况，比如判断B和C之间是否存在must-link或cannot-link。为了控制约束集的大小，该方法“贪心”地对它进行扩展，直到达到预定义的最大尺寸。这个阶段实现步骤如下(见图4)：

1)选择must-link和cannot-link的初始随机集。

2)在must-link集中查找所有可能的禁止三元组，以便在数据库中查询它们之间的关系。

3)如果它们的关系是must-link，则将其插入到must-link集中，否则将其插入到cannot-link集中。

4)重复以上步骤，直到设置达到最大尺寸。

在该阶段结束时，成对约束集即完成以用于GCE算法进行社区检测。

阶段2：成对约束的GCE(PC-GCE)。在社区检测阶段，只将cannot-link约束结合到现有的GCE算法中，实现步骤如下(见图5)：

1)找到种子，这些种子都是网络G中具有至少k个节点的最大团体。

2)选择最大的未扩展种子，并通过使用社区适应度函数(公式(1))贪婪地将其扩展到候选社区C′，直到添加任何节点都不再增加适应度值。但是，在扩展过程中，不要添加任何节点，该节点与种子中的任何现有节点都是cannot-link。

3)检查C′中所有节点对之间是否存在任何cannot-link约束。如果存在这样的对，则计算2个节点相对于C′的适应度，并移除值较低的节点。

4)使用公式(2)测试社区C′与所有已接受社区之间的距离。如果C′与任何已接受社区C之间的距离<ε，则C′和C接近重叠，丢弃C′，否则，接受C′。

5)返回步骤2并重复该过程，直到没有种子冗余。

在社区发现的过程中只采用cannot-link约束的原因是：由于种子扩展步骤的贪婪性质，将must-link约束纳入此步骤会导致相当大社区数量变少。主要使用适应度函数作为将群集扩展到社区的局部优化技术已经实现了一些must-link关系，并且处理cannot-link集将主要检测从2个链接的must-link对中派生的对。因此，使用算法处理的must-link集将是额外的对非信息性约束的处理，这会对算法产生噪声并降低精度。

图4 半监督GCE阶段1涉及的4个步骤

图5 半监督GCE阶段2涉及的4个步骤

3 实验结果及分析

本文通过在包含重叠社区的2组人工合成网络上进行实验来评估PC-GCE的性能。为了进行对比，将PC-GCE的结果与以下无监督重叠社区检测算法进行比较：标准GCE[16]、OSLOM[13]、MOSES[5]和COPRA[11]。

3.1 实验数据

实验中使用的合成网络是用广泛使用的LFR基准网络生成器[15]生成的，它可以生成具有类似真实网络属性的人工合成网络，它也包含嵌入式地面真实社区。表1中列出了用于生成网络的所有参数值。

表1 用于生成LFR合成网络参数值

在实验中，生成2组不同的网络，分别包含小型社区和大型社区。小型社区有10～50个节点，而大社区有20～100个节点。每组由16个具有2个参数Om和On的不同组合的网络组成，参数Om控制每个节点的社区数量，On控制重叠节点的数量。对于每组中的第一个网络，所有节点属于2个社区(Om=2)，然后对于每个连续网络，该参数的值递增1，直到Om=5。对于每个参数值Om，将重叠节点参数On增加25%，直到100%的节点属于多个社区。

3.2 实验步骤

为了比较不同算法在实验中的性能，本文使用了标准归一化互信息(NMI)测量重叠[14]。该算法度量在网络中使用算法产生的社区与地面真实社区之间的一致性。若A值接近1表示高度一致，接近0表示算法社区并不比随机产生的社区好。

进行了2个实验。第一个实验旨在测量所选社区检测算法的当前性能，使用GCE算法所得的结果作为评估PC-GCE算法性能的基准。第二个实验评估针对不同约束数，PC-GCE的性能，每个网络中可能的约束对数量占总数的1%到5%。在该实验中，随机选择初始约束对；然后重复20次以上并对NMI分数进行平均；最后，将PC-GCE获得的结果与选定的基准算法进行比较。

3.3 实验结果分析

实验采用2步比较和评估结果。首先，将PC-GCE的准确性与标准GCE进行比较(如表2)。其次，比较了PC-GCE算法与其他基准算法的准确性(如表3)。

从表2中可见，在大多数情况下，无论网络中重叠节点的比例如何，PC-GCE都优于标准GCE算法。更具体地说，对于重叠节点分数的所有度量，随着成对约束的百分比增加，PC-GCE的准确度也提高。另一方面，当将重叠节点On的比例从节点总数的25%增加到100%时，GCE的NMI下降到0的情况几乎占总结果集的60%。又如，在小型社区网络的情况下，对于Om=3时，GCE的NMI值从0.7636降到0，对于Om=4，NMI从0.6484降至0。对比一下，PC-GCE算法随着On值的增加，准确度会适当降低，这表明PC-GCE在高度重叠的社区中优于标准GCE。但是，通常，2种算法在包含较小社区的网络上都表现出更好的性能。

表2 小型和大型社区网络中运用PC-GCE的NMI值(约束对占比0～5%)

大型社区网络每个节点的社区数(Om)201%2%3%4%5%GCEPC-GCE重叠节点数(On)2500.96920.97040.97120.97220.97200.97245000.98500.99020.99230.99310.99540.99587500.94420.96500.97500.97840.98150.986010000.82090.86200.88430.88610.88950.8946301%2%3%4%5%GCEPC-GCE重叠节点数(On)2500.65400.67550.67600.67670.67720.67765000.62750.66600.68540.69320.70400.70867500.49520.56460.58660.59620.62240.624010000.25770.28880.30760.32500.33140.3494401%2%3%4%5%GCEPC-GCE重叠节点数(On)2500.55900.55960.56060.56160.56100.56225000.44000.46220.47520.48620.48860.49547500.10310.12800.15860.16640.17540.177410000.00000.01060.01100.01420.01520.0211501%2%3%4%5%GCEPC-GCE重叠节点数(On)2500.46660.46680.46720.46800.46860.46865000.19800.20820.23140.24880.25880.26927500.00000.06360.07840.07980.07620.081510000.00000.00000.00000.00020.00000.0000

从表3可以看出，PC-GCE算法在2种网络中性能均优于COPRA算法。当考虑重叠节点数最小(即On=250)时，COPRA与PC-GCE几乎相当。然而，随着On值的增加，COPRA的性能下降到0，而PC-GCE的性能仅显示略微下降。因此，可以得出结论，PC-GCE算法在高度重叠的社区网络上优于COPRA。另一方面，PC-GCE在大型网络上优于MOSES，但在小型网络上表现出几乎相似的性能。最后，在2种类型的网络中，使OSLOM的NMI得分与PC-GCE的整体性能相当。

表3 小型和大型社区网络中应用无监督算法的NMI值

小型社区网络每个节点的社区数(Om)COPRA2345重叠节点数(On)2500.75360.61380.49500.35955000.56640.00000.00000.00007500.00000.00000.00000.000010000.00000.00000.00000.0000

小型社区网络每个节点的社区数(Om)OSLOM2345重叠节点数(On)2500.97320.91460.79620.71685000.94350.84960.60200.31727500.92400.67890.22990.077710000.89520.37170.00980.0000

大型社区网络每个节点的社区数(Om)MOSES2345重叠节点数(On)2500.61400.54480.45950.42445000.53380.44980.34950.31987500.47880.34350.17960.096010000.57400.19890.01910.0000

大型社区网络每个节点的社区数(Om)COPRA2345重叠节点数(On)2500.71200.62350.48440.43775000.52160.00000.00000.00007500.00000.00000.00000.000010000.00000.00000.00000.0000

大型社区网络每个节点的社区数(Om)OSLOM2345重叠节点数(On)2500.95240.86000.70760.64245000.90770.73750.46460.22857500.90250.49080.17800.072510000.86180.13820.00000.0000

4 结束语

本文探讨了半监督策略在网络中寻找重叠社区的潜力，提出了一种新的基于成对(对偶)约束的重叠社区检测算法(PC-GCE)。大量实验表明，基于对偶约束的GCE算法性能优于基于无约束的重叠社区发现算法，并且随着成对约束数量的增加，其性能有所提高。这显示了本文采用半监督策略寻找重叠社区的潜力。然而，在大多数网络中，只有一小部分节点具有成对的信息约束。因此，使用成对约束的随机选择可能会产生负面影响，因为选择非信息性节点会降低社区检测过程的准确性。未来的工作将致力于应用主动学习的思想来选择成对的信息约束，以及探讨不正确的“噪声”约束的影响及其对算法性能的影响。