一种面向社区发现的高鲁棒性标签传播算法  

Highly Robust Community Detection Algorithm Based on Label Propagation

作　　者：郑少强 赵中英 冯慧子[1] 李超 ZHENG Shao-qiang;ZHAO Zhong-ying;FENG Hui-zi;LI Chao(College of Computer Science and Engineering,Shandong University of Science and Technology,Qingdao 266590,China;Shenzhen Institutes of Advanced Technology,Chinese Academy of Sciences,Shenzhen 518055,China;Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China)

机构地区：[1]山东科技大学计算机科学与工程学院,山东青岛266590 [2]中国科学院深圳先进技术研究院,广东深圳518055 [3]桂林电子科技大学广西可信软件重点实验室,广西桂林541004

出　　处：《小型微型计算机系统》2018年第8期1809-1813,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61303167;61433012)资助;教育部人文社会科学研究项目(16YJCZH041;17YJCZH262)资助;山东科技大学人才引进启动基金项目(2015RCJJ069)资助;广东省自然科学基金项目(2015A030310364)资助;广西可信软件重点实验室开放课题(KX201535)资助

摘　　要：社区结构是真实网络普遍具有的拓扑特征,已经成为社交网络分析与挖掘领域的重要研究课题之一.研究社区结构对理解网络功能、揭示网络模式、分析网络行为等具有重要的研究意义.标签传播算法是速度较快的社区发现算法之一,但存在明显的缺陷,譬如划分社区不稳定、鲁棒性差等.为解决上述问题,本文提出一种有效改善标签传播的高鲁棒性算法(LPA_D_CC),算法首先根据节点度和聚集系数对网络中所有节点做影响力排序,根据影响力将网络中节点做初始划分,并对划分后的所有节点有条件的赋标签,最后根据标签传播过程对网络进行划分得到社区结构.在四种真实数据集上对算法进行实验与比较分析,结果表明,与原始LPA算法相比,该算法具有更高的准确性和稳定性,同时能够减少传播过程中的迭代次数,能快速收敛得到结果.Community structure is one of the most common and important characteristics of real world network. It has become a major research topic of social network analysis and mining. Community detection is of very important theoretical significance. It enables us to understand the functions of networks, reveal the implicit patterns, and analyze the network behaviors. Label propagation algorithm is one of the most efficient method to identify communities in social networks. However there axe still some obvious defects, such as in- stability of the .division for community, poor robustness and so on. In order to solve the above problem, we propose a high robust com- munity detection algorithm based on label propagation. Firstly, the nodes in the network are ranked according to the degree and the ag- gregation coefficient. According to the ranking of influence, the nodes in the network are initially divided, and then all the nodes are conditionally labeled. Finally, on the basis of process of label propagation, the final communities are formed. Experiments and compar- ative analysis are performed on four real data sets. Compared with the original LPA algorithm, the algorithm proposed in this paper has higher accuracy and stability. Meanwhile the algorithm can reduce the number of iterations during the propagation process, and can quickly converge to the results.

关 键 词：标签传播 社区发现 节点度数 聚集系数 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]