Community detection algorithm based on maximal clique of network nodes

Abstract

Abstract: Community structure detection is instrumental in revealing the structure-function properties of complex networks. The existing community detection algorithms suffer from resolution limitations, node uncertainty, and the need for prior parameters in their research process. A community detection algorithm based on the maximal clique of network nodes (BMC) is proposed to solve these problems. The BMC algorithm sets the maximal clique of nodes in the network as the initial node cluster, and merges the node clusters by hierarchical clustering based on the proposed local similarity of the maximal clique and the local clique relationship, so as to mine the community structure in the network. Aiming at tackling the issue of node uncertainty in the mining process of community structure, the module membership degree is proposed through the modularity matrix to optimize the single neighbor nodes and overlapping nodes in the network. In order to verify the accuracy of the BMC algorithm for network community structure mining, experiments are conducted on five real network datasets with five algorithms for comparison. The experimental results obtained by the three measures show that the BMC algorithm accurately detects the community structure in the network.

Key words: complex network, community detection, maximal clique, modularity matrix

CLC Number:

TP393

LU Peng-li, YANG Ya-lei. Community detection algorithm based on maximal clique of network nodes[J]. Journal of Lanzhou University of Technology, 2024, 50(4): 86-93.

References

[1] CHUNAEV P.Community detection in node-attributed social networks:a survey [J].Computer Science Review,2020,37:100286.
[2] ÁLVAREZN G, ADENSO-DÍAZ B, CALZADA-INFANTEL. Maritime traffic as a complex network:a systematic review [J].Networks and Spatial Economics,2021,21(2):387-417.
[3] MUZIO G,O’BRAY L,BORGWARDT K.Biological network analysis with deep learning [J].Briefings in Bioinformatics,2021,22(2):1515-1530.
[4] ROKACH L,MAIMON O.Data mining and knowledge discovery handbook:clustering methods [M].Berlin:Springer,2005:321-352.
[5] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks [J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[6] NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks [J].Physical Review E,2004,69(2):026113.
[7] 陈国强,王宇平.基于极值优化模块密度的复杂网络社区检测 [J].华中科技大学学报:自然科学版,2011,39(4):82-85.
[8] TRAAG V A,WALTMAN L,VAN ECK N J.From Louvain to Leiden:guaranteeing well-connected communities [J].Scientific Reports,2019,9(1):1-12.
[9] REN S,ZHANG S,WU T.An improved spectral clustering community detection algorithm based on probability matrix [J].Discrete Dynamics in Nature and Society,2020(8):1-6.
[10] FORTUNATO S,BARTHELEMY M.Resolution limit in community detection [J].Proceedings of the National Academy of Sciences,2007,104(1):36-41.
[11] CONTE A,TOMITA E.On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms [J].Theoretical Computer Science,2022,899:1-24.
[12] BAUDIN A,DANISCH M,KIRGIZOV S,et al.Clique percolation method:memory efficient almost exact communities [C]//International Conference on Advanced Data Mining and Applications.Cham:Springer,2022:113-127.
[13] KIRUTHIKA R,VIJAYA M S.Community detection using Girvan-Newman and Kernighan-Lin bipartition algorithms [C]//Data Intelligence and Cognitive Informatics.Singapore:Springer,2022:217-231.
[14] CHENG J,LI L,LENG M,et al.A divisive spectral method for network community detection [J].Journal of Statistical Mechanics:Theory and Experiment,2016(3):033403.
[15] WU Q,HAO J K.A review on algorithms for maximum clique problems [J].European Journal of Operational Research,2015,242(3):693-709.
[16] GANJI M,SEIFI A,ALIZADEH H,et al.Generalized modularity for community detection [C] //Joint European Conference on Machine Learning and Knowledge Discovery in Databases.Cham:Springer,2015:655-670.
[17] VERMA V,AGGARWAL R K.A comparative analysis of similarity measures akin to the Jaccard index in collaborative recommendations:empirical and theoretical perspective [J].Social Network Analysis and Mining,2020,10(1):1-16.
[18] ZACHARY W W.An information flow model for conflict and fission in small groups [J].Journal of Anthropological Research,1977,33(4):452-473.
[19] LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations [J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[20] LIU Z,MA Y.A divide and agglomerate algorithm for community detection in social networks [J].Information Sciences,2019,482:321-333.
[21] FORTUNATO S.Community detection in graphs [J].Physics Reports,2010,486(3/4/5):75-174.
[22] DANON L,DIAZ-GUILERA A,DUCH J,et al.Comparing community structure identification [J].Journal of Statistical Mechanics:Theory and Experiment,2005,2005(9):P09008.
[23] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks [J].Physical Review E,2004,70(6):066111.
[24] GARZA S E,SCHAEFFER S E.Community detection with the label propagation algorithm:a survey [J].Physica A:Statistical Mechanics and Its Applications,2019,534:122058.
[25] PARÉS F,GASULLA D G,VILALTA A,et al.Fluid communities:a competitive,scalable and diverse community detection algorithm [C] //International Conference on Complex Networks and Their Applications.Cham:Springer,2017:229-240.