《计算机应用》唯一官方网站

• •    下一篇

超图应用方法综述:问题、进展与挑战

曾蠡1,杨婧如2,黄罡3,景翔1,罗超然2   

  1. 1. 北京大学软件与微电子学院
    2. 数据空间技术与系统全国重点实验室
    3. 北京大学软件研究所
  • 收稿日期:2023-12-01 接受日期:2024-01-01 发布日期:2024-01-04 出版日期:2024-01-04
  • 通讯作者: 罗超然
  • 基金资助:
    国家重点基础研究发展计划;北京高等学校卓越青年科学家项目

Survey on Hypergraph Application Methods: Research Problem, Progress, and Challenges

  • Received:2023-12-01 Accepted:2024-01-01 Online:2024-01-04 Published:2024-01-04

摘要: 超图是图的泛化。相较于普通图,超图在复杂关系的高阶特征表达上具有显著优势。作为一种相对较新的数据结构,超图在应用领域正在发挥越来越大的作用,研究者采用超图模型及算法对现实世界中的具体问题进行建模、求解,有效地提升了解决问题的效率及质量。现有对超图的综述更多侧重于解决超图本身问题的理论及技术,缺乏对超图在具体应用场景下的建模及求解方法的归纳、总结。本文首先对超图的一些基础概念进行了介绍,在此基础上分析了超图在各个主流应用场景下的应用方法、技术、共性问题及解决方案;进一步的,通过对现有工作的归纳、总结提出了超图运用于现实问题中仍然存在的一些问题与障碍;最后,对超图应用的未来研究方向进行了展望。

关键词: 超图应用, 图像处理, 网络分析, 推荐系统, 分布式网络

Abstract: A hypergraph is the generalization of a graph. In comparison to regular graphs, hypergraphs offer significant advantages in representing high-order features of complex relationships. As a new data structure, hypergraph is increasingly playing a crucial role in various application domains. By appropriately using hypergraphs, researchers model and solve real-world problems with higher effectiveness and efficiency. However, existing surveys of hypergraphs mainly focus on the theory and techniques of hypergraphs itself, lacking a comprehensive study about how to apply hypergraphs to real-world problems in specific scenarios. In this paper, we first introduce the fundamental concepts of hypergraphs, and then we analyze the application methods, techniques, common issues, and solutions of hypergraphs in various application scenarios. Furthermore, we propose the remaining problems in hypergraph applications and point out the directions in hypergraph application research.

Key words: hypergraph application, image processing, network analysis, recommender system, distributed network

中图分类号: