Cohesive subgraph discovery in hypergraphs is essential for analysing complex group interactions in various domains such as e-commerce, social media, and collaboration networks. However, existing models are vulnerable to large hyperedges that artificially inflate connectivity, obscuring meaningful structure. We propose the (k,s)-core, a new model requiring each node to have at least k neighbours with a minimum interaction strength s, measured via a size-sensitive decay function. This penalises noisy co-occurrences while preserving strong local patterns. We develop an efficient algorithm with theoretical guarantees, and experiments on real-world datasets demonstrate improved compactness and robustness over prior methods.

Community search in heterogeneous graphs is fundamental to applications such as expert team formation and scholarly collaboration. Many existing studies leverage meta-paths, which are sequences of node and edge types, to capture semantic relationships in heterogeneous graphs. However, most of them only consider the existence of meta-path instances, overlooking their frequency and thus failing to capture relationship strength. This limitation can result in communities that include nodes with numerous but weak relations. To capture the strength of relationships in heterogeneous graphs, we define the Strong Community (StrCom) model, which evaluates the strength between users based on the number of connecting meta-path instances. Building upon this model, we further propose the Budgeted Strong Community (BSC) problem by incorporating a size constraint. We provide theoretical analyses showing that the BSC problem is NP-hard and not in APX. To address this problem, we design three strategies-Shrink, Expand, and Hybrid-along with several optimization techniques to improve efficiency. Extensive experiments on large real-world datasets (e.g., DBLP, YAGO, DBpedia) demonstrate the effectiveness and efficiency of our approach. Specifically, our method achieves 3.49-107.09× higher PathSim scores for StrCom and two to five orders of magnitude higher scores for BSC compared to state-of-the-art baselines, demonstrating that the identified communities are both semantically coherent and structurally compact.

Identifying cohesive subgraphs in hypergraphs is a fundamental problem that has received recent attention in data mining and engineering fields. Existing approaches mainly focus on a strongly induced subhypergraph or edge cardinality, overlooking the importance of the frequency of co-occurrence. In this paper, we propose a new cohesive subgraph named (k,g)-core, which considers both neighbour and co-occurrence simultaneously. The (k,g)-core has various applications including recommendation system, network analysis, and fraud detection. To the best of our knowledge, this is the first work to combine these factors. We extend an existing efficient algorithm to find solutions for (k,g)-core. Finally, we conduct extensive experimental studies that demonstrate the efficiency and effectiveness of our proposed algorithm.