›› 2015, Vol. 24 ›› Issue (1): 18703-018703.doi: 10.1088/1674-1056/24/1/018703

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇    下一篇

Detecting overlapping communities in networks via dominant label propagation

孙鹤立a b, 黄健斌b c, 田勇强c, 宋擒豹a, 刘怀亮d   

  1. a Department of Computer Science and Technology, Xi'an Jiaotong University, Xi'an 710049, China;
    b State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China;
    c School of Software, Xidian University, Xi'an 710071, China;
    d School of Economics and Management, Xidian University, Xi'an 710071, China
  • 收稿日期:2014-07-14 修回日期:2014-08-15 出版日期:2015-01-05 发布日期:2015-01-05
  • 基金资助:
    Project supported by the National Natural Science Foundation of China (Grant Nos. 61173093 and 61202182), the Postdoctoral Science Foundation of China (Grant No. 2012 M521776), the Fundamental Research Funds for the Central Universities of China, the Postdoctoral Science Foundation of Shannxi Province, China, and the Natural Science Basic Research Plan of Shaanxi Province, China (Grant Nos. 2013JM8019 and 2014JQ8359).

Detecting overlapping communities in networks via dominant label propagation

Sun He-Li (孙鹤立)a b, Huang Jian-Bin (黄健斌)b c, Tian Yong-Qiang (田勇强)c, Song Qin-Bao (宋擒豹)a, Liu Huai-Liang (刘怀亮)d   

  1. a Department of Computer Science and Technology, Xi'an Jiaotong University, Xi'an 710049, China;
    b State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China;
    c School of Software, Xidian University, Xi'an 710071, China;
    d School of Economics and Management, Xidian University, Xi'an 710071, China
  • Received:2014-07-14 Revised:2014-08-15 Online:2015-01-05 Published:2015-01-05
  • Contact: Sun He-Li E-mail:hlsun@mail.xjtu.edu.cn
  • Supported by:
    Project supported by the National Natural Science Foundation of China (Grant Nos. 61173093 and 61202182), the Postdoctoral Science Foundation of China (Grant No. 2012 M521776), the Fundamental Research Funds for the Central Universities of China, the Postdoctoral Science Foundation of Shannxi Province, China, and the Natural Science Basic Research Plan of Shaanxi Province, China (Grant Nos. 2013JM8019 and 2014JQ8359).

RichHTML

1

PDF (PC)

683

赞

摘要： Community detection is an important methodology for understanding the intrinsic structure and function of a real-world network. In this paper, we propose an effective and efficient algorithm, called Dominant Label Propagation Algorithm (Abbreviated as DLPA), to detect communities in complex networks. The algorithm simulates a special voting process to detect overlapping and non-overlapping community structure in complex networks simultaneously. Our algorithm is very efficient, since its computational complexity is almost linear to the number of edges in the network. Experimental results on both real-world and synthetic networks show that our algorithm also possesses high accuracies on detecting community structure in networks.

关键词: overlapping community detection, dominant label propagation, complex network

Abstract: Community detection is an important methodology for understanding the intrinsic structure and function of a real-world network. In this paper, we propose an effective and efficient algorithm, called Dominant Label Propagation Algorithm (Abbreviated as DLPA), to detect communities in complex networks. The algorithm simulates a special voting process to detect overlapping and non-overlapping community structure in complex networks simultaneously. Our algorithm is very efficient, since its computational complexity is almost linear to the number of edges in the network. Experimental results on both real-world and synthetic networks show that our algorithm also possesses high accuracies on detecting community structure in networks.

Key words: overlapping community detection, dominant label propagation, complex network

中图分类号:  (Structures and organization in complex systems)

  • 89.75.Fb
89.75.Hc (Networks and genealogical trees)