Leveraging Semantic Information for Enhanced Community Search in Heterogeneous Graphs

Abstract

Abstract Community search (CS) is a vital research area in network science that focuses on discovering personalized communities for query vertices from graphs. However, existing CS methods mainly concentrate on homogeneous or simple attributed graphs, often disregarding complex semantic information and rich contents carried by entities in heterogeneous graphs (HGs). In this paper, we propose a novel problem, namely the “Semantic Network Oriented Community Search with Meta-Structures in Heterogeneous Graphs (SNCS),” which aims to find dense communities that contain the query vertex, with vertices of the same type sharing similar topics. In response to this new problem, we present a novel approach, also named SNCS, representing the first solution employing meta-structures and topic constraints to tackle community search, leveraging both topological and latent features. To overcome the high-time complexity challenge posed by searching through meta-structures, we introduce a unique graph reconstruction technique. Our proposed method’s superiority is validated through extensive evaluations on real-world datasets. The results demonstrate a significant improvement in the quality of the obtained communities, with increases of 3.5–4.4% in clustering coefficient and 5–11% in density while requiring only 4–46% of the running time when compared with the state-of-the-art methods.

Keywords

• Heterogeneous graphs
• Community search
• Meta-structures
• Graph reconstruction