Beyond Trivial Edges: A Fractional Approach to Cohesive Subgraph Detection in Hypergraphs

Abstract

Hypergraphs serve as a powerful tool for modeling complex relationships across domains like social networks, transactions, and recommendation systems. The (k,g)-core model effectively identifies cohesive subgraphs by assessing internal connections and co-occurrence patterns, but it is susceptible to inflated cohesiveness due to trivial hyperedges. To address this, we propose the $(k,g,p)$-core model, which incorporates the relative importance of hyperedges for more accurate subgraph detection. We develop both Naïve and Advanced pruning algorithms, demonstrating through extensive experiments that our approach reduces the execution frequency of costly operations by 51.9% on real-world datasets.

References in corpus (6)

• What are higher-order networks?
• Higher-order motif analysis in hypergraphs
• Hypergraph reconstruction from network data
• An empirical analysis of smart contracts: platforms, applications, and design patterns
• Hypercore Decomposition for Non-Fragile Hyperedges: Concepts, Algorithms, Observations, and Applications
• Experimental Analysis and Evaluation of Cohesive Subgraph Discovery