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

《Expert Systems with Applications》：Three-stage overlapping community detection algorithm based on label propagation

针对现有重叠社区检测算法的不足，本文提出三阶段基于标签传播的TPOC-LPA算法。创新点包括：1）节点重要性综合评估，2）社区紧密度-稀疏性指标设计，3）基于万有引力的吸引力模型，4）加权社区隶属度过滤机制。实验表明该算法在多个评估指标上显著优于现有方法。

　　

作者：孔志|霍明蕾|王立夫|郭戈

东北大学秦皇岛分校控制工程学院，中国秦皇岛 066004

摘要

在复杂网络中，重叠社区检测是一个重要的研究领域。目前，基于标签传播的重叠社区检测算法存在显著缺点。现有方法依赖于单一的节点重要性度量标准，这使得准确识别核心节点变得困难。传统的模块度量标准依赖于全局网络信息，导致在初始构建社区结构时计算复杂度高且效率低下。此外，一些算法在确定目标节点的社区归属时忽略了两个关键差异：它们没有考虑目标节点与其邻居节点之间的重要性差异，也没有考虑目标节点与其不同邻居节点之间的相似性差异，从而导致社区划分不准确。为了解决这些问题，本文提出了一种基于标签传播的三阶段重叠社区检测算法。该算法首先在社区预选阶段提出了一种结合社区紧密度和稀疏度的质量评估指标，通过优化该指标形成初始社区结构；其次，在社区演化阶段，它定义了节点吸引力和社区吸引力以决定节点的社区标签更新；最后，在社区标签过滤阶段，使用加权社区归属来过滤候选标签，从而得到更准确的重叠社区结构。所提出的算法在合成网络和真实网络上进行了测试。实验结果表明，该算法在多个评估指标上的表现显著优于现有的比较算法，实现了更高的准确性。

引言

在当今快速发展的数字和信息时代，各种复杂系统在现实世界中广泛存在，例如生物网络（Doluca O?uz (2021)）、信息网络（Liu, Liu, Dong, Mao, Cambria (2024)）和电力网络（Guerrero, Montoya, Banos, Alcayde, Gil (2018)）。这些复杂网络在不同领域发挥着重要作用。

社区是复杂网络中的常见结构，通常由多个社区组成。社区检测旨在准确高效地将网络的节点划分为不同的社区，从而有助于理解社区之间的关系并推断社区及其成员的功能（Zhao et al. (2025)）。

在社区检测研究中，重叠社区检测尤为重要。许多现实世界网络呈现出基于社区的结构，包含多个局部密集的社区。在每个社区内部，节点之间联系紧密，而社区之间的连接相对稀疏（Sun et al. (2025)）。此外，大多数现实世界网络都表现出重叠社区结构（Gu, Yang, Zhao, Li (2025)）。例如，在合著网络中，作者可能会与多个研究小组合作，因此同时属于不同的学术社区。节点在多个社区之间的重叠不仅反映了现实世界网络的结构复杂性，也为社区检测方法带来了更大的挑战。因此，开发能够识别这种重叠的技术已成为理解网络组织机制的关键焦点。

2005年，Palla等人首次引入了重叠社区的概念，并提出了CPM（Palla, Derényi, Farkas, & Vicsek (2005)算法来识别这些重叠社区。尽管CPM算法为重叠社区检测提供了有效的理论基础，但在大规模网络中其计算复杂性相对较高，尤其是在处理大量节点和边时，其时间和空间复杂性常常成为性能瓶颈。随着研究的进展，出现了各种类型的重叠社区检测算法，包括混合成员随机块概率模型（He Wang (2023)）、图注意力网络方法（Sismanis, Potikas, Souliou, & Pagourtzis (2025)）、非负矩阵分解方法（Zhuo, Chen, Yu, Cao (2024）和种子扩展方法（Li, He, Wu, Lv (2020)）。此外，基于标签传播的算法也成为了研究热点。标签传播算法（LPA）（Raghavan, Albert, Kumara (2007)）因其线性时间复杂性而受到越来越多的关注。然而，LPA算法仅适用于检测非重叠社区，限制了其在重叠社区检测中的应用。为了克服这一限制，COPRA算法（Gregory (2010)创新性地扩展了标签传播机制，允许节点属于多个社区，从而为检测重叠社区提供了新的方法。然而，由于标签选择的固有随机性，该算法的结果稳定性较低。随后，研究人员专注于提高算法准确性和减少随机性：LPANIS算法（Yu, Liu, Liang, Han, Xiong (2025）通过集成种子扩展、相似性预处理和标签传播能力计算，实现了非重叠和重叠社区的同时检测；PLPA算法（Sheng et al. (2019）将网络视为动态系统，根据节点偏好更新标签，在稀疏和模糊网络中表现优异，但在结构清晰的网络中存在准确性缺陷；一些研究（例如，El Kouni, Karoui, Romdhane (2020); Newman (2004)）利用节点重要性来识别核心节点，这些节点随后成为聚类的基础。NALPA算法（Zhang et al. (2020)从社会互动和雷达传输原理中汲取灵感，设计了新颖的节点能力和传播机制，虽然提高了稳定性和准确性，但其时间复杂性显著增加；NI-LPA算法（El Kouni et al. (2020)引入了节点重要性排名，改善了随机更新缺陷，但难以准确区分具有相似特征的节点；LPA-E算法（Chen, Liu, Chen, Cheng (2017)基于信息熵和成员系数优化了标签传播，但对初始条件敏感且容易陷入局部最优；NOHLPA算法（Zhang, Yu, Huo, Sui et al. (2021）结合了多层邻域重叠和历史标签相似性，提高了划分准确性，但显著增加了计算复杂性；FLPA算法（Yan, Yuan, Su, Zhang (2023)通过节点合并和权重计算加速了检测，但在密集或结构复杂的网络中合并效果有限；PECOPRA算法（Yan, Feng, Zhang, Xue, Li (2024)通过结合预处理优化和COPRA提高了准确性，但在大规模网络中面临计算效率瓶颈。

尽管上述基于标签的社区检测算法在研究方面取得了丰硕成果，但仍存在一些问题。

在识别核心节点的过程中，准确测量节点重要性至关重要。He Wang (2023)提出的方法仅依赖于节点度数，难以区分度数相同的节点。相比之下，El Kouni等人（2020）的方法结合了度数和聚类系数，这在一定程度上提高了区分度。然而，当节点在这两个指标上的结果相同时，仍然无法有效捕捉它们之间的重要性差异。初始社区结构的形成在社区检测中至关重要。模块度（Newman Girvan (2004)是评估社区质量的传统指标，但它依赖于整个网络的信息。每当节点标签发生变化时，模块度需要遍历整个网络来更新其值。因此，使用模块度作为优化指标来形成初始社区结构不仅增加了计算复杂性，还显著影响了评估效率。在确定目标节点的社区归属时，仅考虑了邻居节点中出现的社区标签频率，而没有考虑目标节点的邻居节点之间的重要性差异以及目标节点与其不同邻居节点之间的相似性差异。忽略这些差异可能导致社区划分结果不准确。

本文通过研究基于标签传播算法在复杂网络中检测重叠社区的问题来解决上述问题。本文的创新之处如下：

1.

提出了一种新的节点重要性定义，该定义在区分节点重要性方面具有更强的区分能力。这种度量方法有效地区分了度数相同且邻域结构相同的节点之间的重要性水平，从而提高了社区检测的稳定性和可靠性。

2.

本研究提出了一种新的评估指标——社区紧密度-稀疏度，用于评估单个社区的质量。与基于模块度的方法不同，这种局部可计算的指标消除了对全局网络信息的需求，显著提高了计算效率。此外，在用于初始社区选择时，它确保了社区演化的良好基础，从而有效抑制了演化过程中低质量社区的生成。

3.

基于万有引力原理，本文提出了节点吸引力和社区吸引力的定义，然后将其应用于节点社区标签更新的决策机制。这些定义量化了节点重要性和节点相似性的核心要素，从而更精确地描述了邻居节点对目标节点社区标签更新的不同影响，确保了目标节点社区标签分配的精确决策。

4.

本文定义了加权社区归属，以解决节点的多社区归属问题。在这种定义中，不同重要性级别的节点对加权社区归属的贡献被区别对待，以避免低重要性节点对归属产生过度影响，从而更准确地反映节点的实际归属。

部分片段

几个新定义

在下文中，网络被描述为图：$G=(V,E$ 其中V代表网络中实体的节点集合，E代表节点之间的边集合。本文仅考虑无向、无权网络。

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

研究了基于标签传播的重叠社区检测方法。该方法包括三个阶段：社区预选、社区演化和社区标签过滤。以下是该算法的详细描述。

实验环境

实验在配备8 GB RAM和2.40 GHz Intel i5-9300HX处理器的四核系统上进行。该系统运行MATLAB 2021a，并由Windows 10操作系统支持，确保了计算任务的最佳性能。

数据集

由于本文提出的算法是基于非重叠社区结构构建重叠社区的，我们将其与各种经典的非重叠社区检测算法和重叠社区检测算法进行了比较

比较与分析

本节通过与其他基线方法比较，评估和分析TPOC-LPA算法在非重叠和重叠社区检测中的性能。

TPOC-LPA中的参数α

作为关键参数，阈值α在社区预选阶段起着关键作用。当节点添加后的社区紧密度-稀疏度超过添加前的α倍时，该节点将被纳入社区；否则，将被排除。因此，α决定了新节点是否被TPOC-LPA算法接纳进入社区。

为了确定α的最佳范围，我们测试了八个具有已知社区结构的真实世界网络。

结论

本文提出了一种基于标签传播的三阶段重叠社区检测算法TPOC-LPA。该算法通过社区预选、演化和标签过滤来执行社区检测，提高了社区检测的准确性和鲁棒性，并能够高效检测重叠社区。 在合成网络和真实世界网络上进行了广泛的实验，用于非重叠和重叠社区检测任务。

未引用的参考文献

缺少引用：表14、图8。

CRediT作者贡献声明

孔志：方法论、概念化、调查、写作——审阅与编辑。霍明蕾：方法论、概念化、软件、写作——初稿。王立夫：可视化、写作——审阅与编辑。郭戈：概念化、写作——审阅与编辑。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。