基于模糊聚类和标签传播的社会社区检测方法，采用Cuckoo Search算法实现

《IEEE Transactions on Signal and Information Processing over Networks》：Fuzzy Aggregation and Label Propagation Based Social Community Detection Using Cuckoo Search

社区检测两步框架：首先通过聚合（扩展-溶解）形成近似社区，解决重叠问题；其次采用标签传播结合萤火虫算法优化目标函数，实现非重叠社区划分。实验表明该方法在真实和模拟社交网络中优于现有方法。

　　

摘要：

在社交网络中，一个节点不仅仅属于某个紧密的群体；它可能被归类到许多相似或不同的社区中。社交网络中的社区检测问题类似于网络聚类问题，其中信息存储在节点属性和网络结构中。基于节点的特征常用于无监督算法中，这些算法可以部分地检测出局部和重叠的社区。具有社区结构的网络也可能表现出层次化的社区。识别具有层次结构的社区是一项具有挑战性的任务。本文提出了一个两步框架，即聚合和标签传播，以识别清晰且不重叠的社区。聚合是一种扩展-解散技术，能够生成不需要任何先验信息的清晰社区。我们首先为每个节点估计随机社区，并应用聚合来改进它们。第二步是基于标签传播的目标最大化方法，该方法将改进后的清晰社区视为模糊矩阵，从而得到不重叠的社区。标签传播方法是一种针对邻居属于不同社区的节点的标签更新机制。标签传播函数通过布谷鸟搜索进行最大化，并报告优化后的社区。该两步框架在真实和模拟的社交网络上进行了实证测试。使用基于性能和准确性的指标进行了比较和对比研究，以验证该框架的有效性，结果表明其处于领先水平。

引言

网络可以构成复杂系统中节点之间的关系。这些关系可以被视为特征，并在节点之间传播信息[1]。社交网络、通信网络、生物网络、供应链网络和万维网就是这样的例子。随着在线社交网络的出现，社区检测成为识别相似群体的一个研究热点。我们模拟了节点之间的社会关系，其中社区内的节点之间连接紧密，而社区外的节点之间连接稀疏。在社交网络中，可能存在两种类型的社区：1）不相交的社区；2）重叠的社区。如果所有节点都属于互斥的社区，则称为不相交集；如果一个节点属于多个社区，则称为重叠社区。在这项工作中，我们主要关注不相交集的社区检测，为此已经有一些基本方法[2]。 [3]提出了一种基于子图的聚类方法，该方法利用高度紧密的内部结构来识别不相交的簇。一些研究人员将这一概念扩展到了多目标优化问题中。适应度函数基于簇内和簇间的边。当社区数量增加时，进化算法的性能会下降，因为进化优化中的社区向量无法反映社区结构[4]。因此，建议对进化算法进行一些修改，以便识别小的局部社区。由于社区结构的复杂性，在无监督社区检测算法中，对社区的先验知识非常重要。因此，本文提出了一个两步框架，首先通过节点聚合来识别所需的社区，然后使用标签传播方法进行优化。第一步可以称为解决方案空间过滤，第二步称为解决方案改进。第一步，即聚合，是一个两步机制，通过利用社交网络的结构来扩展和解散社区，从而得到一个近似过滤后的社区向量。如果社区之间的入度和出度比例增加，则扩展是有效的。随后进行解散操作，即从社区中移除一个节点应使比例值增加。这一步的输出称为过滤后的社区，其中仍然可能存在重叠社区；因此，下一步是找到不重叠的社区。在第二步中，标签传播方法改进了解决方案空间。标签传播是一种用于检测不重叠社区的方法。标签传播方法针对每个社区节点进行操作，根据邻居节点的标签来更改当前节点的标签。如果大多数邻居的标签不同，则当前节点的社区将被替换为其相邻社区的标签[5]。接下来，目标是为实现不重叠和不相交的社区而制定。第一步得到的过滤后的社区被模糊化，然后使用基于布谷鸟搜索的进化优化来最大化基于标签传播的目标函数。布谷鸟搜索在研究领域是一种广泛应用的算法，可以实现快速收敛和全局搜索[6]。布谷鸟搜索通过控制强度和多样性两种启发式方法来寻找全局最优解。第二步的结果在实验部分与现有技术进行了比较。图1(a)展示了我们提出的框架的图形流程，该框架采用两步方法来发现社区簇。图1(b)表示流程图。