Scholarlink

<p>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 (<i>k</i>,&#xa0;<i>s</i>)-core, a new cohesive subgraph model incorporating both a vertex degree constraint <i>k</i> and a hyperedge intersection constraint <i>s</i>. This model includes two types: (1) strong (<i>k</i>,&#xa0;<i>s</i>)-cores, where connected hyperedges share at least <i>s</i> vertices, enforcing strong hyperedge overlap, and (2) weak (<i>k</i>,&#xa0;<i>s</i>)-cores, where hyperedges are connected through <i>s</i>-walks, allowing for a looser overlap. We prove that our definition of (<i>k</i>,&#xa0;<i>s</i>)-cores exhibits uniqueness and hierarchical properties. Based on the properties, we develop two decomposition algorithms: a bottom-up algorithm for strong (<i>k</i>,&#xa0;<i>s</i>)-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 (<i>k</i>,&#xa0;<i>s</i>)-cores that preserves the subgraph containment relationship. Our algorithms achieve traversal efficiency by processing each hyperedge in the hypergraph only once. Additionally, all (<i>k</i>,&#xa0;<i>s</i>)-cores can be efficiently stored with minimal memory overhead. Comprehensive experiments and case studies show that the (<i>k</i>,&#xa0;<i>s</i>)-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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Hypergraph decomposition with intersection bounds

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年6月24日

查看全文
  • Qi Luo,
  • Zhengyi Yang,
  • Wenjie Zhang,
  • Alexander Zhou,
  • Dongxiao Yu,
  • Xiuzhen Cheng,
  • Xuemin Lin,
  • Song Guo

摘要

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.