复杂网络社团发现综述

doi:10.11896/jsjkx.230100130

摘要/Abstract

摘要： 现实世界中许多复杂系统均被建模成复杂网络,如社交网络、科学家协作网络等。复杂网络的研究吸引了不同领域的诸多研究者的广泛关注。挖掘社团结构,即将网络划分到具有类内链接稠密、类间链接稀疏的不同社团,是复杂网络研究的问题之一。研究复杂网络社团检测对分析复杂网络中潜在结构、规律以及社团的形成有着至关重要的意义,并且有着广泛的应用前景。鉴于复杂网络中同时包含了网络拓扑与节点内容,结合节点内容的社团检测研究将成为该研究领域的新趋势之一。文中介绍了复杂网络社团检测的研究背景和研究意义;并从基于网络拓扑、基于节点内容和基于网络拓扑和节点内容融合3个方面,较为全面地对社团检测研究现状进行了梳理以及对其面临的问题进行了分析。从3类社团检测方法中选择了10种具有代表性的算法,对它们进行性能对比和时间复杂度分析,以期望描绘关于社团发现新趋势的清晰轮廓。

关键词: 复杂网络, 社交网络, 社团发现, 节点内容, 信息融合

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

中图分类号:

TP182

曹金鑫, 许伟忠, 金弟, 丁卫平. 复杂网络社团发现综述[J]. 计算机科学, 2023, 50(11A): 230100130-11. https://doi.org/10.11896/jsjkx.230100130

CAO Jinxin, XU Weizhong, JIN Di, DING Weiping. Survey of Community Discovery in Complex Networks[J]. Computer Science, 2023, 50(11A): 230100130-11. https://doi.org/10.11896/jsjkx.230100130

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed