一种局部强化的多标签传播社区发现算法

A Local Strengthened Multi-label Propagation Algorithm for Community Detection

在社交网络中,社区和圈子均表现为一组内部连接相对紧密的节点,但后者规模较小。圈子是重要的局部社区信息,利用这一特点有助于进行社区发现。然而,现有的大部分基于标签传播的社区发现算法并没有考虑圈子的信息。为此,提出一种基于局部强化的多标签传播(LSMLP)社区发现算法。给出圈子的定义,提出一种基于圈子信息的迭代多标签传播策略,并从每个节点的多个标签中选择归属系数最大的标签作为其从属的临时社区。采用两步优化方法使模度最大化。在真实网络的数据实验结果表明,与已有的社区发现算法相比,LSMLP算法能更高效地发现社区。

In the social networks, community and circle are groups of vertices with relatively dense intra-connection, but the circle is of small-scale. Intuitively, circles are important local information and community detection can benefit from them. Unfortunately, in most existing label propagation methods for community detection, the circle-based information is not taken into account. Aiming at this problem, this paper proposes a Local Strengthened Multi-label Propagation（LSMLP） algorithm for community detection. It first gives the definition of circle and then proposes an iterative strategy for multi-label propagation by using circle-based information. Based on a modularity optimization, a unique label can be selected from multi-labels. Performance properties of the LSMLP are discussed and compared with some related methods on several real networks. The method is more highly efficient and effective for uncovering communities.