Hypergraph decomposition with intersection bounds

Zhengyi Yang

doi:10.1007/s00778-026-00985-5

2026-06-24

DOI：10.1007/s00778-026-00985-5

原文链接

查看原文

摘要

En 中文

超图分解是超图分析中的一个基本问题，它将超图分解为具有密集交互的凝聚子图和功能单元。超边交叠和重叠捕捉了超图中不同组（超边）之间共享元素（顶点）的独特属性，揭示了仅关注个体连接时并不明显的凝聚子结构。尽管超边重叠作为衡量超图凝聚性的指标具有重要意义，但现有的超图分解模型未能捕捉这一特征。本文研究了带交集约束的超图分解问题。我们提出了（k, s）-核，一种新的凝聚子图模型，同时包含顶点度约束k和超边交集约束s。该模型包括两种类型：（1）强（k, s）-核，其中连接的超边共享至少s个顶点，强制强超边重叠；（2）弱（k, s）-核，其中超边通过s-步连接，允许更宽松的重叠。我们证明了我们定义的（k, s）-核具有唯一性和层次化性质。基于这些性质，我们开发了两种分解算法：一种用于强（k, s）-核的自底向上算法，该算法采用启发式超边移除机制以保持一致的分解结果，并使用并查集数据结构高效识别连通性；以及一种用于弱（k, s）-核的自顶向下算法，该算法保留子图包含关系。我们的算法通过仅处理超图中的每个超边一次来达到遍历效率。此外，所有（k, s）-核可以用最小的内存开销高效存储。全面的实验和案例研究表明，（k, s）-核模型在捕捉超图中具有重叠的凝聚子图方面优于现有方法。此外，所提出的算法表现出高效率和可扩展性，使其非常适合于实际超图。

Keyword:

Hypergraph decomposition

Hyperedge overlap

Cohesive subgraph

Graph theory

AI总结

对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

The VLDB Journal

IF:

论文数:

被引数:

机构

hong kong university of science and technology

学者数:

1.0K

论文数: 468

被引数: 1

Shanghai Jiao Tong University

学者数:

9.9K

论文数: 2.9K

被引数: 0

University of New South Wales

学者数:

1.1K

论文数: 470

被引数: 0

Hong Kong Polytechnic University

学者数:

1.5K

论文数: 757

被引数: 0

Shandong University

学者数:

6.0K

论文数: 1.6K

被引数: 0

查看更多机构

引用论文

I/O efficient ECC graph decomposition via graph reduction

The VLDB Journal

IF0

2016-12-31

PREAI

Long Yuan; Lu Qin; Xuemin Lin; Lijun Chang; Wenjie Zhang

Efficient community discovery with user engagement and similarity

The VLDB Journal

IF0

2019-10-26

PREAI

Fan Zhang; Xuemin Lin; Ying Zhang; Lu Qin; Wenjie Zhang

Efficient indexing and searching of constrained core in hypergraphs 超图中有约束核心的高效索引与搜索

VLDB JOURNAL

IF3.8

2025-04-22

PREAI

Luo, Qi; Zhang, Wenjie; Yu, Dongxiao; Lin, Xuemin; Wang, Liping

Smallest-last ordering and clustering and graph coloring algorithms

Journal of the ACM

IF0

1983-07-01

OAAI

David W. Matula; Leland L. Beck

Hypergraph models of biological networks to identify genes critical to pathogenic viral response

BMC Bioinformatics

IF0

2021-05-29

OAAI

Song Feng; Emily Heath; Brett Jefferson; Cliff Joslyn; Henry Kvinge; Hugh D. Mitchell; Brenda Praggastis; Amie J. Eisfeld; Amy C. Sims; Larissa B. Thackray; Shufang Fan; Kevin B. Walters; Peter J. Halfmann; Danielle Westhoff-Smith; Qing Tan; Vineet D. Menachery; Timothy P. Sheahan; Adam S. Cockrell; Jacob F. Kocher; Kelly G. Stratton; Natalie C. Heller; Lisa M. Bramer; Michael S. Diamond; Ralph S. Baric; Katrina M. Waters; Yoshihiro Kawaoka; Jason E. McDermott; Emilie Purvine

Network structure and minimum degree

Social Networks

IF0

1983-09-01

PREAI

Stephen B. Seidman

Efficiently answering reachability and path queries on temporal bipartite graphs

Proceedings of the VLDB Endowment

IF0

2021-10-26

PREAI

Xiaoshuang Chen; Kai Wang; Xuemin Lin; Wenjie Zhang; Lu Qin; Ying Zhang