a. School of Systems Science, Beijing 100875, China; b. Center for Computational Communication Research, Zhuhai 519085, China; c. School of Journalism and Communication, Beijing 100875, China; d. School of Arts & Communication, Beijing Normal University, Beijing 100875, China
Abstract：In order to adapt to the development of dynamic network data, the detection, tracking and prediction of the community structure in dynamic networks have been a crucial research problem at present. This research reviewed the literatures on community discovery and community evolution in dynamic networks at home and abroad. This research summarized the community discovery algorithm of dynamic network, clarified the definitions of community evolution events, and sorted out the application scenarios of community evolution algorithm. Through literature review, it is believed that future dynamic community research should focus on algorithm optimization on large data sets, data mining in multiple contexts, and applicability in multiple scenarios.
李永宁, 吴晔, 张伦. 动态社团发现研究综述[J]. 复杂系统与复杂性科学, 2021, 18(2): 1-8.
LI Yongning, WU Ye, ZHANG Lun. A Review of Dynamic Community Detection. Complex Systems and Complexity Science, 2021, 18(2): 1-8.
[1]骆志刚,丁凡,蒋晓舟,等.复杂网络社团发现算法研究新进展[J].国防科技大学学报,2011,33(1):47-52.
Luo Zhigang, Ding Fan, Jiang Xiaozhou, et al. New progress on community detection in complex networks[J]. Journal of National University of Defense Technology, 2011,33(1):47-52.
[2]Ferligoj A, Batagelj V. Direct multicriteria clustering algorithms[J]. Journal of Classification, 1992, 9(1): 43-61.
[3]Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.
[4]Strogatz S H. Exploring complex networks[J]. Nature, 2001, 410(6825): 268-276.
[5]Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
[6]Gasparetti F, Micarelli A, Sansonetti G. Community detection and recommender systems[DB/OL]. [2020-07-01]. https://doi.org/10.1007/978-1-4939-7131-2_110160.
[7]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.
[8]Dakiche N, Tayeb F B S, Slimani Y, et al. Tracking community evolution in social networks: a survey[J]. Information Processing & Management, 2019, 56(3): 1084-1102.
[9]李晓佳, 张鹏, 狄增如, 等.复杂网络中的社团结构[J].复杂系统与复杂性科学, 2008, 5(3):19-42.
Li Xiaojia, Zhang Peng, Di Zengru, et al. Community structure in complex networks[J]. Complex Systems and Complexity Science, 2008, 5(3):19-42.
[10] Bu Z, Wu Z, Cao J, et al. Local community mining on distributed and dynamic networks from a multiagent perspective[J]. IEEE Transactions on Cybernetics, 2015, 46(4): 986-999.
[11] 贾珺,胡晓峰,贺筱媛.基于节点动态连接度的网络社团划分算法[J].复杂系统与复杂性科学,2016,13(4):56-61.
Jia Jun, Hu Xiaofeng. He Xiaoyuan. Finding community structure in networks using node′s dynamic connection degree[J]. Complex Systems and Complexity Science, 2016,13(4):56-61.
[12] 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.
[13] Pan Y, Li D H, Liu J G, et al. Detecting community structure in complex networks via node similarity[J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389(14): 2849-2857.
[14] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences, 2004, 101(9): 2658-2663.
[15] Newman M E J. Detecting community structure in networks[J]. The European Physical Journal B, 2004, 38(2): 321-330.
[16] Reichardt J, Bornholdt S. Detecting fuzzy community structures in complex networks with a Potts model[J]. Physical Review Letters, 2004, 93(21): 218701.
[17] Capocci A, Servedio V D P, Caldarelli G, et al. Detecting communities in large networks[J]. Physica A: Statistical Mechanics and Its Applications, 2005, 352(2-4): 669-676.
[18] Pons P, Latapy M. Computing communities in large networks using random walks[C]// Yolum P, Güngör T, Gürgen F, et al. Computer and Information Sciences-ISCIS 2005. Berlin, Heidelberg: Springer, 2005: 284-293.
[19] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
[20] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. The Bell System Technical Journal, 1970, 49(2): 291-307.
[21] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452.
[22] Xie J, Kelley S, Szymanski B K. Overlapping community detection in networks: The state-of-the-art and comparative study[J]. ACM Comput Surv, 2013, 45(4): 1-35.
[23] 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.
[24] Qiu B, Ivanova K, Yen J, et al. Behavior evolution and event-driven growth dynamics in social networks[C]// SocialCom 2010 PASSAT 2010. Danvers, MA, US: IEEE, 2010: 217-224.
[25] Gouvêa A M M M, Vega-Oliveros D A, Cotacallapa M, et al. Dynamic community detection into analyzing of wildfires events[C]// Computational Science and Its Applications-ICCSA 2020. Cham, Switzerland: Springer, 2020: 1032-1047.
[26] Ricci F, Rokach L, Shapira B. Recommender Systems Handbook[M]. Boston, MA, US: Springer, 2015: 1-34.
[27] Samie M E, Hamzeh A. Change-aware community detection approach for dynamic social networks[J]. Applied Intelligence, 2018, 48(1): 78-96.
[28] Seifikar M, Farzi S, Barati M. C-Blondel: an efficient louvain-based dynamic community detection algorithm[J]. IEEE Transactions on Computational Social Systems, 2020, 7(2): 308-318.
[29] Boujlaleb L, Idarrou A, Mammass D, et al. User-centric approach of detecting temporary community[C]//Proceedings of 2015 IEEE World Conference on Complex Systems. Marrakech, The Kingdom of Morocco: IEEE, 2015: 1-6.
[30] Wang Y, Wu B, Du N. Community evolution of social network: feature, algorithm and model[DB/OL]. [2020-07-01]. https://arxiv.org/abs/0804.4356.
[31] Sun Y, Tang J, Pan L, et al. Matrix based community evolution events detection in online social networks[C]//2015 IEEE International Conference on Smart City. NJ, US: IEEE, 2015: 465-470.
[32] 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.
[33] Azaouzi M, Rhouma D, Romdhane L B. Community detection in large-scale social networks: state-of-the-art and future directions[J]. Social Network Analysis and Mining, 2019, 9(1): 1-23.
[34] 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.
[35] Shang J, Liu L, Li X, et al. Targeted revision: a learning-based approach for incremental community detection in dynamic networks[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 443: 70-85.
[36] Zhao Z, Li C, Zhang X, et al. An incremental method to detect communities in dynamic evolving social networks[J]. Know-ledge-Based Systems, 2019, 163: 404-415.
[37] Wang Z, Li Z, Yuan G, et al. Tracking the evolution of overlapping communities in dynamic social networks[J]. Knowledge-Based Systems, 2018, 157: 81-97.
[38] Jdidia M B, Robardet C, Fleury E. Communities detection and analysis of their dynamics in collaborative networks[C]// 2007 2nd International Conference on Digital Information Management. Lyon, France: IEEE, 2007: 744-749.
[39] Aynaud T, Guillaume J L. Static community detection algorithms for evolving networks[C]// 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks. Avignon, France: IEEE, 2010: 513-519.
[40] Mitra B, Tabourier L, Roth C. Intrinsically dynamic network communities[J]. Computer Networks, 2012, 56(3): 1041-1053.
[41] Li J, Huang L, Bai T, et al. CDBIA: a dynamic community detection method based on incremental analysis[C]//2012 International Conference on Systems and Informatics. Yantai, China: IEEE, 2012: 2224-2228.
[42] Rossetti G, Pappalardo L, Pedreschi D, et al. Tiles: an online algorithm for community discovery in dynamic social networks[J]. Machine Learning, 2017, 106(8): 1213-1241.
[43] Nguyen N P, Dinh T N, Tokala S, et al. Overlapping communities in dynamic networks: their detection and mobile applications[C]//Proceedings of the 17th Annual International Conference on Mobile Computing and Networking. NY, USA: Association for Computing Machinery, 2011: 85-96.
[44] Boudebza S, Cazabet R, Azouaou F, et al. Olcpm: an online framework for detecting overlapping communities in dynamic social networks[J]. Computer Communications, 2018, 123: 36-51.
[45] Saganowski S, Bródka P, Koziarski M, et al. Analysis of group evolution prediction in complex networks[J]. PloS One, 2019, 14(10): e0224194.
[46] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[47] 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.
[48] Krebs V. Working in the connected world book network[J]. International Association for Human Resource Information Management Journal, 2000, 4(1): 87-90.
[49] Guimera R, Danon L, Diaz-Guilera A, et al. Self-similar community structure in a network of human interactions[J]. Physical Review E, 2003, 68(6): 065103.
[50] 汪小帆,刘亚冰.复杂网络中的社团结构算法综述[J].电子科技大学学报,2009,38(5):537-543.
Wang Xiaofan, Liu Yabing. Overview of algorithms for detecting community structure in complex networks[J]. Journal of University of Electronic Science and Technology of China,2009,38(5):537-543.
[51] Newman M E J. Analysis of weighted networks[J]. Physical Review E, 2004, 70(5): 056131.
[52] Newman M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582.
[53] Arenas A, Fernandez A, Gomez S. Analysis of the structure of complex networks at different resolution levels[J]. New Journal of Physics, 2008, 10(5): 053039.
[54] Bródka P, Saganowski S, Kazienko P. Community evolution[DB/OL]. [2020-07-01]. https://doi.org/10.1007/978-1-4614-6170-8_223.
[55] Palla G, Barabási A L, Vicsek T. Quantifying social group evolution[J]. Nature, 2007, 446(7136): 664-667.
[56] Xu H, Hu Y, Wang Z, et al. Core-based dynamic community detection in mobile social networks[J]. Entropy, 2013, 15(12): 5419-5438.
[57] Cazabet R, Rossetti G. Challenges in community discovery on temporal networks[M]// Holme P, Saramäki J. Temporal Network Theory. Cham, Switzerland: Springer, 2019: 181-197.
[58] Dakiche N, Tayeb F B S, Slimani Y, et al. Tracking community evolution in social networks: a survey[J]. Information Processing & Management, 2019, 56(3): 1084-1102.
[59] Mohammadmosaferi K K, Naderi H. Evolution of communities in dynamic social networks: an efficient map-based approach[J]. Expert Systems with Applications, 2020, 147: 113221.
[60] Wang R, Rho S. Dynamics prediction of large-scale social network based on cooperative behavior[J]. Sustainable Cities and Society, 2019, 46: 101435.
[61] Varga A. Shorter distances between papers over time are due to more cross-field references and increased citation rate to higher-impact papers[J]. Proceedings of the National Academy of Sciences, 2019, 116(44): 22094-22099.
[62] Singh C K, Jolad S. Structure and evolution of Indian physics co-authorship networks[J]. Scientometrics, 2019, 118(2): 385-406.[63] Atzmueller M, Ernst A, Krebs F, et al. Formation and temporal evolution of social groups during coffee breaks[M]// Atzmueller M, Chin A, Janssen F, et al. Big Data Analytics in the Social and Ubiquitous Context. Cham, Switzerland: Springer, 2015: 90-108.
[64] 齐金山,梁循,张树森,等.在线社会网络的动态社区发现及其演化[J].北京理工大学学报,2017,37(11):1156-1162.
Qi Jinshan, Liang Xun, Zhang Shusen, et al. Detection and evolution of dynamic communities in online social network [J]. Transactions of Beijing Institute of Technology,2017,37(11):1156-1162.
[65] 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.
[66] Karthika S, Geetha R. Communalyzer—Understanding life cycle of community in social networks[M]// Saini H S, Sayal R, Govardhan A, et al. Innovations in Computer Science and Engineering. Singapore: Springer, 2019: 197-204.
[67] Goldberg M, Magdon-Ismail M, Nambirajan S, et al. Tracking and predicting evolution of social communities[C]// 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third International Conference on Social Computing. Boston, MA, USA: IEEE, 2011: 780-783.
[68] 王莉, 程学旗. 在线社会网络的动态社区发现及演化[J]. 计算机学报, 2015, 38(2): 219-237.
Wang Li, Cheng Xueqi. Detection and evolution of dynamic communities in online social network[J]. Chinese Journal of Computers, 2015, 38(2): 219-237.
[69] Gao W, Luo W, Bu C. Evolutionary community discovery in dynamic networks based on leader nodes[C]//2016 International Conference on Big Data and Smart Computing (BigComp). Hong Kong, China: IEEE, 2016: 53-60.
[70] Benson A R, Gleich D F, Leskovec J. Higher-order organization of complex networks[J]. Science, 2016, 353(6295): 163-166.
[71] 王莉, 程苏琦, 沈华伟, 等. 在线社会网络共演化的结构推断与预测[J]. 计算机研究与发展, 2013, 50(12): 2492-2503.
Wang Li, Cheng Suqi, Shen Huawei, et al. Structure inference and prediction in the co-evolution of social networks[J]. Journal of Computer Research and Development, 2013, 50(12): 2492-2503.
[72] 杨波, 游新冬, 段文奇.复杂动态网络演化社团结构探测分析的研究进展[J]. 计算机应用研究, 2013, 30(5): 1292-1296.
Yang Bo, You Xindong, Duan Wenqi. Progress on analysis for detecting evolutionary community structure in complex dynamical networks[J]. Application Research of Computers, 2013, 30(5): 1292-1296.
