Detecting communities in higher-order networks by using their derivative graphs

利用導數圖檢測高階網絡中的社區結構

https://doi.org/10.1016/j.chaos.2023.114200

摘 要

與成對網絡領域中發生的情況類似，超圖（也稱為高階網絡）的節點社區由共享許多超邊的節點組形成，因此它們與其余節點共享的超邊數量顯著較少，這些社區可以被視為超圖的獨立部分（或超級簇）。在本工作中，我們提出了一種基于超圖的所謂導數圖的方法，該方法能夠在不產生高計算成本的情況下檢測高階網絡的社區。同時，我們展示了若干模擬實驗，結果表明所提出的方法相較于其他現有方法具有顯著的計算優勢。

關鍵詞: 超圖 超圖的導數 高階網絡 社區 超圖中的社區 UPGMA（非加權組平均法） 層次聚類

1. 引言

在過去的三十年中，網絡科學得到了快速發展，并成為最熱門且最成功的研究領域之一，在遺傳學、神經科學、系統生物學、人工智能、氣象學和網絡安全等領域有著跨學科的應用[1-8]。復雜網絡模型已成為表示和模擬系統各部分之間不同類型交互關系的不可或缺的工具，廣泛應用于工程、語言學、社交網絡和經濟學等多個領域[6,9-16]。然而，在許多情境和情況下，無法通過成對交互來描述系統中不同組件之間的關系，因此為了建立一個適當的系統模型，必須考慮高于二階的交互[17-24]。新興的結構和多種應用模型使得我們能夠以非常高效的方式表示復雜系統組成元素之間的不同類型的交互。通過將兩節點網絡中的交互概念擴展到多節點的交互，超圖或高階網絡的概念自然應運而生[17,18,25,26]。值得注意的是，正如成對連接的網絡一樣，在實際的高階網絡中，節點之間的連接是非常異質的，一些節點具有大量連接，而另一些節點的交互程度則低得多，從而形成了具有高度集中內部交互但與外部組交互較少的節點群。于是，節點被劃分為不同的組，揭示了社區結構，這使得可以在微觀尺度上分析高階網絡。在這種尺度下，可以通過一個新的圖來研究高階網絡，其中頂點是社區，邊表示它們之間適當且特定規模的連接或交互。其基本思想是，每個社區聚集了共享許多屬性的節點，這些節點可能在網絡的功能中扮演類似的角色。

值得注意的是，從網絡拓撲結構中識別簇和模塊的問題有著悠久的傳統。該問題已在不同現象和多個學科領域中進行了研究（在組合圖論的背景下，這個問題被稱為“圖劃分”）。因此，針對這一問題的一些方法基于優化、統計推斷、隨機游走者、構建層次樹狀圖，甚至通過從局部種子節點開始逐步添加節點直到獲得某個質量函數的局部最優結果來獲取社區[27-29]。無論如何，成對交互網絡中的社區結構已經在文獻中得到了廣泛研究[27-37]。事實上，社區檢測算法的發展與這一工具所應用的眾多學科密不可分[2,4,8,11,27,29,33,34]。另一方面，在研究和識別密切交互并可能在所考慮結構中發揮相似作用的節點組方面，高階網絡背景下的社區檢測也引起了網絡科學界的一些關注[38-41]。在本文中，我們提出了一種基于超圖導數圖概念的新方法[10,42]，用于檢測高階網絡中的社區。該方法不僅自然適應于高階網絡，還在此背景下相較于其他算法具有一定的計算優勢。

本文的結構如下：引言之后，第2節致力于探討超圖導數的概念，并為通過導數圖檢測超圖中的社區奠定基礎。第3節應用前幾節定義的數學概念和結構，提出了一種檢測高階網絡中社區的新算法。第4節專注于將開發的工具應用于若干實際例子（包括合成數據和真實世界數據）以獲取相應的特征社區。最后，在第5節中，我們總結了本工作的結論。

2 基本概念與一些初步結果

如前所述，導數圖實現了一種用于衡量節點之間相似性的度量。因此，自然會產生一個問題：我們是否可以利用這一結構所提供的信息，將超圖中的節點劃分為不同的類別，使這些類別依據該相似性被區分開來？這將構成我們接下來將要討論的兩種社區發現方法的基礎。

3 在超圖中檢測社區的不同方法

現在我們已經建立了一些有用的概念和符號，接下來將介紹我們提出的兩種用于獲取超圖社區的算法。它們都具有層次聚類的背景，但在劃分方法上有所不同：第一種本質上是一個數據驅動的算法，而第二種則考慮了問題的超圖本質。隨后我們還將簡要介紹[47]中提出的另一種用于超圖中社區檢測的替代方法，用于與我們的結果進行比較。

3.1. 通過無監督聚類進行社區檢測
在層次聚類中，有兩種程序：聚合式（agglomerative）和分裂式（divisive）。本文聚焦的聚合式聚類方法在每一步中將距離最近的兩個簇合并，直到最終只剩下一個節點，覆蓋整個數據集。

聚合式層次聚類方法特別適用于僅定義了兩種成對距離函數的數據集劃分。一種距離函數用于衡量節點之間的距離，另一種用于根據節點間的距離衡量簇之間的距離，通常稱為連接函數（linkage function）。文獻中存在多種連接函數（如最短距離、平均距離或UPGMA、Ward方法等）[48–50]。在本研究中，我們將聚焦于平均距離連接函數，原因將在接下來的段落中討論。

通常，層次聚類方法處理的數據集可以看作是 R n 中的點。因此，一個經典的選擇是使用歐幾里得距離來建模數據集中點之間的距離。節點聚類的連續步驟可以用一種稱為樹狀圖（dendrogram）的圖示表示。具體而言，在圖的一個坐標軸上表示數據集的點，垂直坐標軸上表示“高度”，即簇之間的距離。

由于 d 只定義在一個離散集合上，因此考慮使用輔助元素（如質心）來計算簇之間距離的連接函數是沒有意義的。因此，在這種情況下，合適的連接函數選擇將是平均值（UPGMA，即非加權成對平均連接法）。

為了啟動凝聚層次聚類算法，每個初始簇將是一個包含一個節點的單元素集。在每一步中，將使用平均連接法計算簇之間的距離，即

3.2. 切割樹狀圖的一般標準：最大間隔切割

在指出切割樹狀圖的標準之前，正如在 [51] 中提到的，在凝聚層次聚類中，當在聚類過程中不同簇之間的兩個或多個距離相同時，對于成對分組方法并不存在唯一性。解決這一缺點的常用方法是采用任意標準來打破距離之間的平局，這會導致根據所遵循的標準產生不同的層次排序。盡管可以考慮其他標準（例如在 [51] 中提出的在平局發生時同時合并兩個以上的簇），但在本文考慮的算法 1 中，使用內部變量在不同簇之間的兩個或多個距離相同時給出的排序標準在計算上更為高效。

在任何情況下，在更廣泛的情境中，我們可以應用一個標準來選擇樹狀圖的一個特定劃分。盡管這種方法沒有使用超圖的額外信息，但其結果可能足夠準確，值得考慮。盡管它很簡單，但這個標準是直觀的，值得解釋。

在凝聚層次聚類中，每一步都會合并兩個不同的簇，以最小化簇之間的距離，這里將這種距離記作 D 。例如，在第一步中，它會尋找

3.3. 基于模塊性的樹狀圖切割標準

模塊性是傳統網絡分析中用于量化網絡中社區結構或模塊化組織存在與否的概念。一個具有模塊性的網絡以節點劃分為不同的組或社區為特征，社區內的節點彼此之間的連接比與其他社區的節點連接更為緊密。

對于成對網絡的模塊性，它衡量這種社區結構的強度。它是一個介于 -1 到 1 之間的標量值，更高的值表示更強的模塊化結構。接近 1 的模塊性值表明社區之間的劃分非常清晰，而接近 0 或負值則表明社區結構較為隨機或不夠明確。它定義為：

然而，到目前為止，對于超圖模塊性的定義尚未達成共識，因為已有多種方法通過使用（3.7）并基于超圖構建某種成對鄰接矩陣來定義它。特別是，Kumar 等人 [47] 使用超圖的團（clique）約簡來定義超圖模塊性，并且由于從團約簡得到的圖中每個節點的度與超圖中的度不一致，他們還進行了一些額外的調整。更具體地說，他們定義了一個具有鄰接矩陣的圖：

因此，在這種方法中，我們將選擇最大化模塊性（使用公式 3.8）的劃分（由樹狀圖給出）。請注意，盡管導數圖（定義 2.4）為我們提供了一個鄰接矩陣，但我們不能用它來計算模塊性值，因為考慮到導數圖的定義，超圖中的一些節點可能會在導數圖中合并為新的節點。此外，導數的較小值意味著節點之間的相似性更高，而公式 3.8 中導數的較小值則意味著社區結構更弱。此外，由于我們希望將我們的方法與 [47] 中的方法進行比較，我們需要使用相同的鄰接矩陣來進行這樣的比較。

迭代劃分。需要注意的是，根據對社區劃分細致程度的需求，算法2可以迭代地應用于每個獲得的社區（考慮與它們相關的子超圖）。這通常會增加獲得的模塊性。

3.4. 其他方法：迭代加權模塊性最大化（IRMM）

在文獻中，已經存在一種基于團約簡（3.8）的超圖社區檢測方法，該方法通過最大化模塊性來實現，即迭代加權模塊性最大化（Iteratively Reweighted Modularity Maximization, IRMM）算法。我們將在后續部分將其與我們的方法進行比較，因此這里先簡要概述。

IRMM算法的核心思想是在超圖 H 的團約簡圖上應用Louvain算法，以獲得最大化模塊性的劃分。隨后，算法通過依賴于當前劃分的重新加權函數重新計算超邊的權重。重新加權的目的是強調當前聚類能夠較好捕捉的超邊的重要性，并降低信息量較少的超邊的影響。通過迭代地重新加權超邊并最大化模塊性，IRMM算法旨在發現能夠最大化超圖社區結構的劃分。迭代過程通過逐步調整超邊權重和節點分配，幫助細化聚類結果。

4. 應用與現實世界示例

現在我們已經建立了兩種社區檢測算法（算法1和算法2）的理論基礎，接下來我們將轉向它們在合成網絡和真實網絡中的應用，并與之前提出的社區檢測方法 [47] 進行比較。

我們將首先將這些算法應用于一個“手工設計”的超圖，在這個超圖中，通過簡單的視覺檢查，我們可以預期兩種算法都能找到合理的劃分。隨后，我們使用一個真實且帶有標簽的小學學生數據集 [53, 54]，發現這些算法能夠以高精度預測節點標簽（即個體所屬的班級）。最后，我們在這一部分的結尾將這些算法應用于一個更具異質性的數據集——科學合作網絡。

所有數值模擬均在專用服務器（4.0 GHz Intel Xeon Gold 5220R）上進行，數據和代碼可在以下鏈接獲取，以確保結果的可重復性： 。

4.1. 一個簡單的玩具模型

為了實踐和討論前一節中引入和討論的想法，我們考慮了一個“玩具模型”，即一個預先設計好預期社區結構的超圖。這個超圖包含14個節點（按字母順序標記為字母）和21條超邊，如圖2所示。我們還展示了其導數圖對應的樹狀圖。

通過一般方法（在最大間隔處切割樹狀圖），我們找到了以下劃分：

如果我們改用最大模塊性來劃分，得到的劃分結果是相同的（這意味著在最大間隔處切割樹狀圖可以得到具有最大模塊性的劃分，如圖2d所示），模塊性值為 Q = 0.34056 。

使用Kumar算法，我們發現了一組不同的社區：

很容易看出，這兩個劃分之間的唯一區別是，在第一個劃分中我們有一個額外的社區 ，而在第二個劃分中，它被拆分到了社區中。鑒于社區檢測本身總是存在一定的主觀性（并且在這個人為設計的例子中沒有所謂的“真實情況”），這種差異是在合理范圍內的。

在簡單的例子中驗證了一切如預期般運行之后，我們現在轉向更現實的用例。

4.2. 用真實數據驗證劃分結果

將社區檢測應用于真實網絡時，面臨的一個主要問題是：獲得的劃分是否“合理”。這種合理性通常來源于圖之外的信息，通常與所討論網絡的特征和/或數據中未用于構建圖或超圖的信息或標簽有關。

因此，為了驗證所提出的方法，將其應用于一個真實的數據集（而不是像前面的玩具模型那樣人為設計的）是很有意義的，這個數據集可能基于數據集的信息對獲得的社區有一些“普遍共識”。

為此，我們將分析法國里昂一所小學在兩天內232名學生和10名教師之間的面對面互動數據 [53, 54]。該數據集包括10個不同的班級，每個年級（從一年級到五年級）各有2個班級。互動是通過近距離傳感器測量的，每個傳感器都與一個組相關聯：對于學生是特定的班級，對于教師則是“教師”標簽。因此，超圖由這242個節點組成，代表學生和教師，以及12699條超邊，這些超邊代表近距離傳感器在20秒時間框架內捕獲的面對面互動。

應用算法1和算法2，我們得到了有意義的結果。使用基于高度的切割算法，我們識別出8個社區。其中6個分別對應單獨的班級：1A、1B、2A、2B、4A和4B。剩下的兩個分別對應3A與3B的合并，以及5A與5B的合并。需要注意的是，一些社區中包含來自其他班級的少數“異常值”，但絕大多數都屬于其同齡人。如果我們改用基于模塊性最大化的算法，我們會發現1A、1B、2A和2B會被合并在一起。

從這次分析中，我們可以得出兩個結論：從社區檢測的角度來看，這些算法能夠得出合理的分類結果，因為它們（特別是基于高度的切割算法，在這個特定例子中）符合應用于小學的社區檢測預期。從社會網絡的角度來看，這暗示了年幼的孩子可能跨越不同年級形成社區，而年長的孩子則更多地按年齡分化。

在表1中可以找到對這個數據集應用這兩種方法的更定量的比較。值得注意的是，盡管超圖中存在大量的超邊，基于高度的切割方法在社區檢測任務中表現得非常高效。而模塊性最大化方法受到構建團約簡圖（3.8）的計算成本的限制，這是計算模塊性所必需的。

在真實數據集中驗證了獲得的劃分結果的合理性之后，我們將轉向一個更具異質性的數據集，以進行最終比較，驗證我們方法相對于文獻中已有的方法的優勢。

4.3. 真實數據的進一步結果

為了展示和比較我們的算法應用于真實數據時的表現，我們考慮了斯特凡諾·博卡萊蒂（Stefano Boccaletti）教授的合著者網絡作為一個“試驗場”來檢測社區。我們將首先描述該數據集的主要特征以及構建超圖時所做的不同選擇。隨后，我們將對我們的算法進行測試，并將其與其他已提出的算法進行比較，就像我們之前對玩具模型所做的那樣。

數據集 我們構建了一個初始的合作超圖，其中每個節點是一位與Boccaletti教授合作過的作者，每條超邊代表一篇科學出版物。數據來源是Scopus，總計有338篇出版物和413位合著者。

為了給超圖增加更多的結構，我們加入了另一組數據，這次不包括Boccaletti教授，而是包含每位合著者的全部出版物（原則上可能包括從未與Boccaletti教授合作過的其他作者，但這些作者并未被納入超圖中）。因此，超圖得以擴展，現在總共包含15237條超邊。

雖然我們的算法可以直接處理這個超圖，但我們發現，當將其應用于該超圖時，文獻[47]中提出的IRMM算法無法在合理時間內收斂（在一臺配備4.0 GHz Intel Xeon Gold 5220R的專用服務器上運行超過24小時）。為了比較兩種方法，我們決定根據以下標準對超圖進行過濾：僅保留與Boccaletti教授有5篇或更多共同出版物的作者（即我們考慮頻繁合作的作者）。經過過濾后的超圖包含67位作者，涉及他們之間和/或Boccaletti教授的1685篇出版物。

社區檢測 我們將四種方法（導數圖最大間隙切割、最大模塊度、迭代最大模塊度、IRMM）應用于Stefano Boccaletti的合作者超圖。在展示實際分區結果（圖3）之前，讓我們先介紹每種方法的一些定量結果和指標。

從表2可以清楚地看出，盡管在模塊度方面最佳的分區是IRMM方法得到的，但其計算成本并不值得這種微小的模塊度提升，其運行速度比我們的最大模塊度方法慢了約320倍。還應指出，IRMM能夠獲得最高的模塊度是可以預期的，因為這是一種專門設計用于優化該分數的算法，而其他方法并非如此。因此，令人印象深刻的是，通過簡單地掃描樹狀圖中的個分區并選擇模塊度最大的一個，能夠如此高效地達到類似的分數（僅相差0.04）。需要注意的是，盡管IRMM和模塊度最大化都使用了團縮減方法（在小學示例中代價較高，見前一小節），但由于超邊數量的減少，團縮減的計算速度顯著加快。然而，IRMM的重新加權過程非常耗時，因為它需要在團縮減圖上多次運行Louvain算法[52]，這抵消了部分加速效果。

5. 結論

在本文中，我們提出了兩種用于檢測高階網絡社區（在超圖背景下）的方法，這些方法依賴于超圖的導數圖。通過多個例子和模擬實驗表明，導數圖所誘導的節點相似性和半距離概念對于在聚合過程中獲得的簇之間建立連接距離特別有用。

通過多次模擬實驗表明，盡管IRMM方法在模塊性方面給出了略微更好的劃分結果，但本文提出的方法在效率和計算成本方面更具優勢。第一種方法是識別樹狀圖中分支之間的最大距離。這種算法不僅速度最快，而且效率最高，因為它能夠達到非常高的模塊性值，接近IRMM的結果。此外，IRMM在計算上要昂貴得多，并且在其中一個例子中，它無法在合理的時間內完成所需的計算。另一方面，本文提出的第二種方法在模塊性方面有所改進，盡管它增加了額外的計算成本，但這種成本與IRMM相比微不足道，IRMM雖然能夠產生略微更好的模塊性值，但其計算成本顯著更高。

原文鏈接： https://doi.org/10.1016/j.chaos.2023.114200