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

doi:10.23940/ijpe.19.12.p7.31613170

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 Ma^a,b,* and Jianping Fan^a,b

^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

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

Jian Ma and Jianping Fan. A Complex Network Overlapping Community Detection Algorithm based on K-Cliques and Fitness Function [J]. Int J Performability Eng, 2019, 15(12): 3161-3170.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

[1] G. Palla, I. Derényi, I. Farkas,T. Vicesk, “Uncovering the Overlapping Community Structures of Complex Networks in Nature and Society,” Nature, Vol. 435, No. 7043, pp. 814-818, June 2005
[2] A. Lancichinetti, S. Fortunato,J. Kertész, “Detecting the Overlapping and Hierarchical Community Structure in Complex Network,” New Journal of Physics, Vol. 11, No. 3, pp. 033015, March 2009
[3] E. Gregori, L. Lenzini,S. Mainardi, “Parallel k-Clique Community Detection on Large-Scale Networks,” IEEE Transaction on Parallel and Distributed System, Vol. 24, No. 8, pp. 1651-1660, August 2013
[4] J. Yang, J. McAuley,J. Leskovec, “Community Detection in Networks with Node Attributes,” inProceedings of the 13th IEEE International Conference on Data Mining, pp. 1151-1156, Dallas, USA, December 2013
[5] F. Hao, S. S. Yau, G. Min,L. T. Yang, “Detecting k-Balanced Trusted Cliques in Signed Social Networks,” IEEE Internet Computing, Vol. 18, No. 2, pp. 24-31, March 2014
[6] X. Wen, W. Chen, Y. Lin, T. Gu, H. Zhang, Y. Li, et al., “A Maximal Clique based Multiobjective Evolutionary Algorithm for Overlapping Community Detection,” IEEE Transactions on Evolutionary Computation, Vol. 21, No. 3, pp. 363-377, September 2016
[7] D. Jin, B. Gabrys,J. Dang, “Combined Node and Link Partitions Method for Finding Overlapping Communities in Complex Networks,” Scientific Reports, Vol. 5, pp. 8600, February 2015
[8] C. Lee, F. Reid, A. McDaid,N. Hurley, “Detecting Highly Overlapping Community Structure by Greedy Clique Expansion,”(https://arxiv.org/abs/1002.1827)
[9] J. Xie, B. K. Szymanski,X. Liu, “SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process,” inProceedings of the 11th International Conference on Data Mining Workshops, pp. 344-349, Vancouver, CA, November 2011
[10] Y. Y. Ahn, J. P. Bagrow,S. Lehmann, “Link Communities Reveal Multi-Scale Complexity in Networks,” Nature, Vol. 466, No. 7307, pp. 761-764, October 2010
[11] T. Zhang and B. Wu, “A Method for Local Community Detection by Finding Core Nodes,” inProceedings of 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 1171-1176, Istanbul, Turkey, August 2012
[12] X. Zhang, W. Zheng, C. Wang, Z. Ding,Y. Su, “An Overlapping Community Detection Algorithm based on Addtion of a Clique at Each Step,” Journal of South China University of Technology (Natural Science Edition), Vol. 44, No. 9, pp. 24-31, September 2016
[13] Z. Huang, Z. Wang,Z. Zhang, “Detecting Overlapping and Hierarchical Communities in Complex Network based on Maximal Cliques,” inProceedings of the 6th Chinese National Conference on Social Media Processing, pp. 184-191, Guangzhou, CHN, November 2015
[14] P. Wu and L. Pan, “Detecting Highly Overlapping Community Structure based on Maximal Clique Networks,” inProceeding of 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 196-199, Beijing, CHN, August 2014
[15] Y. Cui, X. Wang,J. Li, “Detecting Overlapping Communities in Networks using the Maximal Sub-graph and the Clustering Coefficient,” Physica A: Statistical Mechanics and its Applications, Vol. 405, pp. 85-91, March 2014
[16] V. Nicosia, G. Mangioni, V. Carchiolo,M. Malgeri, “Extending the Definition of Modularity to Directed Graphs with Overlapping Communities,” Journal of Statistical Mechanics: Theory and Experiment, Vol. 2009, No. 3, pp. 3166-3168, March 2009
[17] H. Shen, X. Chen, K. Cai,M. Hu, “Detect Overlapping and Hierarchical Community Structure in Networks,” Physica A: Statistical Mechanics and its Applications, Vol. 388, No. 8, pp. 1706-1712, April 2009
[18] W. W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups,” Journal of Anthropological Research, Vol. 33, No. 4, pp. 452-473, 1977
[19] D. Lusseau, “The Emergent Properties of a Dolphin Social Network,” Proceedings of the Royal Society B: Biological Sciences, Vol. 270, No.Supl.2, pp. 186-188, 2003

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 9

Recommended 0

[1]	Ashima Arya and Sanjay Kumar Malik. An Improved Firefly-Based Feature Selection Method for Software Fault Identification and Classification [J]. Int J Performability Eng, 2023, 19(11): 744-752.
[2]	Ying Huang, Linglin Gong, Jianguo Zhang, Haiwei Fan, and Yizhuo Zhang. Review of Key Elements Identification and Robustness Analysis of Power Grid based on Complex Network Theory [J]. Int J Performability Eng, 2022, 18(5): 359-368.
[3]	Dan Lu and Shunkun Yang*. A Survey of the Analysis of Complex Systems based on Complex Network Theory and Deep Learning [J]. Int J Performability Eng, 2022, 18(4): 241-250.
[4]	Hailu Yang, Ying Zhang, Jin Zhang, Deyun Chen, and Guanglu Sun. Event-based Community Detection in Micro-Blog Networks [J]. Int J Performability Eng, 2021, 17(1): 60-73.
[5]	Jun Lu and Yuanzhong Zhang. Optimization and Parallelization of MRF Community Detection Algorithm for a Specific Network [J]. Int J Performability Eng, 2019, 15(8): 2153-2164.
[6]	Yuling Tian. Community Structure Division based on Immune Algorithm [J]. Int J Performability Eng, 2019, 15(4): 1103-1111.
[7]	Yan Liu, Chunliang Chen, Kangzhu Chen, Weilong Chen, and Lijun Zhang. Evaluationof Equipment Node Importance based on Bi-Layer Coupling Complex Networks [J]. Int J Performability Eng, 2019, 15(2): 374-386.
[8]	Hui Xu and Yang Li. Robustness Analysis of Urban Rail Transit Network [J]. Int J Performability Eng, 2019, 15(10): 2762-2771.
[9]	Zhaotong Wang, Yupeng Li, Mengze Li, and Xiaoyu Zhong. Reliability Modeling of Complex Machinery and Electronic Products based on the Identification of Vital Components [J]. Int J Performability Eng, 2019, 15(1): 156-166.