Computer Engineering and Applications ›› 2024, Vol. 60 ›› Issue (21): 55-72.DOI: 10.3778/j.issn.1002-8331.2403-0432

• Research Hotspots and Reviews • Previous Articles     Next Articles

Survey of Community Detection from Perspectives of Dynamics and Heterogeneity

WU Yongliang, DOU Shimao, LI Jinghui, DONG Jiahao, WEI Dan   

  1. School of Information Science and Technology, Shijiazhuang Tiedao University, Shijiazhuang 050043, China
  • Online:2024-11-01 Published:2024-10-25

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

武永亮,窦世卯,李景辉,董家浩,魏丹   

  1. 石家庄铁道大学 信息科学与技术学院,石家庄 050043

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

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

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