Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (11A): 230100130-11.doi: 10.11896/jsjkx.230100130

• Big Data & Data Science • Previous Articles     Next Articles

Survey of Community Discovery in Complex Networks

CAO Jinxin1, XU Weizhong1, JIN Di2, DING Weiping1   

  1. 1 School of Information Science and Technology,Nantong University,Nantong,Jiangsu 226019,China
    2 College of Intelligence and Computing,Tianjin University,Tianjin 300350,China
  • Published:2023-11-09
  • About author:CAO Jinxin,born in 1987,Ph.D,lectu-rer,is a member of China Computer Fe-deration.His mainresearch interests include data mining,machine learning,community detection.
    JIN Di,born in 1981,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include data mining,complex network analysis,machine learning.
  • Supported by:
    National Natural Science Foundation of China(61876128,61976120),Natural Science Foundation of Jiangsu Province(BK20191445) and Natural Science Foundation of the Higher Education Institutions of Jiangsu Province(21KJB520018).

PDF (PC)

610

Abstract: Many complex systems in the real world can be modeled as complex networks,such as social networks and scientist collaboration networks.The study of complex networks has attracted the attention of many researchers in different fields.The mining of community structure,division of a network into different communities of nodes with dense intra-community links and sparse inter-community links,is one of the main problems in the study of complex network.Research on community detection in complex networks is of vital importance to the analysis of the potential structure,laws,and the formation of communities in complex networks,and has a wide range of application prospects.Since complex networks contain both network topology and node content,the study of community detection combining node content will become one of the new trends in this field.This paper introduces the research background and significance of community detection in complex networks.And from three aspects based on network topology,node content,and network topology and node content integration,we comprehensively sort out the research status of community detection and analyze the problems it faces.We select 10 representative algorithms from the mentioned three types of community detection methods,and compare their performance of identifying communities and analyze time complexity of these algorithms,hoping to draw a clear outline of the new trend of community discovery.

Key words: Complex networks, Social networks, Community discovery, Node content, Information fusion

CLC Number: 

  • TP182
[1]WANG X F,LI X,CHEN G R.Complex network theory and its applications[M]//Beijing:Tsinghua University Press,2006.
[2]EULER L.The seven bridges of Königsberg[J].The world of mathematics,1956,1:573-580.
[3]ERDO″S P,RÉNYI A.On the strength of connectedness of a random graph[J].Acta Mathematica Hungarica,1961,12(1/2):261-267.
[4]WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):440.
[5]BARABÁSI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.
[6]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.
[7]HILL R A,DUNBAR R I M.Social network size in humans[J].Human Nature,2003,14(1):53-72.
[8]FORTUNATO S.Community detection in graphs[J].PhysicsReports,2010,486(3/4/5):75-174.
[9]JIN D,YOU X X,LIU Y S,et al.Stuctural Feature Enhanced Markov Random Field for Community Detection in Large-Scale networks[J].Chinese Journal of Computer.2019,40(12):2822-2835.
[10]ZHANG L,LIU Q,YANG S S,et al.A Dual Representation-Based Multi-Objective Evolutionary Algorithm for Overlapping Community Detection[J].Acta Electronica Sinica,2021,49(11):2101-2107.
[11]DOURISBOURE Y,GERACI F,PELLEGRINI M.Extractionand classification of dense communities in the web[C]//Proceedings of the 16th International Conf.on World Wide Web.ACM,2007:461-470.
[12]CHEN J C,YUAN B.Detecting functional modules in the yeast protein-protein interaction network[J].Bioinformatics,2006,22(18):2283-2290.
[13]RIVES A W,GALITSKI T.Modular organization of cellularnetworks[J].Proceedings of the National Academy of Sciences,2003,100(3):1128-1133.
[14]SPIRIN V,MIRNY L A.Protein complexes and functional mo-dules in molecular networks[J].Proceedings of the National Academy of Sciences,2003,100(21):12123-12128.
[15]MACQUEEN J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability.1967:281-297.
[16]GLARIA F,HERNÁNDEZ C,LADRA S,et al.Compact structure for sparse undirected graphs based on a clique graph partition[J].Information Sciences,2021,544:485-499.
[17]DONETTI L,MUNOZ M A.Detecting network communities:a new systematic and efficient algorithm[J].Journal of Statistical Mechanics:Theory and Experiment,2004,2004(10):P10012.
[18]WU C R,PENG Q L,LEE J,et al.Effective hierarchical clustering based on structural similarities in nearest neighbor graphs[J].Knowledge-Based Systems,2021,228:107295.
[19]NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical review E,2004,69(2):026113.
[20]ROSVALL M,BERGSTROM C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences,2008,105(4):1118-1123.
[21]FAYSAL M A M,ARIFUZZAMAN S.Distributed community detection in large networks using an information-theoretic approach[C]//Proceedings of 2019 IEEE International Conference on Big Data.IEEE,2019:4773-4782.
[22]HOLLAND P W,LASKEY K B,LEINHARDT S.Stochasticblockmodels:First steps[J].Social Networks,1983,5(2):109-137.
[23]KARRER B,NEWMAN M E J.Stochastic blockmodels andcommunity structure in networks[J].Physical Review E,2011,83(1):016107.
[24]JIN D,CHEN Z,HE D X,et al.Modeling with node degree preservation can accurately find communities[C]//Proceedings of the 29th AAAI Conf.on Artificial Intelligence.2015.
[25]CUI P,WANG X,PEI J,et al.A survey on network embedding[J].IEEE Transactions on Knowledge and Data Engineering,2018,31(5):833-852.
[26]LIU F Z,XUE S,WU J,et al.Deep learning for community detection:progress,challenges and opportunities[J].arXiv:2005.08225,2020.
[27]SU X,XUE S,LIU F Z,et al.A comprehensive survey on community detection with deep learning[J].IEEE Transactions on Neural Networks and Learning Systems,2021,33:6737-6748.
[28]NEWMAN M E J,CLAUSET A.Structure and inference in annotated networks[J].Nature Communications,2016,7(1):1-11.
[29]JIN D,YU Z Z,JIAO P F,et al.A survey of community detection approaches:From statistical modeling to deep learning[J].IEEE Transactions on Knowledge and Data Engineering,2023,35(2):1147-1170.
[30]SHI J B,JITENDRA M.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.
[31]MAJI S,VISHNOI N K,MALIK J.Biased normalized cuts[C]//Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition.2011:2057-2064.
[32]CHEW S E,CAHILL N D.Semi-supervised normalized cuts for image segmentation[C]//Proceedings of the IEEE International Conference on Computer Vision.2015:1716-1723.
[33]SUN Z J,SUN Y N,CHANG X F,et al.Community detection based on the Matthew effect[J].Knowledge-Based Systems,2020,205:106256.
[34]SUN P G.Weighting links based on edge centrality for community detection[J].Physica A:Statistical Mechanics and Its Applications,2014,394:346-357.
[35]LI T X,LEI L H,BHATTACHARYYA S,et al.Hierarchical community detection by recursive partitioning[J].Journal of the American Statistical Association,2022,117(538):951-968.
[36]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,2008(10):P10008.
[37]QIAO S J,HAN N,GAO Y J,et al.A fast parallel community discovery model on complex networks through approximate optimization[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(9):1638-1651.
[38]KIRKPATRICK S,GELATT C D,VECCHI M P.Optimization by simulated annealing[J].Science,1983,220(4598):671-680.
[39]AIROLDI E M,BLEI D M,FIENBERG S E,et al.Mixed membership stochastic blockmodels[J].Journal of Machine Learning Research,2008,9:1981-2014.
[40]HE C B,ZHANG Q,TANG Y,et al.Community detectionmethod based on robust semi-supervised nonnegative matrix factorization[J].Physica A:Statistical Mechanics and its Applications,2019,523:279-291.
[41]LUO X,LIU Z G,JIN L,et al.Symmetric nonnegative matrix factorization-based community detection models and their convergence analysis[J].IEEE Transactions on Neural Networks and Learning Systems,2021,33(3):1203-1215.
[42]GROVER A,LESKOVEC J.node2vec:Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2016:855-864.
[43]PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:Online lear-ning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conf.on Knowledge Discovery and Data Mining.2014:701-710.
[44]LONG Q Q,WANG Y M,DU L,et al.Hierarchical community structure preserving network embedding:A subspace approach[C]//Proceedings of the 28th ACM international conference on information and knowledge management.2019:409-418.
[45]WANG D X,CUI P,ZHU W W.Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conf.on Knowledge Discovery and Data Mining.2016:1225-1234.
[46]XU R B,CHE Y,WANG X M,et al.Stacked autoencoder-based community detection method via an ensemble clustering framework[J].Information sciences,2020,526:151-165.
[47]CAI B,WANG Y P,ZENG L N,et al.Edge classification based on Convolutional Neural Networks for community detection in complex network[J].Physica A:Statistical Mechanics and Its Applications,2020,556:124826.
[48]JIA Y T,ZHANG Q Q,ZHANG W N,et al.Communitygan:Community detection with generative adversarial nets[C]//Proceedings of the World Wide Web Conference.2019:784-794.
[49]CHEN J Y,GONG Z G,MO J Q,et al.Self-training enhanced:Network embedding and overlapping community detection with adversarial learning[J].IEEE Transactions on Neural Networks and Learning Systems,2021,33:6737-6748.
[50]RODRIGUEZ A,LAIO A.Clustering by fst search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[51]CHEN Y W,HU X L,FAN W T,et al.Fast density peak clustering for large scale data based on kNN[J].Knowledge-Based Systems,2020,187:104824.
[52]YU H,CHEN L Y,YAO J T.A three-way density peak clustering method based on evidence theory[J].Knowledge-Based Systems,2021,211:106532.
[53]XU X,DING S F,WANG Y R,et al.A fast density peaks clustering algorithm with sparse search[J].Information Sciences,2021,554:61-83.
[54]HOFMANN T.Probabilistic latent semantic indexing[C]//Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,1999:50-57.
[55]BLEI D M,NG A Y,JORDAN M I.Latent dirichlet allocation[J].Journal of Machine Learning Research,2003,3:993-1022.
[56]STREICH A P,FRANK M,BASIN D,et al.Multi-assignment clustering for boolean data[C]//Proceedings of the 26th Annual International Conference on Machine Learning.2009:969-976.
[57]MIKOLOV T,SUTSKEVER I,CHEN K,et al.Distributed representations of words and phrases and their compositionality[C]//Proceedings of Advances in Neural Information Proces-sing Systems.2013:3111-3119.
[58]YANG Y,WANG H G,ZHU J Q,et al.Dataless short textclassification based on biterm topic model and word embeddings[C]//Proceedings of the 29th International Conference on International Joint Conferences on Artificial Intelligence.2021:3969-3975.
[59]FARD M M,THONET T,GAUSSIER E.Deep k-means:Join-tly clustering with k-means and learning representations[J].Pattern Recognition Letters,2020,138:185-192.
[60]RUAN Y,FUHRY D,PARTHASARATHY S.Efficient community detection in large networks using content and links[C]//Proceedings of the 22nd International Conference on World Wide Web.2013:1089-1098.
[61]BU Z,LI H J,CAO J,et al.Dynamic cluster formation game for attributed graph clustering[J].IEEE transactions on cyberne-tics,2017,49(1):328-341.
[62]YANG J,MCAULEY J,LESKOVEC J.Community detection in networks with node attributes[C]//Proceedings of IEEE 13th International Conf.on Data Mining.IEEE,2013:1151-1156.
[63]BALASUBRAMANYAN R,COHEN W W.Block-LDA:Jointly modeling entity-annotated text and entity-entity links[C]//Proceedings of the 2011 SIAM International Conf.on Data Mining.Society for Industrial and Applied Mathematics.2011:450-461.
[64]WANG X,JIN D,CAO X C,et al.Semantic community identification in large attribute networks[C]//Proceedings of the AAAI Conf.on Artificial Intelligence.2016.
[65]HU L,CHAN K,YUAN X H,et al.A variational Bayesianframework for cluster analysis in a complex network[J].IEEE Transactions on Knowledge and Data Engineering,2019,32(11):2115-2128.
[66]JIN D,WANG K Z,ZHANG G,et al.Detecting communities with multiplex semantics by distinguishing background,general,and specialized topics[J].IEEE Transactions on Knowledge and Data Engineering,2019,32(11):2144-2158.
[67]YANG C,LIU Z Y,ZHAO D L,et al.Network representation learning with rich text information[C]//Proceedings of the 24th International Joint Conference on Artificial Intelligence.2015.
[68]NATARAJAN N,DHILLON I S.Inductive matrix completion for predicting gene-disease associations[J].Bioinformatics,2014,30(12):i60-i68.
[69]KANG Z,LIU Z Y,PAN S R,et al.Fine-grained Attributed Graph Clustering[C]//Proceedings of the 2022 SIAM International Conference on Data Mining.Society for Industrial and Applied Mathematics.2022:370-378.
[70]SUN X F,GUO J,DING X,et al.A general framework for content-enhanced network representation learning[J].arXiv:1610.02906,2016.
[71]FAN S H,WANG X,SHI C,et al.One2multi graph autoencoder for multi-view graph clustering[C]//Proceedings of The Web Conference 2020.2020:3070-3076.
[72]YANG L,WANG Y Y,GU J H,et al.JANE:Jointly Adversa-rial Network Embedding[C]//Proceedings of IJCAI.2020:1381-1387.
[73]CUI G Q,ZHOU J,YANG C,et al.Adaptive graph encoder for attributed graph embedding[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2020:976-985.
[74]ZHENG Y P,ZHANG X F,CHEN S Y,et al.When Convolutional Network Meets Temporal Heterogeneous Graphs:An Effective Community Detection Method[J].IEEE Transactions on Knowledge and Data Engineering,2023,35(2):2173-2178.
[75]FETTAL C,LABIOD L,NADIF M.Efficient Graph Convolut-ion for Joint Node Representation Learning and Clustering[C]//Proceedings of the 15th ACM International Conference on Web Search and Data Mining.2022:289-297.
[76]WANG C,PAN S R,HU R Q,et al.Attributed graph clustering:A deep attentional embedding approach[J].arXiv:1906.06532,2019.
[77]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical review E,2008,78(4):046110.
[78]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[1] CHENG Haiyang, ZHANG Jianxin, SUN Qisen, ZHANG Qiang, WEI Xiaopeng. Deep Cross-modal Information Fusion Network for Stock Trend Prediction [J]. Computer Science, 2023, 50(5): 128-136.
[2] DUAN Shunran, YIN Meijuan, LIU Fenlin, JIAO Longlong, YU Lanlan. Nodes’ Ranking Model Based on Influence Prediction [J]. Computer Science, 2023, 50(3): 155-163.
[3] ZHANG Weiliang, CHEN Xiuhong. SSD Object Detection Algorithm with Cross-layer Fusion and Receptive Field Amplification [J]. Computer Science, 2023, 50(3): 231-237.
[4] CHEN Zhen, PU Yuanyuan, ZHAO Zhengpeng, XU Dan, QIAN Wenhua. Multimodal Sentiment Analysis Based on Adaptive Gated Information Fusion [J]. Computer Science, 2023, 50(3): 298-306.
[5] CHEN Duanbing, YANG Zhijie, ZENG Zhuo, FU Yan, ZHOU Junlin, ZHAO Junyan. Node Ranking Algorithm Based on Subgraph Features [J]. Computer Science, 2023, 50(11A): 230100122-7.
[6] LIU Hualing, ZHANG Guoxiang, WANG Liuyue, LIANG Huabi. Study on Credit Anti-fraud Based on Heterogeneous Information Network [J]. Computer Science, 2023, 50(11A): 221100173-9.
[7] ZHAO Xingwang, XUE Jinfang. Community Discovery Algorithm for Attributed Networks Based on Bipartite Graph Representation [J]. Computer Science, 2023, 50(11): 107-113.
[8] YAN Jia-dan, JIA Cai-yan. Text Classification Method Based on Information Fusion of Dual-graph Neural Network [J]. Computer Science, 2022, 49(8): 230-236.
[9] ZHANG Yuan, KANG Le, GONG Zhao-hui, ZHANG Zhi-hong. Related Transaction Behavior Detection in Futures Market Based on Bi-LSTM [J]. Computer Science, 2022, 49(7): 31-39.
[10] HE Yi-chen, MAO Yi-jun, XIE Xian-fen, GU Wan-rong. Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation [J]. Computer Science, 2022, 49(6A): 272-279.
[11] ZHOU Chu-lin, CHEN Jing-dong, HUANG Fan. WiFi-PDR Fusion Indoor Positioning Technology Based on Unscented Particle Filter [J]. Computer Science, 2022, 49(6A): 606-611.
[12] WEI Peng, MA Yu-liang, YUAN Ye, WU An-biao. Study on Temporal Influence Maximization Driven by User Behavior [J]. Computer Science, 2022, 49(6): 119-126.
[13] TANG Chun-yang, XIAO Yu-zhi, ZHAO Hai-xing, YE Zhong-lin, ZHANG Na. EWCC Community Discovery Algorithm for Two-Layer Network [J]. Computer Science, 2022, 49(4): 49-55.
[14] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[15] SHAO Yu, CHEN Ling, LIU Wei. Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model [J]. Computer Science, 2022, 49(2): 204-215.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.