基于节点层级与标签传播增益的重叠社区发现  

Overlapping Community Discovery Based on Node Hierarchy and Label Propagation Gain

作　　者：陈羽中[1,2] 施松[1,2] 陈国龙[1,2] 於志勇[1,2] 

机构地区：[1]福州大学数学与计算机科学学院,福州350108 [2]福州大学福建省网络计算与智能信息处理重点实验室,福州350108

出　　处：《模式识别与人工智能》2015年第4期289-298,共10页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.61300104;61370210;61103175);福建省自然科学基金项目(No.2013J01232);福建省教育厅重点项目(No.JK2012003);福建省科技创新平台项目(No.2009J1007);福建省科技厅产学重大项目(No.2014H6014)资助

摘　　要：多标签传播算法具有接近线性的时间复杂度,但用于重叠社区发现时存在精度低、稳定性差的问题.文中基于重叠节点更可能出现在社区边缘的思想,提出基于节点层级与标签传播增益的重叠社区发现算法.该算法首先利用改进的基于节点中心度与社区分布约束的单标签传播方法发现非重叠社区,并在标签传播过程中利用局部信息同步计算节点中心度.然后根据节点中心度定义节点层级函数,标记节点在所属社区中的层级.最后基于节点间的标签传播增益,利用新的多标签更新规则,获得重叠社区结构.实验表明该算法能有效提高精度和稳定性.The time complexity of multi-label propagation algorithm （ MLPA） is nearly linear. However, when it is applied to overlapping community discovery, the accuracy and the stability of MLPA are poor. Inspired by the idea that overlapping nodes are more probable to appear in the boundary regions of different communities, an overlapping community discovery algorithm based on node hierarchy and label propagation gain is proposed in this paper. Firstly, the improved single label propagation with node centrality and community distribution constraints is utilized to unfold preliminary non-overlapping communities and centrality values of nodes are calculated by local information in the propagation process simultaneously. Furthermore, node hierarchy partition function is defined according to centrality values of nodes and employed to mark the hierarchy of each node in its respective community. Finally, based on the label propagation gain among nodes, a new multi-label updating rule is designed to obtain the final overlapping communities. Extensive experimental results on synthetic and real-world networks validate that the proposed algorithm effectively improves the accuracy and stability.

关 键 词：重叠社区发现 多标签传播 节点层级 传播增益 中心度 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]