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

Semi-synchronous communities detection algorithm based on label influence

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

It is a great challenge to discover communities in the fast growing large-scale interactive social information networks such as Weibo and social networks. Although Label Propagation Algorithm（ LPA） has great advantage in time complexity,but its inherent multiple random strategies make the algorithm unstable. In order to solve the problem,a semisynchronous label propagation algorithm named Influence-driven Semi-synchronous Label Propagation Algorithm（ ISLPA） was proposed. The propagation oscillation was avoided effectively and the synchronous update between neighbor nodes was realized by abandoning the original random strategy and integrating node influence into label initialization,neighbor node selection and updated order determination. The experimental results from the real-world and artificial networks indicate that,in terms of validity and stability of generated communities from the networks,the proposed ISLPA outperforms the currently typical LPAs used in community detection.