电子学报 ›› 2015, Vol. 43 ›› Issue (6): 1113-1118.DOI: 10.3969/j.issn.0372-2112.2015.06.012

• 学术论文 • 上一篇    下一篇

基于边标签传播的复杂网络社区识别方法

张健沛1, 邓琨1, 杨静1, 刘星妍2   

  1. 1. 哈尔滨工程大学计算机科学与技术学院, 黑龙江哈尔滨 150001;
    2. 黑龙江省电子信息产品监督检验院, 黑龙江哈尔滨 150090
  • 收稿日期:2014-03-31 修回日期:2014-05-21 出版日期:2015-06-25 发布日期:2015-06-25
  • 通讯作者: 邓琨
  • 作者简介:张健沛 男,1956年生于黑龙江哈尔滨.哈尔滨工程大学计算机科学与技术学院教授、博士生导师.主要研究方向为数据库与知识工程、数据挖掘、复杂网络分析等. E-mail:zhangjianpei@hrbeu.edu.cn
  • 基金资助:

    国家自然科学基金(No.61370083,No.61073043,No.61073041,No.61402126);高等学校博士学科点专项科研基金(No.20112304110011,No.20122304110012);哈尔滨市科技创新人才研究专项资金(优秀学科带头人)(No.2011RFXXG015)

Community Detection in Complex Networks Based on Link Label Propagation

ZHANG Jian-pei1, DENG Kun1, YANG Jing1, LIU Xing-yan2   

  1. 1. College of Computer Science and Technology, Harbin Engineering University, Harbin, Heilongjiang 150001, China;
    2. Heilongjiang Province Electronic and Information Products Supervision Inspection Institute, Harbin, Heilongjiang 150090, China
  • Received:2014-03-31 Revised:2014-05-21 Online:2015-06-25 Published:2015-06-25

摘要:

针对传统基于标签传播的复杂网络重叠社区识别算法难以准确识别重叠节点的缺陷,本文通过分析边与其邻居边的关系,提出用来评估边归属社区的归属密度函数及归属倾向性函数,并在此基础上设计一种基于边标签传播的重叠社区识别方法(OLLP).该方法首先以每条边连接2个节点中度高的节点标签作为该边的标签;然后通过分析边的归属密度与归属倾向性迭代更新边标签,最终标签相同的边属于同一社区.在基准网络与真实网络数据集上进行测试,并与多个具有代表性的算法进行比较,实验结果表明了OLLP算法的有效性和可行性.

关键词: 复杂网络, 重叠社区识别, 标签传播

Abstract:

Since traditional overlapping community detection methods in complex networks based on label propagation that could not detect overlapping nodes accurately, this paper presented link attribution density and link attribution orientation functions through analyzing the relationship between each link and its neighbor links to assess the attribution community of each link.On this basis, overlapping community detection method based on link label propagation (OLLP) was designed.Firstly, OLLP used the label of every link to the node label which possesses the higher degree when connected by the link, and then updated the label repeatedly through analyzing attribution density and attribution orientation of the link.Finally, identical label links were attributed to the same community.By testing on both synthetic and real-world networks, and comparing with multiple representative algorithms, the experimental results verify the validity and feasibility of OLLP.

Key words: complex networks, overlapping community detection, label propagation

中图分类号: