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

来源：计算机应用杂志2016年第6期北京时间：

作者：汪焱, 黄发良, 元昌安

单位：1. 福建师范大学 软件学院, 福州 350108;2. 科学计算与智能信息处理广西高校重点实验室, 南宁 530023

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

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

基金资助：国家自然科学基金资助项目(61363037);教育部人文社会科学研究青年基金资助项目(12YJCZH074);福建省教育厅A类项目(JA13077)。