TopologicalGeneralizationsofGraphs:IntegratingHypergraphand SuperHyperGraphPerspectives

圖的拓撲概括:集成超圖和超超圖觀點

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

摘要：

超圖是圖的一種推廣，其中邊——稱為超邊——可以連接任意數(shù)量的頂點，而不僅僅是兩個。SuperHyperGraph通過引入遞歸冪集構(gòu)造進一步擴展了這一框架，使得超邊本身的層次關(guān)系表示成為可能。拓撲圖是嵌入平面中的圖，其中每個頂點由一個不同的點表示，每條邊被繪制為連接其端點的連續(xù)曲線。拓撲超圖通過將超邊表示為平面上包圍頂點集的閉合曲線來擴展這一思想[13]。在本文中，我們引入了拓撲n-超超圖的概念，它將n-超超圖的結(jié)構(gòu)層次與拓撲超圖的幾何直覺統(tǒng)一起來。我們預期這一新公式將有助于圖論、拓撲學和網(wǎng)絡(luò)理論的未來發(fā)展。

關(guān)鍵詞：SuperHyperGraph，超圖，拓撲超圖，拓撲學，拓撲圖，拓撲超超圖。

1. 引言

1.1. 圖、超圖和SuperHyperGraph。圖論研究由頂點和邊構(gòu)成的結(jié)構(gòu)，對各種科學領(lǐng)域中的關(guān)系、網(wǎng)絡(luò)和連接進行建模[19, 35]。網(wǎng)絡(luò)建模最常見的是從簡單圖開始，其中頂點表示對象，邊表示成對連接。為了適應涉及兩個以上元素的交互，超圖允許每條邊連接任意非空頂點子集，從而捕捉高階關(guān)系[10, 20, 21]。在此基礎(chǔ)上，SuperHyperGraph采用重復的冪集運算來表示頂點之間的嵌套、層次鏈接[31, 55, 57]。這種多層方法在最近的研究中引起了越來越多的興趣[32, 47]。

表1總結(jié)了圖、超圖和SuperHyperGraph之間的主要區(qū)別。在這項工作中，n表示非負整數(shù)，除非另有說明。

1.2. 拓撲與圖。 集合上的拓撲是一組子集——稱為開集——的集合，它對任意并集和有限交集封閉 [45]。拓撲圖是繪制在平面上的圖，其中每個頂點是一個獨特的點，每條邊是連接其端點的連續(xù)曲線（若爾當弧）；邊允許相交，但僅限于有限個點處 [43]。該模型對于網(wǎng)絡(luò)理論以及許多可表示為圖的實際系統(tǒng)至關(guān)重要 [18, 39]。特別是，拓撲圖捕捉了直至連續(xù)變形的連通性，支持變形不變推理、魯棒的曲面嵌入、基于同倫的論證，并與拓撲數(shù)據(jù)分析（TDA）兼容——這對傳感器網(wǎng)絡(luò)、機器人技術(shù)、路由、結(jié)構(gòu)分析和抗噪建模非常有用。在人工智能領(lǐng)域，相關(guān)思想構(gòu)成了拓撲圖神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)，這是一個活躍的研究領(lǐng)域 [38, 44, 66]。拓撲超圖通過在平面中將超邊實現(xiàn)為簡單閉曲線（例如，圓）來擴展這一范式；一條超邊精確地包含位于相應閉區(qū)域內(nèi)的頂點 [13]。這種實現(xiàn)方式在幾何上編碼了高階（多元）關(guān)系，并實現(xiàn)了變形不變分析、直觀可視化、同倫論工具以及針對復雜多路交互的曲面感知算法。

1.3. 我們的貢獻。 如上所述，關(guān)于圖論、超圖論、SuperHyperGraph 理論、拓撲圖和拓撲超圖的研究具有重要意義。然而，關(guān)于拓撲 SuperHyperGraph 的研究尚未得到充分發(fā)展。為了彌合這一差距，我們提出了以下貢獻：在本文中，我們引入并形式化了拓撲 SuperHyperGraph 的概念，迄今為止它受到的關(guān)注甚少。我們研究了其數(shù)學結(jié)構(gòu)及其與現(xiàn)有基于圖的框架的關(guān)系。我們希望我們的工作有助于圖論、拓撲圖論、網(wǎng)絡(luò)理論及其各種應用的進步。表 2 總結(jié)了拓撲圖、拓撲超圖和拓撲 SuperHyperGraph 之間的關(guān)鍵區(qū)別。拓撲 SuperHyperGraph 的概念是在本文中新引入并正式定義的。

1.4. 本文結(jié)構(gòu)。 本節(jié)概述了本文的結(jié)構(gòu)。第2節(jié)提供了超圖（Hypergraphs）、超超圖（SuperHyperGraphs）、拓撲圖（Topological Graphs）和拓撲超圖（Topological Hypergraphs）等關(guān)鍵概念的定義。第3節(jié)介紹了拓撲超超圖（Topological SuperHyperGraph）的概念并討論其性質(zhì)。第4節(jié)展示了本文的結(jié)論并概述了未來工作的可能方向。

2. 預備知識

本節(jié)介紹了本文討論所需的基礎(chǔ)概念和定義。關(guān)于圖的基本運算、概念和原理，請參閱 [19, 42]。

2.1. 冪集與 n 次冪集。 一個集合的冪集是所有可能子集的集合，包括空集和集合本身。n 次冪集是通過連續(xù)進行 n 次冪集運算而生成的，從而形成嵌套的子集層。

2.2. 圖與超圖。 在經(jīng)典圖論中，超圖通過允許邊——稱為超邊——連接兩個以上的頂點，從而推廣了標準圖的概念 [19]。這種擴展的結(jié)構(gòu)使得超圖特別適合對元素間的復雜關(guān)系進行建模，從而提高了它們在計算機科學、生物學和網(wǎng)絡(luò)理論等各種領(lǐng)域的適用性 [8, 9, 21, 34]。在下文中，我們將提供超圖的精確定義。在整篇論文中，我們將關(guān)注點限制在有限、無向、簡單圖上。

定義 2.8 (超圖)。 [10,12] 一個超圖 H = ( V ( H ) , E ( H ) )) 由以下部分組成：

• 一個非空的頂點集合 V ( H ) 。
• 一個超邊集合 E ( H ) ，其中每條超邊都是 V ( H ) 的一個非空子集，從而允許多個頂點之間的連接。

與標準圖不同，超圖非常適合表示高階關(guān)系。在本文中，我們僅限于 V ( H )
和 E ( H )
均為有限的情況。

那么， H = ( V ( H ) , E ( H ) 是一個有限超圖，其中每條超邊記錄一次多項商品聯(lián)合購買。與標準圖（僅捕捉成對共現(xiàn)）不同，該超圖直接表示了單個購物籃中幾種產(chǎn)品之間的高階購買關(guān)系。

2.3. 超超圖。 超超圖（SuperHyperGraph）是經(jīng)典超圖的高階推廣，是通過允許頂點本身存在于迭代冪集層級上而獲得的。該框架已在最近的作品 [15,22,31,32,57] 中得到發(fā)展和研究。近年來，超超圖因在決策 [36,37]、圖神經(jīng)網(wǎng)絡(luò) (GNNs) [26,30,33]、醫(yī)學 [29]、化學 [24,28]、量子理論 [27]、能源系統(tǒng) [23]、城市養(yǎng)老 [14]、媒體融合 [69]、商業(yè) [11,63]、工程 [25] 及其他領(lǐng)域 [16,50,64] 的潛在應用而引起了越來越多的興趣。 n n-超超圖的定義和具體示例如下所示。

2.4. 拓撲圖與拓撲超圖。 我們使用以下定義來描述拓撲圖和拓撲超圖。拓撲圖是圖的一種平面描繪，其中頂點是不同的點，邊是連續(xù)曲線 [2,17,43,49,61]。拓撲超圖通過在平面中使用簡單閉曲線（如圓）來定義超邊，從而擴展了這一思想。每條超邊由被其中一條曲線所包圍的頂點組成 [7,13]。

3. 本文的主要結(jié)果

作為本文的主要貢獻，我們定義了拓撲 n -超超圖的概念，并研究了它們的結(jié)構(gòu)性質(zhì)。

3.1. 拓撲 n-超超圖。在本小節(jié)中，我們考察拓撲 n-超超圖的基本特征和數(shù)學特性。拓撲 n-超超圖將迭代冪集的頂點和邊與拓撲實現(xiàn)相結(jié)合，對層次幾何關(guān)系進行建模。

4. 結(jié)論與未來工作

在本文中，我們引入了拓撲 n-超超圖的概念，它將 n-超超圖的結(jié)構(gòu)層次與拓撲超圖的幾何直覺統(tǒng)一起來。

作為未來工作，我們旨在探索其在網(wǎng)絡(luò)分析中的潛在應用，并考慮使用先進的不確定性處理框架進行擴展，例如模糊集 [46,68]、直覺模糊集 [5,6]、中智集 [3,52,65]、猶豫模糊集 [62,67] 和 Plithogenic 集 [53,60]。此外，我們期望在基于拓撲 n-超超圖的編程工具創(chuàng)建、其數(shù)學結(jié)構(gòu)的深入研究，以及定量分析和應用案例研究的進展方面取得進一步發(fā)展。

原文鏈接：https://www.researchgate.net/publication/396508324_Topological_Generalizations_of_Graphs_Integrating_Hypergraph_and_SuperHyperGraph_Perspectives