图拓扑:超图超超图

TopologicalGeneralizationsofGraphs:IntegratingHypergraphand SuperHyperGraphPerspectives

图的拓扑概括:集成超图和超超图观点

https://www.researchgate.net/publication/396508324_Topological_Generalizations_of_Graphs_Integrating_Hypergraph_and_SuperHyperGraph_Perspectives

摘要：

超图是图的一种推广，其中边——称为超边——可以连接任意数量的顶点，而不仅仅是两个。SuperHyperGraph通过引入递归幂集构造进一步扩展了这一框架，使得超边本身的层次关系表示成为可能。拓扑图是嵌入平面中的图，其中每个顶点由一个不同的点表示，每条边被绘制为连接其端点的连续曲线。拓扑超图通过将超边表示为平面上包围顶点集的闭合曲线来扩展这一思想[13]。在本文中，我们引入了拓扑n-超超图的概念，它将n-超超图的结构层次与拓扑超图的几何直觉统一起来。我们预期这一新公式将有助于图论、拓扑学和网络理论的未来发展。

关键词：SuperHyperGraph，超图，拓扑超图，拓扑学，拓扑图，拓扑超超图。

1. 引言

1.1. 图、超图和SuperHyperGraph。图论研究由顶点和边构成的结构，对各种科学领域中的关系、网络和连接进行建模[19, 35]。网络建模最常见的是从简单图开始，其中顶点表示对象，边表示成对连接。为了适应涉及两个以上元素的交互，超图允许每条边连接任意非空顶点子集，从而捕捉高阶关系[10, 20, 21]。在此基础上，SuperHyperGraph采用重复的幂集运算来表示顶点之间的嵌套、层次链接[31, 55, 57]。这种多层方法在最近的研究中引起了越来越多的兴趣[32, 47]。

表1总结了图、超图和SuperHyperGraph之间的主要区别。在这项工作中，n表示非负整数，除非另有说明。

1.2. 拓扑与图。 集合上的拓扑是一组子集——称为开集——的集合，它对任意并集和有限交集封闭 [45]。拓扑图是绘制在平面上的图，其中每个顶点是一个独特的点，每条边是连接其端点的连续曲线（若尔当弧）；边允许相交，但仅限于有限个点处 [43]。该模型对于网络理论以及许多可表示为图的实际系统至关重要 [18, 39]。特别是，拓扑图捕捉了直至连续变形的连通性，支持变形不变推理、鲁棒的曲面嵌入、基于同伦的论证，并与拓扑数据分析（TDA）兼容——这对传感器网络、机器人技术、路由、结构分析和抗噪建模非常有用。在人工智能领域，相关思想构成了拓扑图神经网络的基础，这是一个活跃的研究领域 [38, 44, 66]。拓扑超图通过在平面中将超边实现为简单闭曲线（例如，圆）来扩展这一范式；一条超边精确地包含位于相应闭区域内的顶点 [13]。这种实现方式在几何上编码了高阶（多元）关系，并实现了变形不变分析、直观可视化、同伦论工具以及针对复杂多路交互的曲面感知算法。

1.3. 我们的贡献。 如上所述，关于图论、超图论、SuperHyperGraph 理论、拓扑图和拓扑超图的研究具有重要意义。然而，关于拓扑 SuperHyperGraph 的研究尚未得到充分发展。为了弥合这一差距，我们提出了以下贡献：在本文中，我们引入并形式化了拓扑 SuperHyperGraph 的概念，迄今为止它受到的关注甚少。我们研究了其数学结构及其与现有基于图的框架的关系。我们希望我们的工作有助于图论、拓扑图论、网络理论及其各种应用的进步。表 2 总结了拓扑图、拓扑超图和拓扑 SuperHyperGraph 之间的关键区别。拓扑 SuperHyperGraph 的概念是在本文中新引入并正式定义的。

1.4. 本文结构。 本节概述了本文的结构。第2节提供了超图（Hypergraphs）、超超图（SuperHyperGraphs）、拓扑图（Topological Graphs）和拓扑超图（Topological Hypergraphs）等关键概念的定义。第3节介绍了拓扑超超图（Topological SuperHyperGraph）的概念并讨论其性质。第4节展示了本文的结论并概述了未来工作的可能方向。

2. 预备知识

本节介绍了本文讨论所需的基础概念和定义。关于图的基本运算、概念和原理，请参阅 [19, 42]。

2.1. 幂集与 n 次幂集。 一个集合的幂集是所有可能子集的集合，包括空集和集合本身。n 次幂集是通过连续进行 n 次幂集运算而生成的，从而形成嵌套的子集层。

2.2. 图与超图。 在经典图论中，超图通过允许边——称为超边——连接两个以上的顶点，从而推广了标准图的概念 [19]。这种扩展的结构使得超图特别适合对元素间的复杂关系进行建模，从而提高了它们在计算机科学、生物学和网络理论等各种领域的适用性 [8, 9, 21, 34]。在下文中，我们将提供超图的精确定义。在整篇论文中，我们将关注点限制在有限、无向、简单图上。

定义 2.8 (超图)。 [10,12] 一个超图 H=(V(H),E(H))) 由以下部分组成：

• 一个非空的顶点集合 V(H) 。
• 一个超边集合 E(H) ，其中每条超边都是 V(H) 的一个非空子集，从而允许多个顶点之间的连接。

与标准图不同，超图非常适合表示高阶关系。在本文中，我们仅限于 V(H) 和 E(H) 均为有限的情况。

那么，H=(V(H),E(H)是一个有限超图，其中每条超边记录一次多项商品联合购买。与标准图（仅捕捉成对共现）不同，该超图直接表示了单个购物篮中几种产品之间的高阶购买关系。

2.3. 超超图。 超超图（SuperHyperGraph）是经典超图的高阶推广，是通过允许顶点本身存在于迭代幂集层级上而获得的。该框架已在最近的作品 [15,22,31,32,57] 中得到发展和研究。近年来，超超图因在决策 [36,37]、图神经网络 (GNNs) [26,30,33]、医学 [29]、化学 [24,28]、量子理论 [27]、能源系统 [23]、城市养老 [14]、媒体融合 [69]、商业 [11,63]、工程 [25] 及其他领域 [16,50,64] 的潜在应用而引起了越来越多的兴趣。nn-超超图的定义和具体示例如下所示。

2.4. 拓扑图与拓扑超图。 我们使用以下定义来描述拓扑图和拓扑超图。拓扑图是图的一种平面描绘，其中顶点是不同的点，边是连续曲线 [2,17,43,49,61]。拓扑超图通过在平面中使用简单闭曲线（如圆）来定义超边，从而扩展了这一思想。每条超边由被其中一条曲线所包围的顶点组成 [7,13]。

3. 本文的主要结果

作为本文的主要贡献，我们定义了拓扑 n-超超图的概念，并研究了它们的结构性质。

3.1. 拓扑 n-超超图。在本小节中，我们考察拓扑 n-超超图的基本特征和数学特性。拓扑 n-超超图将迭代幂集的顶点和边与拓扑实现相结合，对层次几何关系进行建模。

4. 结论与未来工作

在本文中，我们引入了拓扑 n-超超图的概念，它将 n-超超图的结构层次与拓扑超图的几何直觉统一起来。

作为未来工作，我们旨在探索其在网络分析中的潜在应用，并考虑使用先进的不确定性处理框架进行扩展，例如模糊集 [46,68]、直觉模糊集 [5,6]、中智集 [3,52,65]、犹豫模糊集 [62,67] 和 Plithogenic 集 [53,60]。此外，我们期望在基于拓扑 n-超超图的编程工具创建、其数学结构的深入研究，以及定量分析和应用案例研究的进展方面取得进一步发展。