Efficient indexing and searching of constrained core in hypergraphs
摘要
Hypergraphs are generalized graph models that capture high-order relationships through hyperedges that contain arbitrary vertices. In large-scale hypergraphs, it is common to observe global sparsity and local density, which makes identifying the dense substructures a fundamental task in graph mining. This paper introduces a framework called (k, p)-PoolCore for searching constrained cohesive subgraphs in hypergraphs, with k representing the degree constraint of vertices and p indicating the size constraint of hyperedges. We theoretically analyze the monotonicity and hierarchical properties of (k, p)-PoolCore. To capitalize on these properties, we propose a tree-based PoolCore index that organizes all (k, p)-PoolCores within trees to facilitate efficient queries. Furthermore, we optimize this index to establish a list-based PoolCore index, which offers O(1) query time complexity in most cases without additional space complexity in large-scale hypergraphs. Our extensive experiments and case studies on real-world hypergraphs demonstrate the advantages of (k, p)-PoolCore in hypergraph decomposition and modeling cohesiveness substructures. The proposed tree-based PoolCore index achieves a remarkable