基于SLPA改进的重叠社团检测算法

来源：计算机技术与发展杂志2024年第09期北京时间：

作者：胡志涛;余路粉;潘文林*

摘要：标签传播算法(Speaker-Listener Label Propagation Algorithm,SLPA)在重叠社团检测任务上具有线性时间复杂度和优良的检测效果,但作为一种随机算法其多次的随机选择策略致使算法的精度受限且算法结果不稳定;此外,算法在选取的阈值较低时容易出现大量相互嵌套的小型社团和重叠节点。 针对上述问题,提出一种精度更高、稳定性更好的改进算法。 算法初始化阶段,使用节点局部结构熵(Local Structure Entropy,LE)计算的节点重要性排序升序作为节点更新序列;标签传播阶段,使用资源分配指标(Resource Allocation,RA)作为节点进一步选择的依据,引导标签传播的方向;后处理阶段,新增两两对比待选社团集以去除嵌套包含的社团。 在真实网络与人工网络上验证算法的有效性,使用重叠标准互信息(Overlapping Normalized Mutual Information,NMIov)和扩展模块度(Extended Modularity,EQ)与 5 个经典算法进行对比。实验证明,改进算法在精度与经典算法相比具有优势,在真实网络和人工网络中均具备较好的鲁棒性;改进算法与原算法相比,算法的结果精度分布更为集中,算法的稳定性有提升。

关键词：复杂网络;重叠社团检测;标签传播算法;局部结构熵;SLPA