基于标签传播的重叠社团发现算法

Overlapping Community Discovery Algorithm Based on Label Propagation

说话者-侦听器标签传播算法(Speaker-Listener Label Propagation Algorithm,SLPA)以标签传播算法为基础,通过Speaker和Listener互动的动态过程来发现网络中的重叠社团,时间复杂度近似线性,但在标签传播过程中存在随机性,并且在应用到大规模网络时节点标签初始化需耗费大量的资源。针对以上问题,通过改进SLPA设计了一种基于标签传播的重叠社团发现算法(Overlapping Community Division Algorithm Based on Label Propagation,LP-OCD)。该算法在每个节点存储器初始化标签之前,利用K-Shell分解算法对网络进行预处理,去除边缘层节点;在标签更新阶段,通过改进Speaking和Listening策略来降低算法的随机性;后处理阶段边缘层节点的标签由其邻居节点信息决定。实验结果表明,LP-OCD算法不仅具有近似线性的时间复杂度,而且显著提高了所发现重叠社团的质量。

Based on the label propagation algorithm,the Speaker-Listener Label Propagation Algorithm(SLPA)discovers the overlapping communities in the network through the dynamic process of interaction between Speaker and Listener.The time complexity is approximately linear.However,there is randomness in the process of label propagation,and the initialization of node labels takes a lot of resources when it is applied to large-scale networks.To solve the above problems,an overlapping community discovery algorithm Overlapping Community Division Algorithm Based on Label Propagation(LP-OCD)based on label propagation is designed by improving SLPA.The algorithm preprocesses the network with the K-Shell decomposition algorithm to remove the edge layer nodes before each node memory initializes the label.In the label update phase,the randomness of the algorithm is reduced by improving Speaking and Listening strategies.Labels of all edge-layer nodes in the post-processing stage are determined by the information of their neighbors.Experimental results on social networks show that the LP-OCD algorithm not only has approximately linear time complexity,but also significantly improves the quality of the overlapping communities discovered.