基于标签影响力的半同步社区发现算法

汪焱 黄发良 元昌安

摘 要：微博网络与社交网络等的交互式社会信息网络规模的快速增长对社区发现提出巨大挑战。标签传播算法（LPA）虽然在时间复杂度上具有很大的优势，但是其内在的多种随机策略使得算法稳定性不高。针对LPA的随机问题，提出了一种基于影响力的半同步标签传播算法（ISLPA），能有效地避免振荡问题，巧妙地实现了相邻节点之间的同步更新，并结合影响力从初始标签、选择邻居节点和更新顺序三方面进行了改进，摒弃了原有的随机策略。真实网络和人工网络的实验结果表明，ISLPA具有较高的稳定性与有效性，与其他LPA相关算法相比存在明显的优势。

关键词：社区发现；标签传播法；半同步；节点影响力；振荡

中图分类号： TP393 文献标志码：A英文标题