TopologicalGeneralizationsofGraphs:IntegratingHypergraphand SuperHyperGraphPerspectives

圖的拓?fù)涓爬?集成超圖和超超圖觀點(diǎn)

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

摘要：

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

關(guān)鍵詞：SuperHyperGraph，超圖，拓?fù)涑瑘D，拓?fù)鋵W(xué)，拓?fù)鋱D，拓?fù)涑瑘D。

1. 引言

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

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

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

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

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

2. 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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