Density Decomposition on Hypergraphs
This work addresses hypergraph analysis for applications like community detection and task scheduling, offering a novel method for density-based decomposition.
The paper tackles the problem of hypergraph decomposition by proposing a novel (k,δ)-dense subhypergraph model to address limitations of existing methods that rely on vertex degree constraints, resulting in more continuous and less redundant decomposition hierarchies with improved computational efficiency, as demonstrated on nine real-world datasets.
Decomposing hypergraphs is a key task in hypergraph analysis with broad applications in community detection, pattern discovery, and task scheduling. Existing approaches such as $k$-core and neighbor-$k$-core rely on vertex degree constraints, which often fail to capture true density variations induced by multi-way interactions and may lead to sparse or uneven decomposition layers. To address these issues, we propose a novel \((k,δ)\)-dense subhypergraph model for decomposing hypergraphs based on integer density values. Here, $k$ represents the density level of a subhypergraph, while \(δ\) sets the upper limit for each hyperedge's contribution to density, allowing fine-grained control over density distribution across layers. Computing such dense subhypergraphs is algorithmically challenging, as it requires identifying an egalitarian orientation under bounded hyperedge contributions, which may incur an intuitive worst-case complexity of up to $O(2^{mδ})$. To enable efficient computation, we develop a fair-stable-based algorithm that reduces the complexity of mining a single $(k,δ)$-dense subhypergraph from $O(m^{2}δ^{2})$ to $O(nmδ)$. Building on this result, we further design a divide-and-conquer decomposition framework that improves the overall complexity of full density decomposition from $O(nmδ\cdot d^E_{\max} \cdot k_{\max})$ to $O(nmδ\cdot d^E_{\max} \cdot \log k_{\max})$. Experiments on nine real-world hypergraph datasets demonstrate that our approach produces more continuous and less redundant decomposition hierarchies than existing baselines, while maintaining strong computational efficiency. Case studies further illustrate the practical utility of our model by uncovering cohesive and interpretable community structures.