Faster context-sensitive dense structure extraction in Heterogeneous Information Networks

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ₚ| nodes and one secondary layer with |Vₛ| nodes. The proposed algorithm extracts CSDSs in O(|Vₚ|³+|Vₚ|²degₘₐₓ²+|Vₛ|³) time when memoization is used with Floyd-Warshall algorithm where degₘₐₓ 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ₚ|³+|Vₚ|²degₘₐₓ²+|Vₛ|²log|Vₛ|+|Vₛ|.|Eₛ|) when memoization is used along with Johnson’s algorithm. All the proposed algorithms are experimentally evaluated to establish their efficiency in practice.