Hypergraphx: 一整套高階網絡分析算法和功能

Hypergraphx: a library for higher-order network analysis

Hypergraphx:用於高階網絡分析的庫

https://github.com/HGX-Team/hypergraphx

從社會系統到生物系統，許多現實世界的系統都具有高階的非二元交互。這些系統可以用超圖來方便地描述，其中超邊表示任意數量單位之間的交互。在這裡，我們介紹了一個開源的 Python 庫——HypergraphX（HGX），它提供了一整套用於高階網絡分析的算法和功能。這些功能包括不同的數據轉換方式，將數據從一種高階表示形式轉換爲另一種高階表示形式，局部和中觀尺度的各種高階組織度量，高階數據的稀疏化統計過濾器，廣泛的靜態和動態生成模型，以及不同的具有高階交互的動態過程實現。我們的計算框架是通用的，允許分析具有加權、定向、帶符號、時間序列和多重羣體交互的超圖。我們通過各種可視化工具提供高階數據的可視化洞察。我們提供了一個擴展的高階數據庫，並通過對具有高階交互的社會網絡的系統分析來展示 HGX 的分析能力。該庫作爲一個不斷髮展的社區合作項目，將在未來幾年進一步擴展其功能。我們的軟件可以在 https://github.com/HGX-Team/hypergraphx 上獲得。

1. 引言

在過去的幾十年中，網絡作爲一種自然的工具，用於建模各種自然、社會和人造系統已經嶄露頭角。網絡由節點和連接節點對的鏈接組成，它們只能捕捉二元交互。然而，在許多現實世界的系統中，單位以三人或更多人的組進行交互[1–4]。具有非二元交互的系統無處不在，例子包括細胞網絡[5]、藥物重組[6]、結構和功能腦網絡[7–9]、人類[10]和動物[11]的面對面交互，以及合作網絡[12]。這些高階交互可以通過另一種數學結構——超圖來自然描述，其中超邊連接任意大小的節點組。

在過去的25年裡，技術進步產生了前所未有的大量關係數據，涵蓋了各種領域。拓展了網絡科學領域的早期開創性貢獻[14–16]，這些進步使得開發新的數據驅動框架來研究生物、技術和社會系統成爲可能。與理論和方法的進步並行，算法和計算工具的開發在推動網絡科學發展中發揮了關鍵作用。如今，廣泛使用的社區基礎軟件，如 NetworkX [17] 和 igraph [18]，以及諸如 graph-tool [19] 之類的個人努力——僅舉幾例——使得成千上萬的研究人員能夠對關係數據進行多方面、大規模的網絡分析。最近，一些早期貢獻[20–24]，特別是 XGI [25]，已經開始開發計算工具，以匹配對高階系統興趣的爆炸性增長。

在此，我們通過介紹 HypergraphX (HGX) 來提供我們的貢獻，這是一個用於分析具有高階交互的網絡系統的多用途開源 Python 庫。該庫由在高階交互領域有多年經驗和直接貢獻的研究人員構思開發。HGX 由一個多學科的團隊開發，該團隊具有互補的技能和專業知識，旨在作爲單一來源，提供一套全面的工具和算法，用於構建、存儲、分析和可視化具有高階交互的系統。這些工具包括不同的數據轉換方法，以不同的高階表示形式進行轉換；局部和中觀尺度的各種高階組織度量；稀疏化高階數據的統計過濾器；各種靜態和動態生成模型；實現不同的高階交互動態過程，從流行病到擴散、同步等。我們的計算框架是通用的，允許分析具有加權、定向、帶符號、時間序列和多重羣體交互的超圖。除了領域專家，我們希望我們的庫能使所有對探索關係數據高階維度感興趣的人都能訪問高階網絡分析。

2. 工具

在這裡，我們討論 HGX 提供的主要功能。我們的庫中的不同工具通過詳細、用戶友好的教程在線展示。該庫作爲一個不斷髮展的社區基礎項目，將在未來幾年進一步擴展其功能。

2.1 表示

超圖代表了編碼具有高階交互系統的最通用和靈活的框架[2, 13]。然而，特定的研究問題或數據特徵可能從其他高階框架中受益。我們提供了將通常表示爲超圖的高階數據輕鬆且高效地轉換爲不同表示形式的函數，如二分網絡、最大簡形復形、高階線圖、對偶超圖和 clique 擴展圖[2, 26]。

2.2 基本節點和超邊統計

我們的庫提供了描述基本節點和超邊統計的簡單工具。這些工具包括超度分佈的度量，無論是彙總的還是按交互階數分開的，以及它們之間的相關性度量。我們包括計算超度-超度關聯性的函數，涵蓋了階內和階間的情況。我們還提供了計算整個系統以及單個節點級別的超邊大小分佈的簡單工具。

2.3 中心性度量

中心性分數是網絡分析中的關鍵工具，允許量化系統中不同節點的重要性或影響力[15]。具有高中心性的節點通常具有大量鏈接、在其他重要節點之間具有戰略連接，或具備這兩種特徵。我們的庫提供了多種高階中心性度量，考慮了不同羣體大小的交互。這些包括基於節點參與不同子超圖的中心性度量[27]和基於譜方法的不同中心性分數[28]。我們還實現了基於最短路徑和介數流的超邊中心性度量[29]。

2.4 模式

模式是網絡中過度代表的小的重複子圖模式[30]。模式分析已成爲網絡科學中的一個基礎工具，用於描述網絡系統的微觀尺度，識別其結構和功能構建塊[31]。我們提供了高階模式分析的實現，提取由高階交互連接的過度丰度子圖，正如 Ref. [32] 中最初定義的那樣。考慮到它們的廣泛應用和預計在大規模現實世界數據集上的使用，我們還提供了一種基於超邊採樣的高階模式分析的近似算法，能夠在僅有極小精度妥協的情況下顯著加速計算[33]。

2.5 中尺度結構

在表示現實世界系統的圖中，最相關的特徵之一是社區結構[34]。各種圖社區檢測方法展示了這些劃分如何提供對節點交互基本模式的有意義洞察。近年來，定義高階網絡中尺度結構的方法得到了探索。我們提供了一種基於譜方法的實現，通過超圖切割優化來恢復硬社區[35]。我們還實現了不同的生成模型，這些模型能夠提取重疊社區並聯合推斷超邊[36]，從而捕捉多種中尺度組織結構，包括不關聯的和關聯的社區結構[37]。我們提供了一種能夠提取超鏈接社區的方法，其中交互而非系統單位被聚類到不同的超圖模塊中[38]。最後，我們提供了一種方法來提取高階系統的核心-邊緣組織，捕捉在超圖中支配整體系統行爲的一組中心和緊密連接的節點，這一方法受到了 Ref. [39] 的啓發。

2.6 過濾器

許多現實世界的系統特點是過多的噪聲和冗餘的交互，導致網絡連接過於密集。爲了通過統計驗證的方法確定最有信息的連接，已經開發了不同的過濾技術，這些方法通過與保留一些個體特徵（如度數或強度）的隨機複製集進行比較，來評估真實系統中交互的統計顯著性[40]。我們的庫提供了多種過濾工具，用於處理具有高階交互的系統。這些工具包括提取統計驗證的超圖，這是一組過度表達的超邊，代表在相同大小的固定組中顯著交互的節點[41]，以及識別顯著的最大交互集，這些集代表交互顯著的最大節點組，通過結合不同階的交互來捕捉[42]。

2.7 生成模型

生成具有不同拓撲特徵的合成數據的能力對於各種任務至關重要，從算法基準測試到非平凡網絡統計的研究和測試[43, 44]。在我們的庫中，我們提供了各種合成超圖採樣器的現成實現。我們提供了構建廣義 Erdös–Rényi 模型的函數，適用於均勻（所有交互具有相同階數）和非均勻（不同階的交互）超圖。我們實現了無標度隨機超圖模型，可以調整不同階之間度序列的相關性。我們還包括各種隨機化工具和超圖配置模型，其中樣本是在尊重給定的節點度和超邊大小序列的情況下生成的[45]。基於類似的機制，我們還實現了一個更復雜的採樣器，允許指定節點的硬性和軟性社區分配以及任意社區結構，如關聯和不關聯[46]。最後，我們提供了一個高階活動驅動模型，其中組交互隨時間變化[47]，並計算了相關的滲透閾值。

2.8 動態過程

複雜網絡的結構特性會影響在其上發生的動態過程[48]。最近的研究揭示了高階交互顯著影響各種動態過程，包括滲透[49]、擴散[50, 51]、模式形成[52, 53]、同步[54–58]、傳染[59–61]和進化博弈[62–64]。我們提供了研究這些過程的功能。這些工具包括用於分析高階交互的同步工具，從對 Kuramoto 動力學的多階拉普拉斯矩陣分析[55]，到用於同步穩定性的主穩定性函數方法[54, 65]的實現。我們還提供了模擬簡形社會傳染的算法[60]，以及分析和數值工具來研究超圖上的隨機遊走[50]。

2.9 加權、定向、帶符號、時間序列和多層超圖

我們的庫具有高度的靈活性。它允許存儲和分析具有豐富特徵的超圖，包括不同強度、方向、符號的交互，這些特徵可能隨時間變化或屬於多層系統的不同層。

2.10 可視化

隨着對高階網絡的應用迅速增加，開發標準工具來可視化這些網絡仍在進行中。我們的庫提供了不同的可視化工具，以便對現實世界系統中的高階組織結構獲得視覺洞察。我們提供了繪製高階交互系統的工具，其中任意大小的超邊表示節點之間的關係。由於可能的高階交互及其重疊數量的組合性迅速增加，這種直接的方法特別適用於節點數量適中的系統，而在其他情況下可能效果不佳。因此，我們提供了替代方案，可以在各種情況下協助用戶，例如節點數量或超邊大小較大的關係數據。例如，我們提供了繪製超圖的二部投影的選項，其中兩個節點集分別代表原始系統單元和它們參與的超邊。我們還可以繪製超圖的克利克投影，這將生成一個簡單的圖，其中每個大小爲s的超邊被分解爲s(s−1)/2個無序的對偶交互。此外，我們實現了超圖的多層表示，其中每一層編碼了給定大小的交互，兩個節點僅在它們通過大小爲s的超邊在超圖中交互時纔在第s層連接。最後，我們提供了一種新穎的超圖可視化方式，其中超圖表示爲圖，圖的節點是餅圖。這些餅圖顯示了每個節點的交互大小比例，兩個節點之間的連接表示它們在多個階次中有顯著的交互。

3. 數據

在這裡，我們介紹了附帶我們庫的數據集存儲庫。該存儲庫旨在提供一個初始核心的高階關係數據，我們計劃在接下來的幾年中擴展這些數據集。我們通過對其中一個數據集進行不同的高階分析來展示HGX的功能。

3.1 高階數據存儲庫

數據的可用性在不同科學領域和應用中開發理論框架和計算工具方面發揮了重要作用。近年來，高階關係數據的激增促使了研究高階系統的新方法，這些方法需要廣泛的數據集來進行測試和驗證。一些數據本質上是高階的，而另一些數據最初是通過對偶方法研究的，但最近重新以高階網絡分析的新視角進行了探索。這促使我們爲我們的庫提供一個易於訪問且精心策劃的數據存儲庫，作爲分析高階系統的數據集的統一來源。我們提供了來自不同領域的高階系統的數據集，包括生態（動物接近度[66]）、社會（人際面談互動[67–71]、共同作者[72–74]、投票[75]）、技術（電子郵件[73, 76, 77]）和生物（基因-疾病[78]和藥物[73]關聯）系統。這些數據集中有些記錄了描述系統單元的元數據（例如，醫院中的個體是病人還是醫生）和它們之間的交互（例如，涉及一組作者的科研論文的科學領域）。此外，它們還存儲了羣體交互的結構特徵，這些特徵可能是非互惠的、多重關係的和時間變化的。數據集可以在加載時明確突出一些這些特徵。實際上，我們的庫允許在數據加載過程中應用過濾器，例如，通過選擇特定的節點集合來滿足某些元數據限制，或提取限制於特定大小、類型或時間間隔的羣體交互。在未來幾年，我們計劃不斷擴展數據存儲庫，併爲數據加載函數添加更多過濾選項。

3.2 分析現實世界的高階系統：引導之旅

爲了展示HGX在加載、處理、分析和可視化具有羣體交互的現實世界系統中的強大功能，我們在圖1中展示了對SocioPattern合作數據集的示例分析，該數據集記錄了高中中的面對面社交互動[69]。這個數據集在高階交互的文獻中得到了廣泛研究[32, 36, 46, 60, 73]，記錄了327名學生的活動，這些學生分爲九個不同的高中班級。我們的分析特別集中在2人、3人和4人之間的互動，因爲對於較大羣體的統計數據有限。

在圖1(A)中，我們展示了不同的高階度分佈。對於成對的交互，度數最大，一般來說，曲線顯示出不同的輪廓。高階度分佈在不同的階次之間顯示出不同的相關性（皮爾遜相關係數 ρ，ρ2,3 = 0.74，ρ2,4 = 0.46，ρ3,4 = 0.72）。爲了在微觀尺度上表徵這樣的高階系統，在圖1(B)中，我們進行了高階圖案分析，如Ref. [32]中介紹的那樣。我們考慮了三節點的子超圖，並捕捉了在數據中較多（正丰度分數較高）和較少（負丰度分數）出現的圖案，相較於隨機的高階配置模型[45]。發現有羣體交互支持的局部結構特別相關。在圖1(C)中，我們描述了系統的中尺度結構，通過使用Ref. [36]中的方法提取重疊的社區。爲簡化起見，我們考慮了三類的子集，並僅繪製了成對的交互。節點用餅圖表示，顏色與它們所屬的高階社區成比例。一般而言，推斷出的模塊與節點元數據很好地對齊，大多數學生主要在其班級相關的社區內進行交互。在圖1(D)中，我們展示了數據集中交互的統計信息。我們觀察到交互數量與羣體大小之間的反向趨勢。我們還繪製了過濾系統的統計信息，其中我們考慮了統計驗證的超圖[41]，去除了冗餘超邊，並識別了最具信息性的羣體交互。接下來，我們展示了Ref. [46]中介紹的模型生成與原始數據集相似的超圖的能力。爲了驗證這一點，在圖1(E)中，我們繪製了現實和採樣超圖中（一個重新縮放版本的）高階中心性度量的分佈，顯示了兩者之間的良好一致性。爲了進一步說明我們計算框架的靈活性，我們考慮了高階交互的時間維度。特別是在圖1(F)中，我們展示了不同交互規模的時間自相關性，這是Ref. [79]中引入的用於表徵高階系統時間演變的測量方法之一。結果顯示所有交互階次都存在長程相關性，時間截止點取決於羣體大小。除了結構分析，我們的庫還允許研究多種高階交互的動態過程。在這裡，我們模擬了高中生中的高階傳播，採用了一種模型，其中感染個體的羣體與高階傳染項相關聯，此外還有傳統的成對機制[60]。在圖1(G)中，我們展示了兩種配置下的感染節點比例隨時間的變化，一種包含高階感染，另一種不包含。如圖所示，存在這種高階項可能顯著改變集體動態，將系統從健康狀態推向流行狀態。最後，在圖1(H)中，我們呈現了高階系統的直接超圖可視化。爲了簡化起見，我們繪製了單一班級的個體，並顯示了他們之間的所有統計顯著交互[41]，包括兩個、三個和四個個體之間的交互。

結論

隨着新理論和方法的不斷髮展，高效算法和軟件的開發在現代網絡科學的進步中發揮了關鍵作用。在這裡，我們介紹了HGX，一個多功能且強大的Python庫，提供了一個靈活高效的框架來分析具有高階交互的網絡系統。其用戶友好的環境和廣泛的功能使其對實踐者和研究人員都非常有用，可以解決各種需求和問題。未來，我們計劃繼續擴展HGX的工具集，探索多個新維度。例如，我們已經預見到將實現調查高階系統在不同攻擊策略下的魯棒性工具。我們還將提供有效總結高階信息和降低高階數據維度的方法。我們計劃包括用於從多變量時間序列構建和分析高階依賴關係的工具[9]，以及捕捉冗餘和協同高階交互的信息理論度量[80]。此外，我們還計劃擴展對高階過程的覆蓋，包括不同的進化博弈[62, 64]、生態動態[81]等。

我們希望HGX能夠讓所有處理網絡數據的研究人員都能進行高階網絡分析，並邀請社區探索該庫並進行貢獻。