Detecting communities in higher-order networks by using their derivative graphs
利用導(dǎo)數(shù)圖檢測(cè)高階網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)
https://doi.org/10.1016/j.chaos.2023.114200
摘 要
與成對(duì)網(wǎng)絡(luò)領(lǐng)域中發(fā)生的情況類(lèi)似，超圖（也稱(chēng)為高階網(wǎng)絡(luò)）的節(jié)點(diǎn)社區(qū)由共享許多超邊的節(jié)點(diǎn)組形成，因此它們與其余節(jié)點(diǎn)共享的超邊數(shù)量顯著較少，這些社區(qū)可以被視為超圖的獨(dú)立部分（或超級(jí)簇）。在本工作中，我們提出了一種基于超圖的所謂導(dǎo)數(shù)圖的方法，該方法能夠在不產(chǎn)生高計(jì)算成本的情況下檢測(cè)高階網(wǎng)絡(luò)的社區(qū)。同時(shí)，我們展示了若干模擬實(shí)驗(yàn)，結(jié)果表明所提出的方法相較于其他現(xiàn)有方法具有顯著的計(jì)算優(yōu)勢(shì)。
關(guān)鍵詞: 超圖 超圖的導(dǎo)數(shù) 高階網(wǎng)絡(luò) 社區(qū) 超圖中的社區(qū) UPGMA（非加權(quán)組平均法） 層次聚類(lèi)
1. 引言
在過(guò)去的三十年中，網(wǎng)絡(luò)科學(xué)得到了快速發(fā)展，并成為最熱門(mén)且最成功的研究領(lǐng)域之一，在遺傳學(xué)、神經(jīng)科學(xué)、系統(tǒng)生物學(xué)、人工智能、氣象學(xué)和網(wǎng)絡(luò)安全等領(lǐng)域有著跨學(xué)科的應(yīng)用[1-8]。復(fù)雜網(wǎng)絡(luò)模型已成為表示和模擬系統(tǒng)各部分之間不同類(lèi)型交互關(guān)系的不可或缺的工具，廣泛應(yīng)用于工程、語(yǔ)言學(xué)、社交網(wǎng)絡(luò)和經(jīng)濟(jì)學(xué)等多個(gè)領(lǐng)域[6,9-16]。然而，在許多情境和情況下，無(wú)法通過(guò)成對(duì)交互來(lái)描述系統(tǒng)中不同組件之間的關(guān)系，因此為了建立一個(gè)適當(dāng)?shù)南到y(tǒng)模型，必須考慮高于二階的交互[17-24]。新興的結(jié)構(gòu)和多種應(yīng)用模型使得我們能夠以非常高效的方式表示復(fù)雜系統(tǒng)組成元素之間的不同類(lèi)型的交互。通過(guò)將兩節(jié)點(diǎn)網(wǎng)絡(luò)中的交互概念擴(kuò)展到多節(jié)點(diǎn)的交互，超圖或高階網(wǎng)絡(luò)的概念自然應(yīng)運(yùn)而生[17,18,25,26]。值得注意的是，正如成對(duì)連接的網(wǎng)絡(luò)一樣，在實(shí)際的高階網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的連接是非常異質(zhì)的，一些節(jié)點(diǎn)具有大量連接，而另一些節(jié)點(diǎn)的交互程度則低得多，從而形成了具有高度集中內(nèi)部交互但與外部組交互較少的節(jié)點(diǎn)群。于是，節(jié)點(diǎn)被劃分為不同的組，揭示了社區(qū)結(jié)構(gòu)，這使得可以在微觀尺度上分析高階網(wǎng)絡(luò)。在這種尺度下，可以通過(guò)一個(gè)新的圖來(lái)研究高階網(wǎng)絡(luò)，其中頂點(diǎn)是社區(qū)，邊表示它們之間適當(dāng)且特定規(guī)模的連接或交互。其基本思想是，每個(gè)社區(qū)聚集了共享許多屬性的節(jié)點(diǎn)，這些節(jié)點(diǎn)可能在網(wǎng)絡(luò)的功能中扮演類(lèi)似的角色。
值得注意的是，從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中識(shí)別簇和模塊的問(wèn)題有著悠久的傳統(tǒng)。該問(wèn)題已在不同現(xiàn)象和多個(gè)學(xué)科領(lǐng)域中進(jìn)行了研究（在組合圖論的背景下，這個(gè)問(wèn)題被稱(chēng)為“圖劃分”）。因此，針對(duì)這一問(wèn)題的一些方法基于優(yōu)化、統(tǒng)計(jì)推斷、隨機(jī)游走者、構(gòu)建層次樹(shù)狀圖，甚至通過(guò)從局部種子節(jié)點(diǎn)開(kāi)始逐步添加節(jié)點(diǎn)直到獲得某個(gè)質(zhì)量函數(shù)的局部最優(yōu)結(jié)果來(lái)獲取社區(qū)[27-29]。無(wú)論如何，成對(duì)交互網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)已經(jīng)在文獻(xiàn)中得到了廣泛研究[27-37]。事實(shí)上，社區(qū)檢測(cè)算法的發(fā)展與這一工具所應(yīng)用的眾多學(xué)科密不可分[2,4,8,11,27,29,33,34]。另一方面，在研究和識(shí)別密切交互并可能在所考慮結(jié)構(gòu)中發(fā)揮相似作用的節(jié)點(diǎn)組方面，高階網(wǎng)絡(luò)背景下的社區(qū)檢測(cè)也引起了網(wǎng)絡(luò)科學(xué)界的一些關(guān)注[38-41]。在本文中，我們提出了一種基于超圖導(dǎo)數(shù)圖概念的新方法[10,42]，用于檢測(cè)高階網(wǎng)絡(luò)中的社區(qū)。該方法不僅自然適應(yīng)于高階網(wǎng)絡(luò)，還在此背景下相較于其他算法具有一定的計(jì)算優(yōu)勢(shì)。
本文的結(jié)構(gòu)如下：引言之后，第2節(jié)致力于探討超圖導(dǎo)數(shù)的概念，并為通過(guò)導(dǎo)數(shù)圖檢測(cè)超圖中的社區(qū)奠定基礎(chǔ)。第3節(jié)應(yīng)用前幾節(jié)定義的數(shù)學(xué)概念和結(jié)構(gòu)，提出了一種檢測(cè)高階網(wǎng)絡(luò)中社區(qū)的新算法。第4節(jié)專(zhuān)注于將開(kāi)發(fā)的工具應(yīng)用于若干實(shí)際例子（包括合成數(shù)據(jù)和真實(shí)世界數(shù)據(jù)）以獲取相應(yīng)的特征社區(qū)。最后，在第5節(jié)中，我們總結(jié)了本工作的結(jié)論。
2 基本概念與一些初步結(jié)果
如前所述，導(dǎo)數(shù)圖實(shí)現(xiàn)了一種用于衡量節(jié)點(diǎn)之間相似性的度量。因此，自然會(huì)產(chǎn)生一個(gè)問(wèn)題：我們是否可以利用這一結(jié)構(gòu)所提供的信息，將超圖中的節(jié)點(diǎn)劃分為不同的類(lèi)別，使這些類(lèi)別依據(jù)該相似性被區(qū)分開(kāi)來(lái)？這將構(gòu)成我們接下來(lái)將要討論的兩種社區(qū)發(fā)現(xiàn)方法的基礎(chǔ)。
3 在超圖中檢測(cè)社區(qū)的不同方法
現(xiàn)在我們已經(jīng)建立了一些有用的概念和符號(hào)，接下來(lái)將介紹我們提出的兩種用于獲取超圖社區(qū)的算法。它們都具有層次聚類(lèi)的背景，但在劃分方法上有所不同：第一種本質(zhì)上是一個(gè)數(shù)據(jù)驅(qū)動(dòng)的算法，而第二種則考慮了問(wèn)題的超圖本質(zhì)。隨后我們還將簡(jiǎn)要介紹[47]中提出的另一種用于超圖中社區(qū)檢測(cè)的替代方法，用于與我們的結(jié)果進(jìn)行比較。
3.1. 通過(guò)無(wú)監(jiān)督聚類(lèi)進(jìn)行社區(qū)檢測(cè)
在層次聚類(lèi)中，有兩種程序：聚合式（agglomerative）和分裂式（divisive）。本文聚焦的聚合式聚類(lèi)方法在每一步中將距離最近的兩個(gè)簇合并，直到最終只剩下一個(gè)節(jié)點(diǎn)，覆蓋整個(gè)數(shù)據(jù)集。
聚合式層次聚類(lèi)方法特別適用于僅定義了兩種成對(duì)距離函數(shù)的數(shù)據(jù)集劃分。一種距離函數(shù)用于衡量節(jié)點(diǎn)之間的距離，另一種用于根據(jù)節(jié)點(diǎn)間的距離衡量簇之間的距離，通常稱(chēng)為連接函數(shù)（linkage function）。文獻(xiàn)中存在多種連接函數(shù)（如最短距離、平均距離或UPGMA、Ward方法等）[48–50]。在本研究中，我們將聚焦于平均距離連接函數(shù)，原因?qū)⒃诮酉聛?lái)的段落中討論。
通常，層次聚類(lèi)方法處理的數(shù)據(jù)集可以看作是 R n 中的點(diǎn)。因此，一個(gè)經(jīng)典的選擇是使用歐幾里得距離來(lái)建模數(shù)據(jù)集中點(diǎn)之間的距離。節(jié)點(diǎn)聚類(lèi)的連續(xù)步驟可以用一種稱(chēng)為樹(shù)狀圖（dendrogram）的圖示表示。具體而言，在圖的一個(gè)坐標(biāo)軸上表示數(shù)據(jù)集的點(diǎn)，垂直坐標(biāo)軸上表示“高度”，即簇之間的距離。
由于 d 只定義在一個(gè)離散集合上，因此考慮使用輔助元素（如質(zhì)心）來(lái)計(jì)算簇之間距離的連接函數(shù)是沒(méi)有意義的。因此，在這種情況下，合適的連接函數(shù)選擇將是平均值（UPGMA，即非加權(quán)成對(duì)平均連接法）。
為了啟動(dòng)凝聚層次聚類(lèi)算法，每個(gè)初始簇將是一個(gè)包含一個(gè)節(jié)點(diǎn)的單元素集。在每一步中，將使用平均連接法計(jì)算簇之間的距離，即
3.2. 切割樹(shù)狀圖的一般標(biāo)準(zhǔn)：最大間隔切割
在指出切割樹(shù)狀圖的標(biāo)準(zhǔn)之前，正如在 [51] 中提到的，在凝聚層次聚類(lèi)中，當(dāng)在聚類(lèi)過(guò)程中不同簇之間的兩個(gè)或多個(gè)距離相同時(shí)，對(duì)于成對(duì)分組方法并不存在唯一性。解決這一缺點(diǎn)的常用方法是采用任意標(biāo)準(zhǔn)來(lái)打破距離之間的平局，這會(huì)導(dǎo)致根據(jù)所遵循的標(biāo)準(zhǔn)產(chǎn)生不同的層次排序。盡管可以考慮其他標(biāo)準(zhǔn)（例如在 [51] 中提出的在平局發(fā)生時(shí)同時(shí)合并兩個(gè)以上的簇），但在本文考慮的算法 1 中，使用內(nèi)部變量在不同簇之間的兩個(gè)或多個(gè)距離相同時(shí)給出的排序標(biāo)準(zhǔn)在計(jì)算上更為高效。
在任何情況下，在更廣泛的情境中，我們可以應(yīng)用一個(gè)標(biāo)準(zhǔn)來(lái)選擇樹(shù)狀圖的一個(gè)特定劃分。盡管這種方法沒(méi)有使用超圖的額外信息，但其結(jié)果可能足夠準(zhǔn)確，值得考慮。盡管它很簡(jiǎn)單，但這個(gè)標(biāo)準(zhǔn)是直觀的，值得解釋。
在凝聚層次聚類(lèi)中，每一步都會(huì)合并兩個(gè)不同的簇，以最小化簇之間的距離，這里將這種距離記作 D 。例如，在第一步中，它會(huì)尋找
3.3. 基于模塊性的樹(shù)狀圖切割標(biāo)準(zhǔn)
模塊性是傳統(tǒng)網(wǎng)絡(luò)分析中用于量化網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)或模塊化組織存在與否的概念。一個(gè)具有模塊性的網(wǎng)絡(luò)以節(jié)點(diǎn)劃分為不同的組或社區(qū)為特征，社區(qū)內(nèi)的節(jié)點(diǎn)彼此之間的連接比與其他社區(qū)的節(jié)點(diǎn)連接更為緊密。
對(duì)于成對(duì)網(wǎng)絡(luò)的模塊性，它衡量這種社區(qū)結(jié)構(gòu)的強(qiáng)度。它是一個(gè)介于 -1 到 1 之間的標(biāo)量值，更高的值表示更強(qiáng)的模塊化結(jié)構(gòu)。接近 1 的模塊性值表明社區(qū)之間的劃分非常清晰，而接近 0 或負(fù)值則表明社區(qū)結(jié)構(gòu)較為隨機(jī)或不夠明確。它定義為：
然而，到目前為止，對(duì)于超圖模塊性的定義尚未達(dá)成共識(shí)，因?yàn)橐延卸喾N方法通過(guò)使用（3.7）并基于超圖構(gòu)建某種成對(duì)鄰接矩陣來(lái)定義它。特別是，Kumar 等人 [47] 使用超圖的團(tuán)（clique）約簡(jiǎn)來(lái)定義超圖模塊性，并且由于從團(tuán)約簡(jiǎn)得到的圖中每個(gè)節(jié)點(diǎn)的度與超圖中的度不一致，他們還進(jìn)行了一些額外的調(diào)整。更具體地說(shuō)，他們定義了一個(gè)具有鄰接矩陣的圖：
因此，在這種方法中，我們將選擇最大化模塊性（使用公式 3.8）的劃分（由樹(shù)狀圖給出）。請(qǐng)注意，盡管導(dǎo)數(shù)圖（定義 2.4）為我們提供了一個(gè)鄰接矩陣，但我們不能用它來(lái)計(jì)算模塊性值，因?yàn)榭紤]到導(dǎo)數(shù)圖的定義，超圖中的一些節(jié)點(diǎn)可能會(huì)在導(dǎo)數(shù)圖中合并為新的節(jié)點(diǎn)。此外，導(dǎo)數(shù)的較小值意味著節(jié)點(diǎn)之間的相似性更高，而公式 3.8 中導(dǎo)數(shù)的較小值則意味著社區(qū)結(jié)構(gòu)更弱。此外，由于我們希望將我們的方法與 [47] 中的方法進(jìn)行比較，我們需要使用相同的鄰接矩陣來(lái)進(jìn)行這樣的比較。
迭代劃分。需要注意的是，根據(jù)對(duì)社區(qū)劃分細(xì)致程度的需求，算法2可以迭代地應(yīng)用于每個(gè)獲得的社區(qū)（考慮與它們相關(guān)的子超圖）。這通常會(huì)增加獲得的模塊性。
3.4. 其他方法：迭代加權(quán)模塊性最大化（IRMM）
在文獻(xiàn)中，已經(jīng)存在一種基于團(tuán)約簡(jiǎn)（3.8）的超圖社區(qū)檢測(cè)方法，該方法通過(guò)最大化模塊性來(lái)實(shí)現(xiàn)，即迭代加權(quán)模塊性最大化（Iteratively Reweighted Modularity Maximization, IRMM）算法。我們將在后續(xù)部分將其與我們的方法進(jìn)行比較，因此這里先簡(jiǎn)要概述。
IRMM算法的核心思想是在超圖 H 的團(tuán)約簡(jiǎn)圖上應(yīng)用Louvain算法，以獲得最大化模塊性的劃分。隨后，算法通過(guò)依賴于當(dāng)前劃分的重新加權(quán)函數(shù)重新計(jì)算超邊的權(quán)重。重新加權(quán)的目的是強(qiáng)調(diào)當(dāng)前聚類(lèi)能夠較好捕捉的超邊的重要性，并降低信息量較少的超邊的影響。通過(guò)迭代地重新加權(quán)超邊并最大化模塊性，IRMM算法旨在發(fā)現(xiàn)能夠最大化超圖社區(qū)結(jié)構(gòu)的劃分。迭代過(guò)程通過(guò)逐步調(diào)整超邊權(quán)重和節(jié)點(diǎn)分配，幫助細(xì)化聚類(lèi)結(jié)果。
4. 應(yīng)用與現(xiàn)實(shí)世界示例
現(xiàn)在我們已經(jīng)建立了兩種社區(qū)檢測(cè)算法（算法1和算法2）的理論基礎(chǔ)，接下來(lái)我們將轉(zhuǎn)向它們?cè)诤铣删W(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中的應(yīng)用，并與之前提出的社區(qū)檢測(cè)方法 [47] 進(jìn)行比較。
我們將首先將這些算法應(yīng)用于一個(gè)“手工設(shè)計(jì)”的超圖，在這個(gè)超圖中，通過(guò)簡(jiǎn)單的視覺(jué)檢查，我們可以預(yù)期兩種算法都能找到合理的劃分。隨后，我們使用一個(gè)真實(shí)且?guī)в袠?biāo)簽的小學(xué)學(xué)生數(shù)據(jù)集 [53, 54]，發(fā)現(xiàn)這些算法能夠以高精度預(yù)測(cè)節(jié)點(diǎn)標(biāo)簽（即個(gè)體所屬的班級(jí)）。最后，我們?cè)谶@一部分的結(jié)尾將這些算法應(yīng)用于一個(gè)更具異質(zhì)性的數(shù)據(jù)集——科學(xué)合作網(wǎng)絡(luò)。
所有數(shù)值模擬均在專(zhuān)用服務(wù)器（4.0 GHz Intel Xeon Gold 5220R）上進(jìn)行，數(shù)據(jù)和代碼可在以下鏈接獲取，以確保結(jié)果的可重復(fù)性： 。
4.1. 一個(gè)簡(jiǎn)單的玩具模型
為了實(shí)踐和討論前一節(jié)中引入和討論的想法，我們考慮了一個(gè)“玩具模型”，即一個(gè)預(yù)先設(shè)計(jì)好預(yù)期社區(qū)結(jié)構(gòu)的超圖。這個(gè)超圖包含14個(gè)節(jié)點(diǎn)（按字母順序標(biāo)記為字母）和21條超邊，如圖2所示。我們還展示了其導(dǎo)數(shù)圖對(duì)應(yīng)的樹(shù)狀圖。
通過(guò)一般方法（在最大間隔處切割樹(shù)狀圖），我們找到了以下劃分：
如果我們改用最大模塊性來(lái)劃分，得到的劃分結(jié)果是相同的（這意味著在最大間隔處切割樹(shù)狀圖可以得到具有最大模塊性的劃分，如圖2d所示），模塊性值為 Q = 0.34056 。
使用Kumar算法，我們發(fā)現(xiàn)了一組不同的社區(qū)：
很容易看出，這兩個(gè)劃分之間的唯一區(qū)別是，在第一個(gè)劃分中我們有一個(gè)額外的社區(qū) ，而在第二個(gè)劃分中，它被拆分到了社區(qū)中。鑒于社區(qū)檢測(cè)本身總是存在一定的主觀性（并且在這個(gè)人為設(shè)計(jì)的例子中沒(méi)有所謂的“真實(shí)情況”），這種差異是在合理范圍內(nèi)的。
在簡(jiǎn)單的例子中驗(yàn)證了一切如預(yù)期般運(yùn)行之后，我們現(xiàn)在轉(zhuǎn)向更現(xiàn)實(shí)的用例。
4.2. 用真實(shí)數(shù)據(jù)驗(yàn)證劃分結(jié)果
將社區(qū)檢測(cè)應(yīng)用于真實(shí)網(wǎng)絡(luò)時(shí)，面臨的一個(gè)主要問(wèn)題是：獲得的劃分是否“合理”。這種合理性通常來(lái)源于圖之外的信息，通常與所討論網(wǎng)絡(luò)的特征和/或數(shù)據(jù)中未用于構(gòu)建圖或超圖的信息或標(biāo)簽有關(guān)。
因此，為了驗(yàn)證所提出的方法，將其應(yīng)用于一個(gè)真實(shí)的數(shù)據(jù)集（而不是像前面的玩具模型那樣人為設(shè)計(jì)的）是很有意義的，這個(gè)數(shù)據(jù)集可能基于數(shù)據(jù)集的信息對(duì)獲得的社區(qū)有一些“普遍共識(shí)”。
為此，我們將分析法國(guó)里昂一所小學(xué)在兩天內(nèi)232名學(xué)生和10名教師之間的面對(duì)面互動(dòng)數(shù)據(jù) [53, 54]。該數(shù)據(jù)集包括10個(gè)不同的班級(jí)，每個(gè)年級(jí)（從一年級(jí)到五年級(jí)）各有2個(gè)班級(jí)。互動(dòng)是通過(guò)近距離傳感器測(cè)量的，每個(gè)傳感器都與一個(gè)組相關(guān)聯(lián)：對(duì)于學(xué)生是特定的班級(jí)，對(duì)于教師則是“教師”標(biāo)簽。因此，超圖由這242個(gè)節(jié)點(diǎn)組成，代表學(xué)生和教師，以及12699條超邊，這些超邊代表近距離傳感器在20秒時(shí)間框架內(nèi)捕獲的面對(duì)面互動(dòng)。
應(yīng)用算法1和算法2，我們得到了有意義的結(jié)果。使用基于高度的切割算法，我們識(shí)別出8個(gè)社區(qū)。其中6個(gè)分別對(duì)應(yīng)單獨(dú)的班級(jí)：1A、1B、2A、2B、4A和4B。剩下的兩個(gè)分別對(duì)應(yīng)3A與3B的合并，以及5A與5B的合并。需要注意的是，一些社區(qū)中包含來(lái)自其他班級(jí)的少數(shù)“異常值”，但絕大多數(shù)都屬于其同齡人。如果我們改用基于模塊性最大化的算法，我們會(huì)發(fā)現(xiàn)1A、1B、2A和2B會(huì)被合并在一起。
從這次分析中，我們可以得出兩個(gè)結(jié)論：從社區(qū)檢測(cè)的角度來(lái)看，這些算法能夠得出合理的分類(lèi)結(jié)果，因?yàn)樗鼈儯ㄌ貏e是基于高度的切割算法，在這個(gè)特定例子中）符合應(yīng)用于小學(xué)的社區(qū)檢測(cè)預(yù)期。從社會(huì)網(wǎng)絡(luò)的角度來(lái)看，這暗示了年幼的孩子可能跨越不同年級(jí)形成社區(qū)，而年長(zhǎng)的孩子則更多地按年齡分化。
在表1中可以找到對(duì)這個(gè)數(shù)據(jù)集應(yīng)用這兩種方法的更定量的比較。值得注意的是，盡管超圖中存在大量的超邊，基于高度的切割方法在社區(qū)檢測(cè)任務(wù)中表現(xiàn)得非常高效。而模塊性最大化方法受到構(gòu)建團(tuán)約簡(jiǎn)圖（3.8）的計(jì)算成本的限制，這是計(jì)算模塊性所必需的。
在真實(shí)數(shù)據(jù)集中驗(yàn)證了獲得的劃分結(jié)果的合理性之后，我們將轉(zhuǎn)向一個(gè)更具異質(zhì)性的數(shù)據(jù)集，以進(jìn)行最終比較，驗(yàn)證我們方法相對(duì)于文獻(xiàn)中已有的方法的優(yōu)勢(shì)。
4.3. 真實(shí)數(shù)據(jù)的進(jìn)一步結(jié)果
為了展示和比較我們的算法應(yīng)用于真實(shí)數(shù)據(jù)時(shí)的表現(xiàn)，我們考慮了斯特凡諾·博卡萊蒂（Stefano Boccaletti）教授的合著者網(wǎng)絡(luò)作為一個(gè)“試驗(yàn)場(chǎng)”來(lái)檢測(cè)社區(qū)。我們將首先描述該數(shù)據(jù)集的主要特征以及構(gòu)建超圖時(shí)所做的不同選擇。隨后，我們將對(duì)我們的算法進(jìn)行測(cè)試，并將其與其他已提出的算法進(jìn)行比較，就像我們之前對(duì)玩具模型所做的那樣。
數(shù)據(jù)集 我們構(gòu)建了一個(gè)初始的合作超圖，其中每個(gè)節(jié)點(diǎn)是一位與Boccaletti教授合作過(guò)的作者，每條超邊代表一篇科學(xué)出版物。數(shù)據(jù)來(lái)源是Scopus，總計(jì)有338篇出版物和413位合著者。
為了給超圖增加更多的結(jié)構(gòu)，我們加入了另一組數(shù)據(jù)，這次不包括Boccaletti教授，而是包含每位合著者的全部出版物（原則上可能包括從未與Boccaletti教授合作過(guò)的其他作者，但這些作者并未被納入超圖中）。因此，超圖得以擴(kuò)展，現(xiàn)在總共包含15237條超邊。
雖然我們的算法可以直接處理這個(gè)超圖，但我們發(fā)現(xiàn)，當(dāng)將其應(yīng)用于該超圖時(shí)，文獻(xiàn)[47]中提出的IRMM算法無(wú)法在合理時(shí)間內(nèi)收斂（在一臺(tái)配備4.0 GHz Intel Xeon Gold 5220R的專(zhuān)用服務(wù)器上運(yùn)行超過(guò)24小時(shí)）。為了比較兩種方法，我們決定根據(jù)以下標(biāo)準(zhǔn)對(duì)超圖進(jìn)行過(guò)濾：僅保留與Boccaletti教授有5篇或更多共同出版物的作者（即我們考慮頻繁合作的作者）。經(jīng)過(guò)過(guò)濾后的超圖包含67位作者，涉及他們之間和/或Boccaletti教授的1685篇出版物。
社區(qū)檢測(cè) 我們將四種方法（導(dǎo)數(shù)圖最大間隙切割、最大模塊度、迭代最大模塊度、IRMM）應(yīng)用于Stefano Boccaletti的合作者超圖。在展示實(shí)際分區(qū)結(jié)果（圖3）之前，讓我們先介紹每種方法的一些定量結(jié)果和指標(biāo)。
從表2可以清楚地看出，盡管在模塊度方面最佳的分區(qū)是IRMM方法得到的，但其計(jì)算成本并不值得這種微小的模塊度提升，其運(yùn)行速度比我們的最大模塊度方法慢了約320倍。還應(yīng)指出，IRMM能夠獲得最高的模塊度是可以預(yù)期的，因?yàn)檫@是一種專(zhuān)門(mén)設(shè)計(jì)用于優(yōu)化該分?jǐn)?shù)的算法，而其他方法并非如此。因此，令人印象深刻的是，通過(guò)簡(jiǎn)單地掃描樹(shù)狀圖中的個(gè)分區(qū)并選擇模塊度最大的一個(gè)，能夠如此高效地達(dá)到類(lèi)似的分?jǐn)?shù)（僅相差0.04）。需要注意的是，盡管IRMM和模塊度最大化都使用了團(tuán)縮減方法（在小學(xué)示例中代價(jià)較高，見(jiàn)前一小節(jié)），但由于超邊數(shù)量的減少，團(tuán)縮減的計(jì)算速度顯著加快。然而，IRMM的重新加權(quán)過(guò)程非常耗時(shí)，因?yàn)樗枰趫F(tuán)縮減圖上多次運(yùn)行Louvain算法[52]，這抵消了部分加速效果。
5. 結(jié)論
在本文中，我們提出了兩種用于檢測(cè)高階網(wǎng)絡(luò)社區(qū)（在超圖背景下）的方法，這些方法依賴于超圖的導(dǎo)數(shù)圖。通過(guò)多個(gè)例子和模擬實(shí)驗(yàn)表明，導(dǎo)數(shù)圖所誘導(dǎo)的節(jié)點(diǎn)相似性和半距離概念對(duì)于在聚合過(guò)程中獲得的簇之間建立連接距離特別有用。
通過(guò)多次模擬實(shí)驗(yàn)表明，盡管IRMM方法在模塊性方面給出了略微更好的劃分結(jié)果，但本文提出的方法在效率和計(jì)算成本方面更具優(yōu)勢(shì)。第一種方法是識(shí)別樹(shù)狀圖中分支之間的最大距離。這種算法不僅速度最快，而且效率最高，因?yàn)樗軌蜻_(dá)到非常高的模塊性值，接近IRMM的結(jié)果。此外，IRMM在計(jì)算上要昂貴得多，并且在其中一個(gè)例子中，它無(wú)法在合理的時(shí)間內(nèi)完成所需的計(jì)算。另一方面，本文提出的第二種方法在模塊性方面有所改進(jìn)，盡管它增加了額外的計(jì)算成本，但這種成本與IRMM相比微不足道，IRMM雖然能夠產(chǎn)生略微更好的模塊性值，但其計(jì)算成本顯著更高。
原文鏈接： https://doi.org/10.1016/j.chaos.2023.114200
熱門(mén)跟貼