.png){kind=icon}
.png){kind=icon}
Return
Hypergraph decomposition with intersection bounds
.png){kind=icon}
OA
AI
DOI：10.1007/s00778-026-00985-5.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Hypergraph decomposition is a fundamental problem in hypergraph analysis which breaks down hypergraphs into cohesive subgraphs and functional units with dense interactions. Hyperedge intersections and overlaps capture the unique property of shared elements (vertices) between groups (hyperedges) in hypergraphs, revealing cohesive substructures not apparent when focusing solely on individual connections. Despite the significance of hyperedge overlap as a measure of hypergraph cohesiveness, existing models for hypergraph decomposition fail to capture this feature. In this paper, we study the problem of hypergraph decomposition with intersection bounds. We propose the (k, s)-core, a new cohesive subgraph model incorporating both a vertex degree constraint k and a hyperedge intersection constraint s. This model includes two types: (1) strong (k, s)-cores, where connected hyperedges share at least s vertices, enforcing strong hyperedge overlap, and (2) weak (k, s)-cores, where hyperedges are connected through s-walks, allowing for a looser overlap. We prove that our definition of (k, s)-cores exhibits uniqueness and hierarchical properties. Based on the properties, we develop two decomposition algorithms: a bottom-up algorithm for strong (k, s)-cores, which uses a heuristic hyperedge removal mechanism to maintain consistent decomposition results and employs a union-find data structure for efficient connectivity identification, and a top-down algorithm for weak (k, s)-cores that preserves the subgraph containment relationship. Our algorithms achieve traversal efficiency by processing each hyperedge in the hypergraph only once. Additionally, all (k, s)-cores can be efficiently stored with minimal memory overhead. Comprehensive experiments and case studies show that the (k, s)-core model outperforms existing methods in capturing cohesive subgraphs with overlaps in hypergraphs. Furthermore, the proposed algorithms demonstrate high efficiency and scalability, making them well-suited for real-world hypergraphs.
Keywords:
Hypergraph decomposition
Hyperedge overlap
Cohesive subgraph
Graph theory
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
T
IF:
0
Papers:
36
Citations:
0
View more organizations