Complex Relational Community Search in Heterogeneous Information Networks

Abstract

Community search in heterogeneous information networks (HINs) is a fundamental task in graph management and analysis. Existing relational community search models, which rely on simple connection requirements between vertices, often fall short of capturing users’ complex needs. To address this limitation, we introduce the concept of <italic>complex relational constraints based on meta-paths</italic>. These constraints enable users to specify refined connection requirements by limiting the number of meta-paths between vertex pairs, thereby capturing higher-order semantic relationships. Based on this, we formally define the complex relational community and formulate the problem of <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math></inline-formula>inimum <inline-formula> <tex-math notation="LaTeX">$C$ </tex-math></inline-formula>omplex <inline-formula> <tex-math notation="LaTeX">$R$ </tex-math></inline-formula>elational <inline-formula> <tex-math notation="LaTeX">$C$ </tex-math></inline-formula>ommunity <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula>earch (<italic>MCRCS</italic>), which identifies the minimal such community containing a given query vertex, and prove its NP-hardness. To solve the MCRCS problem, we propose both exact and approximate algorithms. We first develop two exact algorithms: a global vertex-removal method (<italic>Global</italic>) and a local search method (<italic>Ls</italic>). Given the problem’s complexity, we then introduce two efficient approximation algorithms, <italic>Greedy</italic> and <italic>LsApp</italic>, which employ vertex prioritization strategies to find high-quality communities with significantly reduced computational cost. Comprehensive experiments on four real-world HIN datasets demonstrate the effectiveness and efficiency of our proposed algorithms.