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

A Local Strengthened Multi-label Propagation Algorithm for Community Detection

作　　者：马千里[1] 张俊浩[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510006

出　　处：《计算机工程》2014年第6期171-174,179,共5页Computer Engineering

基　　金：中央高校基本科研业务费专项基金资助项目(2012ZZ0064);教育部高等学校博士学科点专项科研基金资助项目(20110172120027);国家大学生创新性实验计划基金资助项目(111056155);广东省自然科学基金资助项目(S2012010009961);广东省教育部产学研结合基金资助项目(2011B090400032);广东省电子商务市场应用技术重点实验室开放基金资助项目(2011GDEC0F01)

摘　　要：在社交网络中,社区和圈子均表现为一组内部连接相对紧密的节点,但后者规模较小。圈子是重要的局部社区信息,利用这一特点有助于进行社区发现。然而,现有的大部分基于标签传播的社区发现算法并没有考虑圈子的信息。为此,提出一种基于局部强化的多标签传播(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.

关 键 词：社区发现 标签传播算法 局部强化 圈子 模度优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]