Faster context-sensitive dense structure extraction in Heterogeneous Information Networks
Journal of Complex Networks · 10.03.2026 · 14 (2)
DOI: 10.1093/comnet/cnag002 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Complex Networks, online erschienen am 18.03.2026. Verfasst von Ajaharul Hoque und 3 weiteren Autor:innen. Die Arbeit nennt 40 Literaturangaben. Gefördert von: Faculty Research Scheme.
Abstract (Originalsprache)
Heterogeneous Information Networks (HIN) are introduced to model and analyze various real-world networks with interactions between multiple types of entities such as social networks, citation networks, the World Wide Web, etc. Extraction of dense subgraphs from a given HIN plays an important role in extracting information-rich substructures that can be used to address fundamental problems like topic detection, community detection, etc. A HIN consists of multiple layers of graphs where nodes in each layer represent similar types of entities, edges represent the interaction between them, and inter-layer edges represent the interaction between different types of entities. This article presents faster algorithms to extract context-sensitive dense structures (CSDS) from a given HIN, which serve as an alternative to dense subgraphs in the same network. A memoization based approach is used along with other techniques to design algorithms to extract CSDS from HINs with one primary layer with $ |V_{p}| $ nodes and one secondary layer with $ |V_{s}| $ nodes. The proposed algorithm extracts CSDSs in $ O(|V_{p}|^{3}+|V_{p}|^{2}deg_{max}^{2}+|V_{s}|^{3}) $ time when memoization is used with Floyd-Warshall algorithm where $ deg_{max} $ is the maximum number of inter-layer edges incident on any node in the primary layer. The time complexity of the proposed algorithm is $ O(|V_{p}|^{3}+|V_{p}|^{2}deg_{max}^{2}+|V_{s}|^{2}\log|V_{s}|+|V_{s}|.|E_{s}|) $ when memoization is used along with Johnson’s algorithm. All the proposed algorithms are experimentally evaluated to establish their efficiency in practice.
Förderung
- Faculty Research Scheme
Zitieren
APA
Hoque, A., Barman, D., Mandal, S., & Dutta, P. (2026). Faster context-sensitive dense structure extraction in Heterogeneous Information Networks. Journal of Complex Networks, 14(2). https://doi.org/10.1093/comnet/cnag002
Vancouver
Hoque A, Barman D, Mandal S, Dutta P. Faster context-sensitive dense structure extraction in Heterogeneous Information Networks. Journal of Complex Networks. 2026;14(2). doi:10.1093/comnet/cnag002
BibTeX
@article{Hoque2026,
author = {Hoque, Ajaharul and Barman, Debaditya and Mandal, Subhrangsu and Dutta, Paramartha},
title = {Faster context-sensitive dense structure extraction in Heterogeneous Information Networks},
journal = {Journal of Complex Networks},
year = {2026},
volume = {14},
number = {2},
doi = {10.1093/comnet/cnag002}
}
EUVIMED