融合异质性和动态性的社区发现研究综述

doi:10.3778/j.issn.1002-8331.2403-0432

摘要/Abstract

摘要： 随着社交网络的发展，图结构成为数据处理的关键技术。社区发现是图结构研究的热点领域，旨在识别连接紧密的结点组（即社区）。由于图结构具有异质性和动态性特征，异质图和动态图中的社区发现成为当前研究难点。已有综述大都针对单一特性开展，对于异质性和动态性特征关注较少。基于此，从图的异质性和动态性两方面进行深入调研，总结社区发现领域的研究进展。介绍社区发现相关的基础知识，并针对异质性和动态性特征汇总了相关数据集和评价指标。针对社区发现算法不同的目标对象，将现有社区发现研究分为静态同质图社区发现、静态异质图社区发现、动态同质图社区发现和动态异质图社区发现，并分别进行文献综述及优缺点分析。总结社区发现算法的应用领域和未来研究方向，并展望了社区发现研究的未来发展趋势。

关键词: 图结构, 社区发现, 异质性, 动态性

Abstract: With the development of social networks, graph structure has become a key technology in data processing. Community detection is a hot area of research in graph structures, aiming to identify groups of nodes that are closely connected (i.e., communities). Due to the heterogeneous and dynamic characteristics of graph structures, community detection in heterogeneous and dynamic graphs has become a current research challenge. Existing reviews mostly focus on a single characteristic, with less attention to heterogeneity and dynamics. Based on this, this paper conducts an in-depth investigation from the aspects of graph heterogeneity and dynamics, summarizing the research progress in the field of community detection. It introduces the basic knowledge related to community detection and summarizes the relevant datasets and evaluation metrics for the characteristics of heterogeneity and dynamics. Then, according to the different target objects of community detection algorithms, existing community detection research is divided into static homogeneous graph community detection, static heterogeneous graph community detection, dynamic homogeneous graph community detection, and dynamic heterogeneous graph community detection, and a literature review and analysis of advantages and disadvantages are conducted for each. Finally, the application fields of community detection algorithms and future research directions are summarized, and the future development trend of community detection research is prospected.

Key words: graph structure, community detection, heterogeneity, dynamic

武永亮, 窦世卯, 李景辉, 董家浩, 魏丹. 融合异质性和动态性的社区发现研究综述[J]. 计算机工程与应用, 2024, 60(21): 55-72.

WU Yongliang, DOU Shimao, LI Jinghui, DONG Jiahao, WEI Dan. Survey of Community Detection from Perspectives of Dynamics and Heterogeneity[J]. Computer Engineering and Applications, 2024, 60(21): 55-72.

参考文献

[1] SATULURI V, WU Y, ZHENG X, et al. SimClusters: community-based representations for heterogeneous recommendations at Twitter[C]//Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020: 3183-3193.
[2] WU Y L, FU Y, XU J W, et al. Heterogeneous question answering community detection based on graph neural network[J]. Information Sciences, 2023, 621: 652-671.
[3] DOLUCA O, OGUZ K. APAL: adjacency propagation algorithm for overlapping community detection in biological networks[J]. Information Sciences, 2021, 579: 574-590.
[4] SUN H, HE F, HUANG J, et al. Network embedding for community detection in attributed networks[J]. ACM Transactions on Knowledge Discovery from Data, 2020, 14(3): 1-25.
[5] ZHOU X, SU L, LI X, et al. Community detection based on unsupervised attributed network embedding[J]. Expert Systems with Applications, 2023, 213: 118937.
[6] ZHANG W, SHANG R, JIAO L. Large-scale community detection based on core node and layer-by-layer label propagation[J]. Information Sciences, 2023, 632: 1-18.
[7] YE F H, CHEN C, WEN Z Y, et al. Homophily preserving community detection[J]. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(8): 2903-2915.
[8] BASUCHOWDHURI P, SIKDAR S, NAGARAJAN V, et al. Fast detection of community structures using graph traversal in social networks[J]. Knowledge and Information Systems, 2019, 59(1): 1-31.
[9] FEI R, WAN Y, HU B, et al. A novel network core structure extraction algorithm utilized variational autoencoder for community detection[J]. Expert Systems with Applications, 2023, 222: 119775.
[10] SUN J Y, ZHENG W, ZHANG Q F, et al. Graph neural network encoding for community detection in attribute networks[J]. IEEE Transactions on Cybernetics, 2022, 52(8): 7791-7804.
[11] LIU H, WEI J, XU T. Community detection based on community perspective and graph convolutional network[J]. Expert Systems with Applications, 2023, 231: 120748.
[12] ZHANG Y, XIONG Y, YE Y, et al. SEAL: learning heuristics for community detection with generative adversarial networks[C]//Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020: 1103-1113.
[13] TOTH C, HELIC D, GEIGER B C. Synwalk: community detection via random walk modelling[J]. Data Mining and Knowledge Discovery, 2022, 36(2): 739-780.
[14] OKUDA M, SATOH S I, SATO Y, et al. Community detection using restrained random-walk similarity[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 43(1): 89-103.
[15] SHEN X, YAO X, TU H, et al. Parallel multi-objective evolutionary optimization based dynamic community detection in software ecosystem[J]. Knowledge-Based Systems, 2022, 252: 109404.
[16] SUN Y, SUN X, LIU Z, et al. Core node knowledge based multi-objective particle swarm optimization for dynamic community detection[J]. Computers & Industrial Engineering, 2023, 175: 108843.
[17] BOLORUNDURO J O, ZOU Z. Community detection on multi-layer graph using intra-layer and inter-layer linkage graphs (CDMIILG)[J]. Expert Systems with Applications, 2024, 238: 121713.
[18] YANG H, CHENG J, SU X, et al. A spiderweb model for community detection in dynamic networks[J]. Applied Intelligence, 2021, 51(7): 5157-5188.
[19] JIANG W, ZHANG X. Dynamic community detection algorithm based on allocating and splitting[C]//Proceedings of the IEEE International Conference on Tools with Artificial Intelligence, 2022: 1132-1137.
[20] 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.
[21] GONG C, JING C, SHEN Y, et al. Dynamic community detection via adversarial temporal graph representation learning[C]//Proceedings of the International Conference on Neural Computing for Advanced Applications, 2022: 1-13.
[22] COSTA A R, RALHA C G. AC2CD: an actor-critic architecture for community detection in dynamic social networks[J]. Knowledge-Based Systems, 2023, 261: 110202.
[23] YIN Y, ZHAO Y H, LI H, et al. Multi-objective evolutionary clustering for large-scale dynamic community detection[J]. Information Sciences, 2021, 549: 269-287.
[24] JIA T, CAI C, LI X, et al. Dynamical community detection and spatiotemporal analysis in multilayer spatial interaction networks using trajectory data[J]. International Journal of Geographical Information Science, 2022, 36(9): 1719-1740.
[25] CHAKRABORTY T, DALMIA A, MUKHERJEE A, et al. Metrics for community analysis: a survey[J]. ACM Computing Surveys, 2017, 50(4): 1-37.
[26] LIU X, CHENG H M, ZHANG Z Y. Evaluation of community detection methods[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(9): 1736-1746.
[27] 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, 2022, 33(3): 1203-1215.
[28] NI L, GE J, ZHANG Y, et al. Semi-supervised local community detection[J]. IEEE Transactions on Knowledge and Data Engineering, 2024, 36(2): 823-839.
[29] KANG D Y, LEE W, LEE Y C, et al. A framework for accurate community detection on signed networks using adversarial learning[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(11): 10937-10951.
[30] ZHU W, CHEN C, PENG B. Unified robust network embedding framework for community detection via extreme adversarial attacks[J]. Information Sciences, 2023, 643: 119200.
[31] WANG Y, CAO J, BU Z, et al. Dual structural consistency preserving community detection on social networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(11): 11301-11315.
[32] ZHOU J, CHEN Z, DU M, et al. RobustECD: enhancement of network structure for robust community detection[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(1): 842-856.
[33] WANG B, CAI X, XU M, et al. A graph-enhanced attention model for community detection in multiplex networks[J]. Expert Systems with Applications, 2023, 230: 120552.
[34] HE C, CHENG J, CHEN G, et al. Multiple topics community detection in attributed networks[C]//Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval, 2023: 2199-2203.
[35] QIN M, ZHANG C, BAI B, et al. Towards a better tradeoff between quality and efficiency of community detection: an inductive embedding method across graphs[J]. ACM Transactions on Knowledge Discovery from Data, 2023, 17(9): 1-34.
[36] WANG Z, LIANG Y B, JI P S. Spectral algorithms for community detection in directed networks[J]. Journal of Machine Learning Research, 2020, 21: 1-45.
[37] CHEN L, GAO Y J, HUANG X R, et al. Efficient distributed clustering algorithms on star-schema heterogeneous graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(10): 4781-4796.
[38] MEI J P, LV H J, YANG L H, et al. Clustering for heterogeneous information networks with extended star-structure[J]. Data Mining and Knowledge Discovery, 2019, 33(4): 1059-1087.
[39] LI X, KAO B, REN Z C, et al. Spectral clustering in heterogeneous information networks[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 4221-4228.
[40] DALL’AMICO L, COUILLET R, TREMBLAY N. Revisiting the bethe-hessian: improved community detection in sparse heterogeneous graphs[C]//Proceedings of the Conference on Neural Information Processing Systems, 2019: 4039-4049.
[41] QING H, WANG J. Community detection for weighted bipartite networks[J]. Knowledge-Based Systems, 2023, 274: 110643.
[42] XU D, CHEN Y, CUI N, et al. Towards multi-dimensional knowledge-aware approach for effective community detection in LBSN[J]. World Wide Web, 2023, 26(4): 1435-1458.
[43] SU S, GUAN J, CHEN B, et al. Nonnegative matrix factorization based on node centrality for community detection[J]. ACM Transactions on Knowledge Discovery from Data, 2023, 17(6): 1-21.
[44] ZHANG B H, GONG M G, HUANG J B, et al. Clustering heterogeneous information network by joint graph embedding and nonnegative matrix factorization[J]. ACM Transactions on Knowledge Discovery from Data, 2021, 15(4): 1-25.
[45] MA X K, DONG D, WANG Q. Community detection in multi-layer networks using joint nonnegative matrix factorization[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 31(2): 273-286.
[46] KONG Q, SUN J, XU Z. Joint orthogonal symmetric non-negative matrix factorization for community detection in attribute network[J]. Knowledge-Based Systems, 2024, 283: 111192.
[47] CHEN Y, MO D X. Community detection for multilayer weighted networks[J]. Information Sciences, 2022, 595: 119-141.
[48] NADERIPOUR M, ZARANDI M H F, BASTANI S. A multilayer general type-2 fuzzy community detection model in large-scale social networks[J]. IEEE Transactions on Fuzzy Systems, 2022, 30(10): 4494-4503.
[49] QING H, WANG J. Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks[J]. Expert Systems with Applications, 2024, 235: 121088.
[50] LI P Z, HUANG L, WANG C D, et al. Community detection by motif-aware label propagation[J]. ACM Transactions on Knowledge Discovery from Data, 2020, 14(2): 1-19.
[51] ROGHANI H, BOUYER A. A fast local balanced label diffusion algorithm for community detection in social networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(6): 5472-5484.
[52] MA X K, ZHANG B H, MA C Z, et al. Co-regularized nonnegative matrix factorization for evolving community detection in dynamic networks[J]. Information Sciences, 2020, 528: 265-279.
[53] MCNEIL M, MATTSSON C, TAKES F W, et al. CADENCE: community-aware detection of dynamic network states[C]//Proceedings of the SIAM International Conference on Data Mining, 2023: 1-9.
[54] SAMIE M E, BEHBOOD E, HAMZEH A. Local community detection based on influence maximization in dynamic networks[J]. Applied Intelligence, 2023, 53(15): 18294-18318.
[55] MáRQUEZ R, WEBER R. Dynamic community detection including node attributes[J]. Expert Systems with Applications, 2023, 223: 119791.
[56] LI H, DU T, WAN X. Time series clustering based on relationship network and community detection[J]. Expert Systems with Applications, 2023, 216: 119481.
[57] ZHUANG D, CHANG J M, LI M C. DynaMo: dynamic community detection by incrementally maximizing modularity[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(5): 1934-1945.
[58] DALL'AMICO L, COUILLET R, TREMBLAY N. Community detection in sparse time-evolving graphs with a dynamical bethe-hessian[C]//Proceedings of the Conference on Neural Information Processing Systems, 2020: 7486-7497.
[59] LI C, GUO X, LIN W, et al. Multiplex network community detection algorithm based on motif awareness[J]. Knowledge-Based Systems, 2023, 260: 110136.
[60] FANI H, JIANG E, BAGHERI E, et al. User community detection via embedding of social network structure and temporal content[J]. Information Processing and Management, 2020, 57(2): 102056.
[61] WU Y, TARDOS J, BATENI M, et al. Streaming belief propagation for community detection[C]//Proceedings of the Conference on Neural Information Processing Systems, 2021: 26976-26988.
[62] ABBOOD A D, ATTEA B A A, HASAN A A, et al. Community detection model for dynamic networks based on hidden Markov model and evolutionary algorithm[J]. Artificial Intelligence Review, 2023, 56(9): 9665-9697.
[63] SHENG J, LIU Q, HOU Z A, et al. A collaborative filtering recommendation algorithm based on community detection and graph neural network[J]. Neural Processing Letters, 2023, 55(6): 7095-7112.
[64] ROSTAMI M, FARRAHI V, AHMADIAN S, et al. A novel healthy and time-aware food recommender system using attributed community detection[J]. Expert Systems with Applications, 2023, 221: 119719.
[65] MOSSIE Z, WANG J H. Vulnerable community identification using hate speech detection on social media[J]. Information Processing and Management, 2020, 57(3): 102087.
[66] WU Y, LIAN D, XU Y, et al. Graph convolutional networks with markov random field reasoning for social spammer detection[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2020: 1054-1061.
[67] DU Y, ZHOU Q, LUO J, et al. Detection of key figures in social networks by combining harmonic modularity with community structure-regulated network embedding[J]. Information Sciences, 2021, 570: 722-743.
[68] LI Z, TANG J, MEI T. Deep collaborative embedding for social image understanding[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019, 41(9): 2070-2083.
[69] LI Z, TANG J, HE X. Robust structured nonnegative matrix factorization for image representation[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(5): 1947-1960.
[70] GUPTA S K, SINGH D P, CHOUDHARY J. A review of clique-based overlapping community detection algorithms[J]. Knowledge and Information Systems, 2022, 64(8): 2023-2058.
[71] 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, 2022, 33(11): 6737-6748.
[72] LU M, ZHANG Z, QU Z, et al. LPANNI: overlapping community detection using label propagation in large-scale complex networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 31(9): 1736-1749.
[73] TENG X, LIU J, LI M. Overlapping community detection in directed and undirected attributed networks using a multiobjective evolutionary algorithm[J]. IEEE Transactions on Cybernetics, 2021, 51(1): 138-150.
[74] TRAN C, SHIN W Y, SPITZ A. Community detection in partially observable social networks[J]. ACM Transactions on Knowledge Discovery from Data, 2022, 16(2): 1-24.
[75] CHEN H R, YU Z J, YANG Q L, et al. Community detection in subspace of attribute[J]. Information Sciences, 2022, 602: 220-235.
[76] JI Y G, SHI C, FANG Y, et al. Semi-supervised co-clustering on attributed heterogeneous information networks[J]. Information Processing and Management, 2020, 57(6): 102338.
[77] ZHENG W, SUN J, ZHANG Q, et al. Continuous encoding for overlapping community detection in attributed network[J]. IEEE Transactions on Cybernetics, 2023, 53(9): 5469-5482.
[78] SU Y, ZHOU K, ZHANG X, et al. A parallel multi-objective evolutionary algorithm for community detection in large-scale complex networks[J]. Information Sciences, 2021, 576: 374-392.
[79] ZHANG X, ZHOU K, PAN H, et al. A network reduction-based multiobjective evolutionary algorithm for community detection in large-scale complex networks[J]. IEEE Transactions on Cybernetics, 2020, 50(2): 703-716.
[80] ZHE C, SUN A X, XIAO X. Community detection on large complex attribute network[C]//Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2019: 2041-2049.