Dynamic Community Detection: A Survey

doi:10.3778/j.issn.1673-9418.2008023

Abstract

Abstract:

With the increasing diversity of social media, the demand for real-time analysis of social networks continues to increase, and research on dynamic community detection has received extensive attention. Existing community detection reviews mostly focus on static community detection and the discussion of related methods, so network evolution analysis cannot be carried out. Besides, the entity data in the community are cross-substitutional and sequential. Therefore, the research status of dynamic community detection is studied, reviewed, and analyzed. First, based on the research background of complex networks, a general research framework for dynamic community detection is proposed. Then, the relevant definitions of dynamic community detection are formally expressed, and the evolution of dynamic communities at the network level and node level is analyzed in detail. According to the difference in architecture and technology, the dynamic community detection methods are summarized and classified. Combined with commonly used data sets, the static community detection algorithm is analyzed qualitatively and quantitatively with evaluation criteria. Finally, the typical application scenarios of community detection are introduced, the main challenges faced by current dynamic community detection research are discussed, and relevant solutions are put forward for dynamic communities, which outlines a clearer and comprehensive research direction for dynamic community detection research field.

Key words: dynamic community detection, social network, network analysis, dynamic community evolution

摘要：

随着社交媒体多样性的增加，实时分析社交网络的需求不断增大，动态社区发现的研究受到了广泛的关注。已有的社区发现综述多是侧重静态社区发现，以及相关方法的探讨，无法进行网络演化分析，此外社区的实体数据往往具有交叉更替性和时序性,因此对动态社区发现的研究现状进行分析和综述。首先，基于复杂网络的研究背景，提出了通用的动态社区发现研究框架；接着，形式化表示动态社区发现的相关定义，并从网络层面和节点层面对动态社区演化进行详细分析；然后，根据架构和技术的不同，对动态社区发现方法进行归纳分类，并结合常用数据集和评价指标对经典静态社区发现算法进行定性和定量分析；最后，介绍了社区发现的典型应用场景，探讨了当前动态社区发现研究面临的主要挑战，针对性地提出了相关解决方案，为动态社区发现研究领域勾画出较为清晰和全面的研究方向。

关键词: 动态社区发现, 社交网络, 网络分析, 动态社区演化

DUAN Xiangyu, YUAN Guan, MENG Fanrong. Dynamic Community Detection: A Survey[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(4): 612-630.

端祥宇, 袁冠, 孟凡荣. 动态社区发现方法研究综述[J]. 计算机科学与探索, 2021, 15(4): 612-630.

References

[1] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486: 75-174.
[2] GIRVAN M, NEWMAN M E. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.
[3] ZHANG X, LIU B Q, WANG X L. Research on community detection methods in complex network[J]. Computer Engin-eering and Applications, 2015, 51(24): 1-7.
张鑫, 刘秉权, 王晓龙. 复杂网络中社区发现方法的研究[J]. 计算机工程与应用, 2015, 51(24): 1-7.
[4] GUIMERA R, AMARAL L. Functional cartography of com-plex metabolic networks[J]. Nature, 2005, 433(7028): 895-900.
[5] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. The Bell System Technical Journal, 1970, 49(2): 291-307.
[6] CAPOCCI A, BALDASSARRI A, SERVEDIO V D, et al. Friendship, collaboration and semantics in Flickr: from social interaction to semantic similarity[C]//Proceedings of the 2010 International Workshop on Modeling Social Media, Toronto, Jun 13, 2010. New York: ACM, 2010: 1-4.
[7] PALLA G, BARABáSI A, VICSEK T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667.
[8] NEWMAN M E. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
[9] NEWMAN M E, GIRVAN M. Finding and evaluating com-munity structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[10] NEWMAN M E. Equivalence between modularity optim-ization and maximum likelihood methods for community detection[J]. Physical Review E, 2016, 94(5): 052315.
[11] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3): 036106.
[12] MARTIN T, BALL B, NEWMAN M E. Structural inference for uncertain networks[J]. Physical Review E, 2016, 93(1): 012306.
[13] PALLA G, DERéNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
[14] DERéNYI I, PALLA G, VICSEK T. Clique percolation in random networks[J]. Physical Review Letters, 2005, 94(16): 160202.
[15] PALLA G, FARKAS I J, POLLNER P, et al. Directed network modules[J]. New Journal of Physics, 2007, 9(6): 186.
[16] ROSVALL M, BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Procee-dings of the National Academy of Sciences, 2008, 105(4): 1118-1123.
[17] LANCICHINETTI A, FORTUNATO S, KERTéSZ J. Det-ecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009, 11(3): 033015.
[18] ZHANG S, WANG R S, ZHANG X S. Identification of overlapping community structure in complex networks using fuzzy C-means clustering[J]. Physica A: Statistical Mechanics and Its Applications, 2007, 374(1): 483-490.
[19] DENG G L, MA Z X, LI X B. Overlapping community detection algorithm based on Markov chain clustering[C]// Proceedings of the 2018 IEEE 3rd International Conference on Big Data Analysis, Shanghai, Mar 9-12, 2018. Piscataway: IEEE, 2018: 458-462.
[20] QIU B J, IVANOVA K, YEN J, et al. Study of effect of node seniority in social networks[C]//Proceedings of the 2010 IEEE International Conference on Intelligence and Security Informatics, Vancouver, May 23-26, 2010. Piscataway: IEEE, 2010: 147-149.
[21] QIU B J, IVANOVA K, YEN J, et al. Behavior evolution and event-driven growth dynamics in social networks[C]// Proceedings of the 2010 IEEE 2nd International Conference on Social Computing, Minneapolis, Aug 20-22, 2010. Was-hington: IEEE Computer Society, 2010: 217-224.
[22] DAKICHE N, TAYEB F B, SLIMANI Y, et al. Tracking community evolution in social networks: a survey[J]. Infor-mation Processing & Management, 2019, 56(3): 1084-1102.
[23] ASUR S, PARTHASARATHY S, UCAR D. An event-based framework for characterizing the evolutionary behavior of interaction graphs[J]. ACM Transactions on Knowledge Discovery from Data, 2009, 3(4): 1-36.
[24] BRóDKA P, SAGANOWSKI S, KAZIENKO P. GED: the method for group evolution discovery in social networks[J]. Social Network Analysis and Mining, 2013, 3(1): 1-14.
[25] GREENE D, DOYLE D, CUNNINGHAM P. Tracking the evolution of communities in dynamic social networks[C]// Proceedings of the 2010 International Conference on Adv-ances in Social Networks Analysis and Mining, Odense, Aug 9-11, 2010. Washington: IEEE Computer Society, 2010: 176-183.
[26] CAZABET R, AMBLARD F, HANACHI C. Detection of overlapping communities in dynamical social networks[C]// Proceedings of the 2010 IEEE 2nd International Conference on Social Computing, SocialCom/IEEE International Confer-ence on Privacy, Security, Risk and Trust, Minneapolis, Aug 20-22, 2010. Washington: IEEE Computer Society, 2010: 309-314.
[27] ZHAO Z Y, LI C, ZHANG X J, et al. An incremental method to detect communities in dynamic evolving social networks[J]. Knowledge Based Systems, 2019, 163: 404-415.
[28] GAO W H, LUO W J, BU C Y. Evolutionary community discovery in dynamic networks based on leader nodes[C]//Proceedings of the 2016 International Conference on Big Data and Smart Computing, Hong Kong, China, Jan 18-20, 2016. Washington: IEEE Computer Society, 2016: 53-60.
[29] XIN Y, XIE Z Q, YANG J. An adaptive random walk sam-pling method on dynamic community detection[J]. Expert Systems with Applications, 2016, 58: 10-19.
[30] HE J, CHEN D. A fast algorithm for community detection in temporal network[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 429: 87-94.
[31] GUO C, WANG J, ZHANG Z. Evolutionary community structure discovery in dynamic weighted networks[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 413(11): 565-576.
[32] ZHANG G Z, ZHANG X K, SU J, et al. Research on evo-lutionary community discovery algorithm in dynamic weighted networks[J]. Application Research of Computers, 2019, 36(4): 992-996.
张高祯, 张贤坤, 苏静, 等. 动态加权网络中的演化社区发现算法研究[J]. 计算机应用研究, 2019, 36(4): 992-996.
[33] AGARWAL P, VERMA R, AGARWAL A, et al. DyPerm: maximizing permanence for dynamic community detection [C]//LNCS 10937: Proceedings of the 22nd Pacific-Asia Con-ference on Knowledge Discovery and Data Mining, Melbourne, Jun 3-6, 2018. Berlin, Heidelberg: Springer, 2018: 437-449.
[34] CORDEIRO M, SARMENTO R P, GAMA J. Dynamic community detection in evolving networks using locality modularity optimization[J]. Social Network Analysis and Mining, 2016, 6(1): 15.
[35] GUO K, PENG S B, CHEN Y Z, et al. Incremental dynamic community detection algorithm based on density clustering [J]. Pattern Recognition and Artificial Intelligence, 2018, 31(11): 965-978.
郭昆, 彭胜波, 陈羽中, 等. 基于密度聚类的增量动态社区发现算法[J]. 模式识别与人工智能, 2018, 31(11): 965-978.
[36] DUAN D, LI Y, LI R, et al. Incremental K-clique clustering in dynamic social networks[J]. Artificial Intelligence Review, 2012, 38(2): 129-147.
[37] JIANG S Y, YANG B H, WANG L X. An adaptive dynamic community detection algorithm based on incremental spectral clustering[J]. Acta Automatica Sinica, 2015, 41(12): 2017-2025.
蒋盛益, 杨博泓, 王连喜. 一种基于增量式谱聚类的动态社区自适应发现算法[J]. 自动化学报, 2015, 41(12): 2017-2025.
[38] NING H Z, XU W, CHI Y, et al. Incremental spectral clustering by efficiently updating the Eigen-system[J]. Pattern Recognition, 2010, 43(1): 113-127．
[39] XIE J R, CHEN M M, SZYMANSKI B K. LabelrankT: incremental community detection in dynamic networks via label propagation[C]//Proceedings of the 2013 Workshop on Dynamic Networks Management and Mining, New York, Jun 22-27, 2013. New York: ACM, 2013: 25-32.
[40] XIN Y, XIE Z, YANG J. The adaptive dynamic community detection algorithm based on the non-homogeneous random walking[J]. Physica A: Statistical Mechanics and Its App-lications, 2016, 450: 241-252.
[41] ZHU T Y. Incremental dynamic community discovery algor-ithm based on density[D]. Fuzhou: Fuzhou University, 2017.
朱腾云. 基于密度的增量动态社区发现算法研究[D]. 福州: 福州大学, 2017.
[42] SUN H, HUANG J, ZHANG X, et al. IncOrder: incremen-tal density-based community detection in dynamic networks[J]. Knowledge-Based Systems, 2014, 72: 1-12.
[43] QIN X, DAI W, JIAO P, et al. A multi-similarity spectral clustering method for community detection in dynamic networks[J]. Scientific Reports, 2016, 6: 31454.
[44] LIU F, CHOI D, XIE L, et al. Global spectral clustering in dynamic networks[J]. Proceedings of the National Academy of Sciences, 2018, 115(5): 927-932.
[45] JDIDIA M B, ROBARDET C, Fleury E. Communities detection and analysis of their dynamics in collaborative networks[C]//Proceedings of the 2007 IEEE International Conference on Digital Information Management, Lyon, Dec 11-13, 2007. Piscataway: IEEE, 2007: 744-749.
[46] LIU K, HUANG J, SUN H, et al. Label propagation based evolutionary clustering for detecting overlapping and non-overlapping communities in dynamic networks[J]. Knowledge- Based Systems, 2015, 89: 487-496.
[47] SATTARI M, ZAMANIFAR K. A cascade information diffusion based label propagation algorithm for community detection in dynamic social networks[J]. Journal of Com-putational Science, 2018, 25: 122-133.
[48] PONS P, LATAPY M. Computing communities in large networks using random walks[C]//LNCS 3733: Proceedings of the 20th International Symposium, Istanbul, Oct 26-28, 2005. Berlin, Heidelberg: Springer, 2005: 284-293.
[49] XIE J R, SZYMANSKI B K. Labelrank: a stabilized label propagation algorithm for community detection in networks[C]//Proceedings of the 2nd IEEE Network Science Workshop, West Point, Apr 29-May 1, 2013. Washington: IEEE Computer Society, 2013: 138-143.
[50] JIN D, YOU X X, LIU Y S, et al. Structural feature enhanced Markov random field for community detection in large-scale networks[J]. Chinese Journal of Computers, 2019, 42(12): 2821-2835.
金弟, 尤心心, 刘岳森, 等. 结构特征强化的高效马尔可夫随机场社团发现方法[J]. 计算机学报, 2019, 42(12): 2821-2835.
[51] XU K S, HERO A O. Dynamic stochastic blockmodels for time-evolving social networks[J]. IEEE Journal of Selected Topics in Signal Processing, 2014, 8(4): 552-562.
[52] YANG T, CHI Y, ZHU S, et al. Detecting communities and their evolutions in dynamic social networks—a Bayesian approach[J]. Machine Learning, 2011, 82(2): 157-189.
[53] WANG W, JIAO P, HE D, et al. Autonomous overlapping community detection in temporal networks: a dynamic Bayesian nonnegative matrix factorization approach[J]. Knowledge-Based Systems, 2016, 110: 121-134.
[54] LIN Y R, CHI Y, ZHU S H, et al. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks[C]//Proceedings of the 17th International Confer-ence on World Wide Web, Beijing, Apr 21-25, 2008. New York: ACM, 2008: 685-694.
[55] GAO F, YUAN L, WANG W, et al. Dynamic community detection using nonnegative matrix factorization[C]//Proc-eedings of the 2017 International Conference on Computing Intelligence and Information System, Nanjing, Apr 21-23,2017. Washington: IEEE Computer Society, 2017: 39-45.
[56] MA X, DONG D. Evolutionary nonnegative matrix factor-ization algorithms for community detection in dynamic networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(5): 1045-1058.
[57] MA X, LI D, TAN S, et al. Detecting evolving com-munities in dynamic networks using graph regularized evolutionary nonnegative matrix factorization[J]. Physica A: Statal Mechanics and Its Applications, 2019, 530: 121279.
[58] MA L, ZHANG Y, LI J, et al. Community-aware dynamic network embedding by using deep autoencoder[J]. Infor-mation Sciences, 2020, 519: 22-42.
[59] MUCHA P J, RICHARDSON T, MACON K, et al. Com-munity structure in time-dependent, multiscale, and multiplex networks[J]. Science, 2010, 328(5980): 876-878.
[60] NIU X, SI W, WU C Q. A label-based evolutionary com-puting approach to dynamic community detection[J]. Computer Communications, 2017, 108: 110-122.
[61] GAO C, CHEN Z, LI X, et al. Multiobjective discrete particle swarm optimization for community detection in dynamic networks[J]. Europhysics Letters, 2018, 122(2): 28001.
[62] WANG C, DENG Y, LI X, et al. Dynamic community detection based on a label-based swarm intelligence[J]. IEEE Access, 2019, 7: 161641-161653.
[63] AYNAUD T, GUILLAUME J L. Long range community detection[C]//Proceedings of the 2010 LAWDN Latin-American Workshop on Dynamic Networks, Buenos Aires, Nov 3, 2010: 1-4.
[64] 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(10): P10008.
[65] NEWMAN M E. Modularity and community structure in networks[J]. Proceedings of the National Academy of Scien-ces, 2006, 103(23): 8577-8582.
[66] SHEN H, CHENG X, CAI K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A: Statistical Mechanics and Its Applications, 2009, 388(8): 1706-1712.
[67] FORTUNATO S, BARTHELEMY M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.
[68] CHAKRABORTY T, SRINIVASAN S, GANGULY N, et al. On the permanence of vertices in network communities[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, Aug 24-27, 2014. New York: ACM, 2014: 1396-1405.
[69] TAKAFFOLI M, RABBANY R, ZA?ANE O R. Incremental local community identification in dynamic social networks [C]//Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Niagara, Aug 25-29, 2013. New York: ACM, 2013: 90-94.
[70] TABARZAD M A, HAMZEH A. Incremental community miner for dynamic networks[J]. Applied Intelligence, 2018, 48(10): 3372-3393.
[71] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algo-rithms[J]. Physical Review E, 2008, 78(4): 046110.
[72] PARéS F, GASULLA D G, VILALTA A, et al. Fluid communities: a competitive, scalable and diverse community detection algorithm[C]//Proceedings of the 6th International Conference on Complex Networks and Their Applications, Lyon, Nov 29-Dec 1, 2017. Berlin, Heidelberg: Springer, 2017: 229-240.
[73] VON LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4): 395-416.
[74] CLAUSET A, Newman M E, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.
[75] WEEKS M R, CLAIR S, BORGATTI S P, et al. Social networks of drug users in high-risk sites: finding the connections[J]. AIDS and Behavior, 2002, 6(2): 193-206.
[76] KARATA? A, ?AHIN S. Application areas of community detection: a review[C]//Proceedings of the 2018 International Congress on Big Data, Deep Learning and Fighting Cyber Terrorism, Ankara, Dec 3-4, 2018. Piscataway: IEEE, 2018: 65-70.
[77] FERRARA E, DE MEO P, CATANESE S, et al. Detecting criminal organizations in mobile phone networks[J]. Expert Systems with Applications, 2014, 41(13): 5733-5750.
[78] CALDERONI F, BRUNETTO D, PICCARDI C. Commun-ities in criminal networks: a case study[J]. Social Networks, 2017, 48: 116-125.
[79] SARVARI H, ABOZINADAH E, MBAZIIRA A, et al. Constructing and analyzing criminal networks[C]//Proceedings of the IEEE Security and Privacy Workshops, San Jose, May 17-18, 2014. Washington: IEEE Computer Society, 2014: 84-91.
[80] LU Y, ZHANG P, LIU J, et al. Health-related hot topic detection in online communities using text clustering[J]. PLoS One, 2013, 8(2): e56221.
[81] SALATHé M, JONES J H. Dynamics and control of diseases in networks with community structure[J]. PLoS Computational Biology, 2010, 6(4): e1000736.
[82] BECHTEL J J, KELLEY W A, COONS T A, et al. Lung cancer detection in patients with airflow obstruction identified in a primary care outpatient practice[J]. Chest, 2005, 127(4): 1140-1145.
[83] HAQ N F, WANG Z J. Community detection from genomic datasets across human cancers[C]//Proceedings of the 2016 IEEE Global Conference on Signal and Information Processing, Washington, Dec 7-9, 2016. Piscataway: IEEE, 2016: 1147-1150.
[84] TAYA F, DE SOUZA J, THAKOR N V, et al. Comparison method for community detection on brain networks from neuroimaging data[J]. Applied Network Science, 2016, 1: 8.
[85] YANG Y, SUN P G, HU X, et al. Closed walks for community detection[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 397: 129-143.
[86] MOSADEGH M J, BEHBOUDI M. Using social network paradigm for developing a conceptual framework in CRM[J]. Australian Journal of Business and Management Research, 2011, 1(4): 63.
[87] REZAEIMEHR F, MORADI P, AHMADIAN S, et al. TCARS: time-and community-aware recommendation system[J]. Future Generation Computer Systems, 2018, 78: 419-429.
[88] GURINI D F, GASPARETTI F, MICARELLI A, et al. iSCUR: interest and sentiment-based community detection for user recommendation on Twitter[C]//LNCS 8538: Procee-dings of the 22nd International Conference on User Mod-eling, Adaptation, and Personalization, Aalborg, Jul 7-11, 2014. Berlin, Heidelberg: Springer, 2014: 314-319.
[89] LALWANI D, SOMAYAJULU D V L N, KRISHNA P R. A community driven social recommendation system[C]//Proc-eedings of the 2015 IEEE International Conference on Big Data, Santa Clara, Oct 29 - Nov 1, 2015. Washington: IEEE Computer Society, 2015: 821-826.
[90] BRINGMANN B, BERLINGERIO M, BONCHI F, et al. Learning and predicting the evolution of social networks[J]. IEEE Intelligent Systems, 2010, 25(4): 26-35.
[91] ?LHAN N, ??üDüCü ? G. Feature identification for predicting community evolution in dynamic social networks[J]. Engineering Applications of Artificial Intelligence, 2016, 55: 202-218.
[92] VALVERDE-REBAZA J C, DE ANDRADE LOPES A. Link prediction in complex networks based on cluster infor-mation[C]//LNCS 7589: Proceedings of the 21st Brazilian Symposium on Artificial Intelligence, Curitiba, Oct 20-25, 2012. Berlin, Heidelberg: Springer, 2012: 92-101.
[93] SOUNDARAJAN S, HOPCROFT J E. Using community information to improve the precision of link prediction methods[C]//Proceedings of the 21st World Wide Web Conference, Lyon, Apr 16-20, 2012. New York: ACM, 2012: 607-608.
[94] XIA Z, BU Z. Community detection based on a semantic network[J]. Knowledge-Based Systems, 2012, 26: 30-39.
[95] INTERDONATO R, TAGARELLI A, IENCO D, et al. Local community detection in multilayer networks[J]. Data Mining and Knowledge Discovery, 2017, 31(5): 1444-1479.
[96] MENG Q X, TAFAVOGH S, KENNEDY P J, et al. Com-munity detection on heterogeneous networks by multiple semantic-path clustering[C]//Proceedings of the 6th Inter-national Conference on Computational Aspects of Social Networks, Porto, Jul 30-Aug 1, 2014. Piscataway: IEEE, 2014: 7-12.
[97] WANG H W, ZHANG F Z, HOU M, et al. SHINE: signed heterogeneous information network embedding for sentiment link prediction[C]//Proceedings of the 11th ACM International Conference on Web Search and Data Mining, Marina Del Rey, Feb 5-9, 2018. New York: ACM, 2018: 592-600.