Journal of South China University of Technology (Natural Science Edition) ›› 2016, Vol. 44 ›› Issue (9): 24-31.doi: 10.3969/j.issn.1000-565X.2016.09.004

• Computer Science & Technology • Previous Articles     Next Articles

An Overlapping Community Detection Algorithm Based on Addtion of a Clique at Each Step

ZHANG Xing-yi ZHENG Wen WANG Cong-tao DING Zhuan-lian SU Yan-sen   

  1. School of Computer Science and Technology//Institute of Bio-inspired Intelligence and Knowledge Mining,Anhui University,Hefei 230601,Anhui,China
  • Received:2015-11-03 Revised:2016-03-29 Online:2016-09-25 Published:2016-08-21
  • Contact: 苏延森( 1985-) ,女,博士,讲师,主要从事复杂网络分析研究. E-mail:suyansen1985@163.com
  • About author:张兴义( 1982-) ,男,博士,教授,博士生导师,主要从事非传统计算模型与算法、多目标优化及复杂网络分析研究E-mail: xyzhanghust@ gmail. com
  • Supported by:
    Supported by the National Natural Science Foundation of China( 61272152, 61502004, 61502001)

Abstract: The local expansion-based overlapping community detection algorithms start from a single node or a clique,and then repeatedly add a new node to the obtained community,thus obtaining the final community.However,the existing local expansion-based overlapping community detection algorithms always add one node at each step,so the local information of the added nodes has not been fully considered,thus reducing the accuracy of the algorithms.In order to solve this problem,an overlapping community detection algorithm is proposed,which adds a clique at each step.This algorithm starts from a clique,and expands the clique by repeatedly adding a clique of the largest fitness value in the neighborhood.In this way,the links between the added node and the existing community and the links between the added nodes are both taken into account.An empirical evaluation on the synthetic and real datasets demonstrates that the proposed algorithm can detect the overlapping communities in complex networks more accurately than the existing algorithms.

Key words: complex networks, community detection, overlapping community, local expansion

CLC Number: