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

An overlapping community identification algorithm based on label propagation

作　　者：吴春国[1,2,3] 李艳振 李瑛 高瑞[1,2] 时小虎 WU Chunguo;LI Yanzhen;LI Ying;GAO Rui;SHI Xiaohu(Symbol Computation and Knowledge Engineering of Ministry of Education,Jilin Universit;College of Computer Science and Technology,Jilin Universit;School of Computer,Zhuhai College of Jilin Universit)

机构地区：[1]吉林大学符号计算与知识工程教育部重点实验室,吉林长春130012 [2]吉林大学计算机科学与技术学院,吉林长春130012 [3]吉林大学珠海学院计算机学院,广东珠海519041

出　　处：《大连理工大学学报》2018年第4期414-421,共8页Journal of Dalian University of Technology

基　　金：国家自然科学基金资助项目(61373050);吉林省科技发展计划青年科研基金资助项目(20130101070JC);教育部在线教育研究中心在线教育研究基金资助项目(2017YB129)

摘　　要：重叠社区发现是复杂网络研究的重要课题.提出一种基于标签传播的重叠社区发现算法.首先利用标签传播算法得到初始无重叠社区划分结果,之后通过设计新的重叠节点识别算法确定重叠节点,最后再根据重叠节点的识别结果对社区进行合并从而得到最终的重叠社区划分结果.该算法克服了已有算法重叠节点占比过大的弊端.为验证算法的有效性,在LFR人工数据集、3个标准公开测试集以及真实的大豆基因共表达网络上进行实验,并与已有算法进行对比.实验结果表明,该算法性能明显优于对比算法,极大地改善了重叠节点比重过大问题.Overlapping community identification is an important problem in complex network study.An overlapping community indentification algorithm based on label propagation is proposed.Firstly,label propagation algorithm is used to achieve the initial non-overlapping community structure.And then,new overlapping node detection algorithm is proposed to identify overlapping nodes.At last,according to the identification results of overlapping nodes,the communities are merged to get the final result of overlapping community partition.The proposed algorithm overcomes the disadvantages of the oversize overlapped nodes in existing algorithms.To verify the effectiveness of the algorithm,the experiments and comparison with existing algorithms are carried out on LFR artificial datasets,three benchmark open test datasets,and real soybean gene co-expression networks.The experimental result shows that this algorithm is clear superior to the existing algorithms,overwhelmingly improves the problem of great proportion of overlapping nodes.

关 键 词：重叠社区 社区发现 标签传播 复杂网络 基因表达数据 

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