HyperGraph and SuperHyperGraph Theorywith Applications I

超圖與超超圖理論及其應(yīng)用 基礎(chǔ)、定義與理論模型

https://fs.unm.edu/HyperGraphSuperHyperGraphTheory1.pdf

摘要

超圖通過(guò)允許連接兩個(gè)以上頂點(diǎn)的超邊，推廣了這一框架 [1]。超超圖（Superhypergraphs）通過(guò)迭代冪集構(gòu)造進(jìn)一步豐富了該模型，捕捉了超邊之間的層級(jí)和自指結(jié)構(gòu) [2]。一個(gè) ( m , n )
-超超圖（SuperHyperGraph）是一種數(shù)學(xué)結(jié)構(gòu)，其中每個(gè)頂點(diǎn)對(duì)應(yīng)于定義在基集上的一個(gè) ( m , n )
-超超函數(shù)（superhyperfunction），而超邊將這些函數(shù)組合在一起，以表示高階關(guān)系和上下文連接。與關(guān)于圖和超圖的廣泛文獻(xiàn)相比，關(guān)于超超圖的系統(tǒng)研究仍然相對(duì)有限。

為了幫助彌合這一差距，本書(shū)對(duì)與超超圖相關(guān)的基礎(chǔ)和高級(jí)概念進(jìn)行了綜述。我們的目標(biāo)有兩個(gè)：(i) 提高超超圖理論的可見(jiàn)性和可及性，從而刺激進(jìn)一步的研究；以及 (ii) 加深從事基于圖和超圖模型的研究人員和從業(yè)者對(duì)其結(jié)構(gòu)的數(shù)學(xué)理解。

關(guān)鍵詞 超超圖理論，超圖理論， ( m , n )
-超超圖理論，不確定圖理論，圖的應(yīng)用

第 1 章 引言

1.1 圖、超圖與超超圖

網(wǎng)絡(luò)建模通常依賴(lài)于圖，其中實(shí)體由頂點(diǎn)表示，二元關(guān)系由邊表示 [3]。然而，經(jīng)典圖可能不足以描述三個(gè)或更多實(shí)體同時(shí)相互作用的復(fù)雜網(wǎng)絡(luò)。超圖通過(guò)允許每條超邊連接頂點(diǎn)的任意非空子集來(lái)解決這一限制，從而捕捉高階交互 [4]。盡管具有表達(dá)能力，超圖在表示許多現(xiàn)實(shí)世界系統(tǒng)中出現(xiàn)的分層、嵌套和固有的層級(jí)關(guān)系方面可能仍然不足。為了彌合這一差距，F(xiàn). Smarandache 引入了超超圖（SuperHyperGraph）的概念。超超圖采用基于迭代冪集的構(gòu)造來(lái)編碼嵌套連接模式和多層級(jí)關(guān)系 [2,5]，并且最近引起了大量關(guān)注 [6, 7]。

圖和超圖為復(fù)雜系統(tǒng)提供了直觀的視覺(jué)隱喻，并支持人工智能、網(wǎng)絡(luò)科學(xué)、數(shù)據(jù)挖掘、信息學(xué)、化學(xué)、物理等領(lǐng)域的廣泛應(yīng)用 [8–11]。通過(guò)明確容納層級(jí)和多層級(jí)關(guān)系，超超圖為建模和分析現(xiàn)代網(wǎng)絡(luò)數(shù)據(jù)中遇到的復(fù)雜結(jié)構(gòu)提供了一個(gè)穩(wěn)健的框架（例如 [12–14, 14–16]）。

表 1.1 總結(jié)了圖、超圖和超超圖之間的關(guān)鍵區(qū)別。在本書(shū)中，除非另有說(shuō)明， 被視為自然數(shù)。

使用超超圖的優(yōu)勢(shì)包括幾個(gè)眾所周知的好處，例如：

• 通過(guò)迭代冪集自然地建模層次結(jié)構(gòu)。
• 在統(tǒng)一框架內(nèi)表示多路、多層次關(guān)系。
• 包含圖 [3]、多重圖 [18,19]、子集頂點(diǎn)圖 [20-22]、超圖 [17]、超圖 [23]、h-模型 [24]、擬超超圖 [5]、冪集圖 [25]、k-鏈自由集 [26]、Johnson 圖 [27]、Kneser 圖 [28] 以及多超圖 [29] 作為特殊（扁平化）實(shí)例。
• 在每一層支持豐富的屬性系統(tǒng)（模糊、直覺(jué)模糊、中智、plithogenic [2]）。
• 為真實(shí)的層次系統(tǒng)（如課程或供應(yīng)鏈網(wǎng)絡(luò)）提供更好的適配。

1.2 圖、超圖和超超圖的應(yīng)用

圖、超圖和超超圖結(jié)構(gòu)已在廣泛的應(yīng)用領(lǐng)域中得到研究。代表性示例總結(jié)在表 1.2 和 1.3 中。需要注意的是，關(guān)于超超圖的研究仍處于早期階段，在撰寫(xiě)本文時(shí)，大多數(shù)現(xiàn)有工作仍停留在理論層面。因此，未來(lái)的研究預(yù)計(jì)將包括更多由計(jì)算實(shí)驗(yàn)、機(jī)器學(xué)習(xí)技術(shù)支持的實(shí)用性研究，以及由領(lǐng)域?qū)＜疫M(jìn)行的詳細(xì)案例研究。

1.3 我們的貢獻(xiàn)

從上述討論可以清楚地看出，超超圖對(duì)于建模層級(jí)結(jié)構(gòu)和多路結(jié)構(gòu)具有極其重要的意義。然而，與關(guān)于圖和超圖的廣泛文獻(xiàn)相比，關(guān)于超超圖的系統(tǒng)研究仍然相對(duì)有限。

為了幫助彌合這一差距，本書(shū)對(duì)與超超圖相關(guān)的基礎(chǔ)概念和高級(jí)概念進(jìn)行了綜述。我們的目標(biāo)有兩個(gè)：(i) 提高超超圖理論的可見(jiàn)性和可及性，從而激發(fā)進(jìn)一步的研究；以及 (ii) 加深從事基于圖和超圖模型的研究人員與從業(yè)者對(duì)這些結(jié)構(gòu)的數(shù)學(xué)理解。

本書(shū)主要聚焦于理論發(fā)展。我們誠(chéng)摯希望，相關(guān)領(lǐng)域的專(zhuān)家能夠進(jìn)一步開(kāi)展計(jì)算實(shí)驗(yàn)和現(xiàn)實(shí)世界的案例研究。

原文鏈接： https://fs.unm.edu/HyperGraphSuperHyperGraphTheory1.pdf