Complex Relational Community Search in Heterogeneous Information Networks
IEEE Transactions on Networking · 2026 · 34 · 6580-6594
DOI: 10.1109/ton.2026.3718688 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Networking, 2026. Verfasst von Chuanyu Zong und 4 weiteren Autor:innen. Die Arbeit nennt 41 Literaturangaben. Gefördert von: Key Research and Development Program of Liaoning, NSF of Liaoning, Liaoning Province Xingliao Talent Program.
Abstract (Originalsprache)
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 complex relational constraints based on meta-paths . 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 $M$ inimum $C$ omplex $R$ elational $C$ ommunity $S$ earch ( MCRCS ), 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 ( Global ) and a local search method ( Ls ). Given the problem’s complexity, we then introduce two efficient approximation algorithms, Greedy and LsApp , 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.
Förderung
- Key Research and Development Program of Liaoning
- NSF of Liaoning
- Liaoning Province Xingliao Talent Program
- National Natural Science Foundation of China
- Liaoning Provincial Science and Technology Program-General Program
- Foundation of Liaoning Provincial Department of Education
Zitieren
APA
Zong, C., Cai, Z., Qiu, T., Zhang, A., & Zhu, R. (2026). Complex Relational Community Search in Heterogeneous Information Networks. IEEE Transactions on Networking, 34, 6580-6594. https://doi.org/10.1109/ton.2026.3718688
Vancouver
Zong C, Cai Z, Qiu T, Zhang A, Zhu R. Complex Relational Community Search in Heterogeneous Information Networks. IEEE Transactions on Networking. 2026;34:6580-6594. doi:10.1109/ton.2026.3718688
BibTeX
@article{Zong2026,
author = {Zong, Chuanyu and Cai, Ziyi and Qiu, Tao and Zhang, Anzhen and Zhu, Rui},
title = {Complex Relational Community Search in Heterogeneous Information Networks},
journal = {IEEE Transactions on Networking},
year = {2026},
volume = {34},
pages = {6580--6594},
doi = {10.1109/ton.2026.3718688}
}
EUVIMED