張量超超圖和張量迭代線圖
Tensor SuperHyperGraph and Tensor Iterated Line Graph
https://www.techrxiv.org/users/868224/articles/1374006-tensor-superhypergraph-and-tensor-iterated-line-graph
![]()
![]()
摘要
超圖通過允許每條邊連接頂點集的任意非空子集,擴展了普通圖。通過將冪集構造再迭代一層,人們獲得嵌套(高階)頂點對象,從而得到有限超超圖,其頂點和邊本身可以是跨多層的集合值對象。線圖是一種變換,它將圖的每條邊替換為一個頂點,當且僅當原始圖中對應的邊共享一個公共端點時,連接兩個這樣的頂點。張量圖可以被視為一個多重網絡:公共頂點集上的圖的 r 元組,通過將其鄰接矩陣堆疊成一個單一的三階鄰接張量來編碼。在本文中,我們引入了張量超超圖的概念。利用線圖變換,我們進一步定義了張量線圖和張量迭代線圖,并研究了這些構造的基本性質。
關鍵詞:超超圖,超圖,張量超超圖,張量線圖,張量迭代線圖
1 預備知識
本節固定符號并回顧后續使用的基本對象。
1.1 超超圖
圖論研究由邊連接的頂點系統,強調數學、計算機科學和眾多應用中出現的連通性、結構性質和算法問題 [1]。超圖通過允許一條邊連接頂點集的任意非空子集來擴展普通圖,因此為真正的多路交互提供了自然的形式化方法 [2, 3]。這種更高元數的關系在現代學習流程中變得越來越重要,包括利用超圖結構的最近神經網絡架構 [3–7]。
如果進一步迭代冪集構造,那么頂點本身可以是嵌套的集合值對象。這導致了有限超超圖,其頂點集和邊集都可以存在于集合嵌套的多個“層級”上 [8, 9]。這些層級表示自然地出現在關系是分層的或多尺度的設置中,例如在分子設計、復雜網絡分析和神經網絡建模等應用中 [10–16]。相關的變體也已被研究,包括有向超超圖 [17, 18] 和元超超圖 [19]。
![]()
![]()
1.2 張量圖與張量超圖
張量圖是一種多重網絡:即共享頂點的 r 個圖構成的 r 元組,通過將它們的鄰接矩陣堆疊成一個張量來進行編碼 [26–28]。這一概念在神經網絡的背景下得到了積極研究,例如被稱為張量圖卷積網絡 [27, 29–31]。張量超圖通過一個對稱的 M 階鄰接張量來表示一個 M 階超圖,該張量編碼了頂點之間的多路超邊交互。在全文中,設 V 為一個有限頂點集,滿足 |V| = n,并且(在方便時)將 V 等同于 {1, ..., n}。對于整數 r ≥ 1,我們記 [r] := {1, ..., r} [32–36]。
![]()
![]()
![]()
![]()
![]()
作為參考,表 2 展示了圖、其線圖及其迭代線圖之間的比較。
雖然與本文的主要結果沒有直接關系,但附錄 A 討論并考察了迭代線圖的一個進一步推廣的概念。
![]()
2 主要結果
本節闡述本文的主要結果。
2.1 張量超超圖
我們現在將超超圖的嵌套頂點視角與超邊關聯的張量編碼相結合,本著與超圖的鄰接張量表示一致的精神。
![]()
![]()
![]()
作為參考,張量圖、張量超圖和張量超超圖的概覽見表 3。
![]()
下面給出一個具體的例子。
例 2.6(張量 n -超超圖的一個具體現實實例)。考慮大型制藥項目中的協作藥物發現。存在多個組織層級(個體研究人員、項目團隊、部門以及跨部門特別工作組),并且每個協作事件都在幾個并行的實驗條件下進行評估。張量 n -超超圖是這種情況的自然形式化,因為 (i) 頂點對象是嵌套的(團隊之團隊等),并且 (ii) 多路交互的強度/質量可以記錄為一個張量,其索引對應于測量軸。
![]()
![]()
![]()
![]()
![]()
![]()
3 附加結果:迭代張量線圖
張量線圖使用張量將線圖鄰接提升到超圖或高階結構,將邊關聯關系轉變為基于張量的連通性表示。迭代張量線圖重復應用張量線圖構造,產生連續的邊之邊張量鄰接,跟蹤跨迭代的高階交互傳播。我們形式化了經典線圖構造的一個張量裝飾變體。貫穿全文,所有圖均為有限簡單圖(無自環且無平行邊),除非另有說明。
![]()
![]()
張量標簽。 固定諸如以下的軸:
- 一天中的時段桶(早高峰、中午、晚高峰、夜間),
- 服務模式(普通/特快,工作日/周末),
- 指標(預期延誤、運力利用率、中斷風險、維護緊迫性)。
![]()
![]()
![]()
例如,條目可以表示歸一化的預期延遲、損壞概率、二氧化碳強度以及貨幣成本。
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
4 未來工作
我們預計未來的研究將探討基于模糊集 [49]、中性集 [50, 51] 和 plithogenic 集 [52, 53] 的擴展,以及它們在神經網絡等基于學習的方法中的應用。此外,我們注意到,基于元圖 [19, 54]、線超超圖 [47, 48]、超粗糙集 [55] 和粗糙集 [56] 等框架的進一步理論擴展與實證研究也有望被積極展開。
原文鏈接:https://www.techrxiv.org/users/868224/articles/1374006-tensor-superhypergraph-and-tensor-iterated-line-graph
特別聲明:以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布,本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.