Int J Performability Eng ›› 2019, Vol. 15 ›› Issue (12): 3161-3170.doi: 10.23940/ijpe.19.12.p7.31613170

Previous Articles     Next Articles

A Complex Network Overlapping Community Detection Algorithm based on K-Cliques and Fitness Function

Jian Maa,b,* and Jianping Fana,b   

  1. aSchool of Computer and Information Technology, Beijing Jiaotong University, Beijing, 100044, China;
    bResearch Center for High-Speed Railway Network Management of Ministry of Education, Beijing Jiaotong University, Beijing, 100044, China
  • Submitted on ; Revised on ; Accepted on
  • Contact: * E-mail address: 13112083@bjtu.edu.cn
  • About author:Jian Ma is a PhD candidate at Beijing Jiaotong University. Her main research interests include data mining and complex network analysis.Jianping Fan is an Adjunct Professor and PhD supervisor at Beijing Jiaotong University. His main research interests include computing, cloud computing, and parallel and distributed computing.

Abstract: This paper presents an algorithm for detecting overlapping communities in complex networks. The algorithm draws on the idea of the clique as the core of the community, and proposes to treat the overlapping community as a collection of all k-cliques. The algorithm uses random nodes as the initial community, and each iteration selects the node with the maximum fitness value of the community neighbor. All k-cliques of the node are added to the community. During the process, nodes with negative fitness are removed. It then realizes the partition of network community structures and detects overlapping nodes. In many experiments of computer-generated networks and real-world networks, algorithms based on this idea have achieved good experimental results, which also illustrates the feasibility of this idea. Furthermore, the time efficiency and complexity of the algorithm is also acceptable. This algorithm also has better community discovery results.

Key words: complex network, community detection, overlapping community detection, fitness function, k-clique