加權單純復形對高階網絡數據與拓撲的表達能力

Weighted simplicial complexes and their representation powerof higher-order network data and topology

加權單純復形對高階網絡數據與拓撲的表達能力

https://arxiv.org/pdf/2207.04710

超圖和單純復形都能捕捉復雜系統的高階相互作用，其范圍從高階協作網絡延伸到大腦網絡。該領域的一個未解問題是：從高階相互作用的數據出發，應該由什么來驅動對所采用的描述高階網絡的數學框架的選擇。無權重單純復形通常會導致數據信息的丟失，盡管它具有捕捉數據高階拓撲結構的優勢。在這項工作中，我們表明加權單純復形能夠規避無權重單純復形在表示高階相互作用時的所有局限性。特別是，加權單純復形可以在不丟失信息的情況下表示高階網絡，同時還能捕捉數據的加權拓撲結構。我們通過研究適當定義的、呈現歸一化譜的加權霍奇拉普拉斯算子（Hodge Laplacians）的譜性質，來探測高階拓撲。本文將上同調理論與信息論相結合，研究了（加權）歸一化霍奇拉普拉斯算子的高階譜。在所提出的框架中，我們利用高階譜熵和譜相對熵，量化并比較了不同維度高階譜的信息含量。所提出的方法在真實的高階協作網絡，以及單純復形模型“帶風味網絡幾何”（Network Geometry with Flavor）的加權版本上進行了測試。

I、 引言

高階網絡 [1–10] 捕捉了復雜系統的高階相互作用，包括協作網絡、面對面社交互動網絡、大腦網絡和化學反應網絡。例如，在科學家之間的協作網絡中，高階網絡能夠捕捉由兩名或更多科學家組成的共同作者團隊的相互作用 [11, 12]。高階網絡包括超圖和單純復形。超圖由一組超邊組成，用于描述高階相互作用。單純復形由單純形組成，其中 n n-單純形由個節點組成。在文獻中，人們越來越關注確定這兩種專為對高階數據建模而設計的數學框架之間的差異。無權重單純復形與超圖的區別在于，超圖是超邊的任意集合，而單純復形是單純形的集合，且該集合在包含其每個單純形的面時是封閉的。例如，這一附加屬性意味著，如果節點 A、B 和 C 之間的三方相互作用（2-單純形，或實心三角形）[A, B, C] 存在于單純復形中，那么我們也必須在單純復形中包含構成該三角形面的所有連邊（成對相互作用）和所有節點，即我們還應包含單純形 [A, B]、[B, C]、[A, C]、[A]、[B]、[C]。在某些應用領域（如協作網絡）中，這可能會被視為一種局限性。事實上，如果協作網絡中的三位作者共同撰寫了一篇論文，通常情況下，并不意味著該三角形中每對科學家都撰寫過兩人合著的論文。另一方面，單純復形為網絡科學家提供了來自代數拓撲的非常強大的工具 [1, 13–15]，用于表征高階數據集的結構 [6, 8, 16–22] 以及拓撲與動力學之間的相互作用 [1, 23–50]。

解決超圖與單純復形之間這種二分法的一個方向是引入代數拓撲的概念來處理超圖 [51, 52]。在這里，我們探索另一個方向，并提議研究加權單純復形，這正吸引著越來越多的關注 [53–55]，其中單純復形的每個單純形都與一個稱為權重的實數相關聯。加權單純復形保留了在包含每個單純形的面時保持封閉的屬性。然而，在本文中我們表明，如果單純形的權重是根據我們的算法定義的，那么就可以區分那些僅僅為了滿足封閉條件而包含在單純復形中（且不描述數據中存在的原始高階相互作用）的單純形，與那些同時也編碼了原始高階相互作用的單純形。因此，通過所提出的權重選擇，單純復形可以與超圖互換使用，因為它們能夠保留數據中存在的所有信息。此外，我們表明，所提出的加權單純復形的權重選擇也允許使用加權單純復形的代數拓撲，從而研究其高階拓撲。事實上，所提出的單純形權重選擇使我們能夠定義每個維度的歸一化霍奇拉普拉斯算子（Hodge Laplacians）。歸一化霍奇拉普拉斯算子對于比較單純復形在不同維度下的譜性質特別有用，從而揭示其高階結構的重要方面。在這里，我們展示了高階譜熵（它推廣了網絡的譜或馮·諾依曼熵的概念 [56–62]）如何用于表征高階擴散過程 [25, 26, 31, 32, 63] 及其相關的特征時間尺度的性質。這些理論見解已被應用于真實的高階科學協作網絡數據集，以及加權單純復形模型“帶味網絡幾何”（Network Geometry with Flavor）[63–67]，揭示了編碼在這些高階網絡結構中的信息含量。重要的是，在分析高階協作網絡時，我們還提出了一種量化與每個合作團隊相關的原始權重的方法，從而將 Newman 在文獻 [68] 中提出的科學協作網絡權重的流行選擇擴展到了高階網絡。

請注意，在本文中，我們的重點是確立如何使用加權單純復形來捕捉真實數據而不丟失信息。因此，與旨在探索考慮不同高階表示時出現的動力學效應的其他近期工作 [69] 相比，我們的方法在性質和范圍上都是不同的。

本文的組織結構如下。在第二節中，我們討論了加權單純復形以及我們提出的拓撲權重選擇。在第三節中，我們介紹了代數拓撲的基本方面，這些方面引出了高階歸一化霍奇拉普拉斯算子和歸一化狄拉克算子（Dirac operator）的定義。在第四節中，我們討論了單純復形的高階譜熵及其性質。在第五節和第六節中，我們分別展示了所提出的數學框架在真實協作網絡和“帶味網絡幾何”模型中的應用。最后，在第七節中，我們提供了一些總結性評論。本文還包含一個附錄，提供了所提出的霍奇拉普拉斯算子在每個階數上都是歸一化的證明，從而豐富了本文的內容。

II、加權單純復形

單純復形 K K 是一種高階網絡 [1]，正被日益廣泛地用于研究數據的底層拓撲。單純復形編碼了復雜系統的高階相互作用，即兩個或更多節點之間的相互作用。換句話說，單純復形使得我們能夠超越僅基于成對相互作用的復雜系統網絡描述。

單純復形的基本構建單元是單純形。一個 n n 維單純形 α α（或 n n-單純形）由一組個節點組成

例如，一個高階協作網絡可以通過一個單純復形來描述，其中將所有至少合著了一篇論文的共同作者團隊視為單純形，并將對應的單純形及其所有面包含在該單純復形中 [11, 12]。因此，給定一個以此方式構建的無權重單純復形，該協作網絡無法被完全重構，因為只有面片（facets）才能確切地指示高階協作。

我們的目的是表明，只要做出適當的權重選擇，加權單純復形反而能夠不失任何信息地忠實地捕捉高階協作數據。

很容易驗證，由于公式 (2) 和公式 (3) 是線性的，它們是可逆的。因此，通過這種拓撲權重的選擇，總是有可能重構原始親和權重并對數據進行忠實的表示，即使數據包含一組高階相互作用，且這組相互作用在其節點子集的包含下并不封閉，正如一般的協作數據那樣。

單純復形的拓撲權重最終可能會隨時間演化和波動，在這種情況下，它們被恰當地稱為拓撲信號（topological signals），其動力學最近引起了廣泛關注 [1, 23–32, 34–37]。然而，在本文中，我們將僅考慮由拓撲信號的單個快照構成的拓撲權重，或者由隨時間恒定的拓撲信號構成的拓撲權重。

III、加權單純復形的高階譜

加權單純復形不僅能夠不失任何信息地忠實表示高階網絡數據，而且還允許對其高階譜進行研究，從而揭示高階擴散的重要性質 [26, 31, 32]。在本節中，我們介紹了研究加權單純復形高階譜的關鍵代數拓撲背景，這構成了將高階結構與高階動力學聯系起來的基本途徑。本節相關的背景文獻包括參考文獻 [1, 13–15, 69, 70]。

A. 鏈與上鏈

C. 高階加權拉普拉斯算子與霍奇分解

D. 加權狄拉克算子

根據加權拓撲狄拉克算子的定義，可以得出結論：狄拉克算子的平方是高階拉普拉斯算子的直和。

加權拓撲算子的特征值 λ λ 在絕對值上等于所考察單純復形的上邊界算子的奇異值。

E. 歸一化高階拉普拉斯算子

一個重要的問題是我們是否可以遵循類似的論證來提出高階拉普拉斯算子的歸一化版本。通常而言，提出歸一化的高階拉普拉斯算子是圖論中的一個重要問題。然而，直到目前為止，只有少數幾篇論文探討了這個問題（例如見文獻 [14, 34]）。在這里我們表明，利用由公式 (2) 和公式 (3) 給出的拓撲權重選擇，并使用對角元由公式 (20) 給出的度量矩陣，只要我們選擇

對于任何不超過單純復形階數的 n n，高階霍奇拉普拉斯算子就會自動歸一化。在這些假設下，可以證明霍奇拉普拉斯算子的特征值總是位于區間內（見附錄 A）。

值得注意的是，本工作中提出的拓撲權重選擇，即公式 (2) 和公式 (3)，自然地將通常用于歸一化圖拉普拉斯算子的權重選擇推廣到了高階情形；正如上文所討論的，該選擇將節點的權重分配為關聯連邊的權重之和。

IV、單純復形的高階譜熵

A. 高階譜熵的定義

為了表征編碼在網絡譜和廣義網絡結構中的信息含量，人們引入了譜熵，也稱為網絡的馮·諾依曼熵（Von Neumann entropy）[56–61]。網絡的譜熵被定義為量子力學中的馮·諾依曼熵 [75]，其中密度算子（density operator）取為與網絡相關聯的半正定算子（semi-definite positive operator），且具有歸一化的跡（normalized trace）。因此，密度算子的典型選擇通常取為圖拉普拉斯算子（graph Laplacian）的函數。在此，我們定義了加權單純復形的高階譜熵，并利用該量以及相關聯的高階相對熵，來評估加權單純復形高階譜的信息含量。

B. 譜密度與返回時間分布

C. 相對熵

在量子信息論 [75] 中，作用于同一空間的兩個密度算子 ρ ρ 和 σ σ 之間的馮·諾依曼相對熵（或量子 Kullback-Leibler 散度）定義為

V、在高階協作網絡中的應用

A. 高階協作網絡的拓撲權重

例如，由兩位作者組成的團隊的協作強度僅僅等于他們共同撰寫的雙人合著論文的數量，而由三位作者組成的團隊的協作強度等于他們共同撰寫的三人合著論文數量除以二，依此類推（見圖 1）。

圖1是一個有助于直觀展示權重分配結果的示例。從左側開始，描繪了由兩位共同作者撰寫單篇論文的簡單情況。接著，描繪了由三位作者撰寫論文的情況，隨后是一個更一般的情況。從情況(c)可以很容易地驗證，連邊的原始親和權重可以通過該連邊的拓撲權重減去與其關聯的三角形的拓撲權重之和來獲得。

B. 高階協作數據集

正如預期的那樣，該單純復形的網絡骨架是一個非連通圖，反映了可能存在孤立的作者協作群組這一事實。由于對馮·諾依曼熵的研究可以解釋為通過單純復形的信息擴散，我們將分析限制在由網絡骨架的最大連通分量所生成的單純復形上。在圖 2 中，我們展示了所考慮的單純復形的網絡骨架，它具有豐富的社區結構。生成的單純復形規模比原始數據集小得多，由 356 個節點、1,172 條邊和 2,614 個三角形組成。

C. 高階協作網絡的高階譜熵

在圖 3 中，馮·諾依曼熵及其導數被繪制為的函數，采用對數刻度。實線代表熵，而虛線表示比熱。第一行顯示了未加權網絡獲得的結果，第二行顯示了加權網絡獲得的結果。從左開始，繪制了直到單純復形階數（在本例中為 2）的每個階數的熵。從圖中可以看出，通過觀察 0 階和 1 階的熵，顯現出了熵的多尺度行為。這一點通過導數中局部極小值/極大值的存在而得到強調。更具體地說，雖然在未加權網絡中可以觀察到 0 階和 1 階具有非常淺的局部極小值和極大值的平臺，但在加權情況下觀察到由兩個更顯著的峰值決定的更清晰的時間尺度分離。這些不同的時間尺度與協作單純復形的介觀尺度（meso-scale）社區結構及其大尺度拓撲有關。然而，我們注意到，這種時間尺度的分離在 2 階譜熵的分析中并不明顯，這可以通過以下事實來解釋：不同的社區通常由僅通過節點相互連接的三角形形成，這不允許任何通過連邊從三角形到三角形的擴散。

VI.在帶味網絡幾何（Network Geometry with Flavor）中的應用

在本節中，我們研究了名為“帶味網絡幾何”（Network Geometry with Flavor）[64, 65, 67] 的加權單純復形模型的高階譜，這是一個非常有趣的基準，用于驗證我們要提出的方法論。該分析遵循與上一節中描述的協作復形分析相同的步驟。

A. 帶味網絡幾何作為加權單純復形模型

B. 帶味網絡幾何的高階熵

VII.結論

在此，我們要提出研究加權單純復形，并對單純形的權重采用精確的約定，以克服單純復形在捕捉任意高階網絡數據方面的局限性。所提出的數學框架的優勢在于，加權單純復形具有豐富的高階結構，可以通過高階加權和歸一化霍奇拉普拉斯算子（Hodge Laplacians）進行探測。高階霍奇拉普拉斯算子的譜使得我們可以利用信息論工具來量化包含在單純復形高階譜中的信息含量以及高階擴散過程的性質。事實上，我們要提出了高階譜熵的概念，并表明該量可用于表征高階擴散的典型時間尺度。此外，高階相對譜熵使我們能夠比較編碼在不同維度霍奇拉普拉斯算子譜中的信息含量。

所提出的方法在此在一個真實的高階協作數據集上進行了測試，該數據集是從文獻計量數據中提取的，采用了一種基于對簡單網絡中廣泛采用的約定進行擴展的程序來對高階協作進行加權。

最后，該方法也被應用于單純復形模型“帶味網絡幾何”（Network Geometry with Flavor）的加權版本。分析揭示了高階擴散性質對單純復形的依賴性，這種依賴性是控制參數的函數。這為理解單純復形的高階譜性質如何依賴于其底層拓撲結構提供了見解。

我們相信，所提出的單純復形權重選擇以及相關的歸一化霍奇拉普拉斯算子，將構成一個非常有用的工具，用于捕捉高階網絡數據的結構。此外，鑒于霍奇拉普拉斯算子越來越多地用于捕捉單純復形上拓撲信號的動力學，我們相信所提出的歸一化和加權霍奇拉普拉斯算子將成為描述加權單純復形上拓撲信號動力學的非常有用的工具。

原文鏈接：https://arxiv.org/pdf/2207.04710