多層網絡社區發現研究綜述*

陳可佳，陳利明，吳 桐

1.南京郵電大學 計算機學院，南京 210023

2.江蘇省大數據安全與智能處理重點實驗室，南京 210023

1 引言

社區是復雜網絡的一個顯著特征，即網絡中的節點呈現出組（group）或者簇（cluster）的結構[1]。一般來說，社區內部節點之間的連接較緊密而社區與社區之間的連接較稀疏。社區發現是復雜網絡分析的重要任務之一，有助于理解網絡的內在結構和交互模式，已被廣泛應用于社會學[2]、生物學[3]、計算機工程學[4]等領域。例如，在社交網絡中，社區發現有助于分析個體的行為模式、信息的傳播方式和網絡的變化趨勢[5]；在生物網絡中，社區發現能夠幫助分析蛋白質相互作用的不同復雜功能[6]；在城市交通網絡中，社區發現有助于從地區之間的交通線路分析城市的影響力[7]。

傳統的社區發現算法[8-9]大多用于單層網絡，即網絡中的節點之間僅存在單一的關系。經典的方法包括：圖劃分方法[10]、基于模塊度的方法[11]、譜方法[12]、結構定義方法[13]等。然而，現實世界的網絡往往是多層的，即節點之間可能存在多種類型的關系，每一種關系構成了一層網絡。例如：社交網絡中的用戶之間不僅存在朋友關系，還可能存在評論關系、轉發關系等。面向多層網絡的社區發現逐步成為了復雜網絡分析的新課題[14]。

在多層網絡中發現社區的最原始做法是直接忽略關系的類型，即將多層網絡視為一個單層網絡，然后采用傳統方法實現社區的劃分。不過，此類方法損失了單層網絡的結構信息，也忽視了層間的相關性，難以獲得理想的劃分結果。因此，多層網絡社區發現的主要挑戰是如何在社區發現過程中同時學習每層網絡的結構信息以及層與層之間的相關性。

2 多層網絡

定義1（單層網絡）一個單層網絡[15]可以形式化為圖G=（V，E）。其中，V是節點的集合，E?V×V是連接節點對的邊的集合。

然而，現實網絡的節點之間通常呈現出多種交互關系。例如Facebook 網絡中，用戶之間存在關注、評論、轉發等不同的交互類型。單層網絡只能粗略近似這類系統，多層網絡則可以進行更準確的建模。

定義2（多層網絡）一個多層網絡可以定義為GM={G1，G2，…，GL，EM}。L是總層數，EM是層與層之間邊的集合，Gl=（Vl，El）是第l層的網絡，其中第l層的節點集合Vl?V（V={v1，v2，…，vN}，即多層網絡中所有節點的集合），El?Vl×Vl，是第l層網絡中邊的集合。

許多復雜網絡都可以視為多層網絡，例如：多路網絡、時間網絡、交互網絡、多維網絡等。

定義3（多路網絡）多路網絡（multiplex network）有時也稱為多重網絡，是指所有層共享相同節點的多層網絡，即V1=V2=…=VL=V（V={v1，v2，…，vN}）。圖1是一個多路網絡示意圖，每一層表示節點之間的一種關系，層間的虛線表示不同層的節點是對齊的。

Fig.1 Example of multiplex network圖1 多路網絡示例

現實世界存在大量的多路網絡，例如：社交網絡（用戶之間存在關注、評論、轉發等不同的交互）、航線網絡（機場之間存在多個航空公司的航線）等。

定義4（時間網絡）時間網絡（temporal network）是用于表示動態網絡每個時間快照的多層網絡（見圖2），定義為GM=（G1，G2，…，GT，EM）。其中，Gt是t時刻的網絡圖，Gt=（Vt，Et）。層間邊EM={Et，t+1}（Et，t+1={（v，v）；v∈Vt∩Vt+1}）。

Fig.2 Example of temporal network圖2 時間網絡示例

定義5（交互網絡）交互網絡（interacting network）是指不同層之間存在相互作用的多層網絡。其中，每個節點最多只存在于一層網絡中，即對于任意兩層網絡Gi和Gj（i，j∈[1，L]且i≠j），Vi∩Vj=?。層間邊集合EM={Ei，j}（Ei，j={（vi，vj）；vi∈Vi，vj∈Vj}） 。城市交通網絡是一個典型的交互網絡（圖3），每個省及其內部城際交通可視為交互網絡中的一層，兩省之間的交通路線為層間的交互，反映了兩省之間的相互影響力。

Fig.3 Example of interactive network圖3 交互網絡示例

此外，具有以下稱謂的復雜網絡也可視為多層網絡，如：多維網絡（multi-dimensional network）[16]、多關系網絡（multi-relational network）[17]、多尺度網絡（multi-scale network）[18]、異質信息網絡（heterogeneous information network）[19]等。

表1 列舉了各類多層網絡在各層節點是否對齊（所有層共享相同的節點）、層間有無邊以及層間邊是否耦合（即每層對齊節點之間存在邊）的情況。

多層網絡能夠更好地表示真實世界網絡的拓撲結構，多層信息的融合能夠大大提升復雜網絡分析模型的性能。例如，將社交網絡建模為多層網絡能夠更準確地劃分社區和預測新的關系；將蛋白質網絡建模為多層網絡，能夠找到更有效的蛋白質劃分方法，發現潛在的蛋白質相互作用；將動態網絡按時間片轉換為多層網絡，能學到時間序列信息，獲得更準確的節點嵌入。

Table 1 Characteristics of different types of multi-layer networks表1 不同類型多層網絡的特點

在上述多層網絡中，對于多路網絡的研究最為廣泛。本文調研的多層網絡社區發現方法大多面向多路網絡，但也可以用于大部分其他類型的多層網絡中。

3 傳統社區發現方法

社區是復雜網絡中廣泛存在的結構。從拓撲結構的角度來看，社區是指一個內部連接緊密但和外部連接稀疏的子網；從信息論的角度來看，社區是指可以在相當長時間內限制信息流的模塊；從機器學習的角度來看，社區可以類比為無監督聚類中的簇。社區發現研究有助于人們理解網絡的內在結構和交互模式，傳統方法主要面向單層網絡設計，包括圖劃分方法、基于模塊度的方法、譜方法和基于動力學的方法等[1]，以及同一節點可能屬于不同社區的重疊社區發現方法[20]。這些方法是多層網絡社區發現的基礎。

（1）圖劃分方法

圖劃分的目標在于將節點劃分成k個組，使得組間邊的總數（也稱為切割總數）最小。K-L（Kernighan-Lin）[21]算法是最早的圖劃分方法之一，基本思想是先定義一個效益（gain）函數fG，表示社區內部邊的總數和社區之間邊的總數之差。設定隨機的初始劃分后，在不同社區之間互換數量相同的節點，直到fG具有最大的增量為止。

（2）基于模塊度的方法

基于模塊度的方法通過節點劃分使得模塊度（modularity）的值最大。Girvan 和Newman[2]最先給出模塊度Q的定義（式（1）），即社區內的邊占所有邊的比例減去在同樣的社區結構下隨機放置社區內部的邊占所有邊的比例的期望值。

其中，ki和kj分別表示節點vi和節點vj的度，A是鄰接矩陣，m是圖中邊的總數，δ（i，j）表示節點vi和vj是否在同一個社區（值為1 表示在，0 表示不在）。社區發現的過程就是模塊度優化的過程，可采用貪婪算法、模擬退火算法、極值優化等策略。經典的模塊度優化方法有GN（Girvan Newman）算法[2]以及適用于大規模網絡的改進算法FN（fast Newman）[22]等。

（3）譜方法

譜方法利用圖矩陣的譜特性來劃分社區，認為特征向量越相似的節點越有可能在同一個社區。譜聚類（spectral clustering）[23]是其中最有代表性的方法，它利用節點在拉普拉斯矩陣對應的特征向量生成空間坐標，將節點映射到多維向量空間中，然后通過kmeans 等傳統聚類方法對節點進行聚類，從而得到社區劃分結果。

（4）基于動力學的方法

基于動力學的方法是通過網絡動態過程（如隨機游走力學）來劃分社區。Infomap[24]是目前通過隨機游走進行社區發現的一種有效方法，首先將每個節點當作獨立的社區，通過構造轉移概率，在圖上進行隨機游走生成序列，再對序列進行層次編碼，最小化平均編碼長度直到收斂為止。對社區編碼的長度越短，社區劃分的效果越好。

（5）重疊社區發現方法

上述方法檢測到的社區均是不重疊的，即每個節點只被分配給一個社區。然而現實網絡中，節點可以屬于多個不同團體，因此出現了一系列重疊社區發現的工作[20]。如Palla 等人[25]基于團（clique）的概念提出團滲透法（clique percolation method，CPM），Lancichinetti 等人[26]提出的局部適應度最大化（local fitness maximization，LFM）方法，Ahn 等人[18]提出的基于邊聚類的重疊社區發現方法以及擴展了標簽傳播算法（label propagation algorithm，LPA）的重疊社區發現方法CORPA（community overlap propagation algorithm）方法[27]和SLPA（speaker-listener label propagation algorithm）方法[28]。

不過，社區發現研究依然存在許多問題，包括：大部分方法的算法復雜度較高，難以處理大規模網絡；有些方法（如基于模塊度的方法）存在分辨率敏感的問題，難以在小規模網絡上準確劃分社區；有些方法（如譜方法）在稀疏網絡上表現較差；許多方法需要預先設定社區的數量，難以適用于動態網絡；大多數方法面向單層網絡，而多層網絡社區發現方法相對較少等。

本文在傳統單層網絡社區發現研究的基礎上，重點考察多層網絡中的社區發現方法。

4 多層網絡社區發現方法

根據多層網絡的類型及其應用場景，社區發現的目標可以是結合其他層的信息對每一層網絡分別進行社區劃分，也可以是融合多層網絡的信息獲得節點的唯一社區劃分結果。

本文調研了已有的多層網絡社區發現方法，根據方法的實現機制大致分為兩類：基于聚合的方法和基于擴展的方法。

4.1 基于聚合的方法

基于聚合的多層網絡社區發現方法又分為兩種：第一種稱為網絡聚合，是將多層網絡直接聚合成一個單層網絡，然后應用傳統的方法進行社區發現；第二種稱為劃分聚合，是在每層網絡上分別進行單層社區發現，再將所有層的社區劃分結果進行聚合。這兩種聚合方法均只得到節點的一種社區劃分結果。

4.1.1 網絡聚合

基于網絡聚合的方法主要是為新聚合網絡中節點間的邊賦予新的權重，主要有兩種基本策略：一種是當任意兩個節點u、v之間至少在一層網絡中存在邊，則聚合網絡的鄰接矩陣中u、v之間的連接值設為1；另一種是對鄰接矩陣進行加權，u、v之間的連接權值設為它們在所有層上存在邊的總數，即。這兩種聚合策略最為基礎，一般作為比較實驗的基線方法。

Berlingerio 等人[29]基于共同鄰居數越多節點越可能處于同一社區的想法，提出了基于共同鄰居數的多層鄰接矩陣加權策略。該策略中，的計算如下：

其中，N?，l是某個節點在l層上的鄰居數量。此外，還有其他的加權聚合策略，如基于度中心性（degree centrality）的方法等，但與式（2）相比計算復雜度較高。

不過，上述方法忽略了不同層網絡具有不同的重要程度。Zhu 等人[30]定義了每層網絡的重要性，如果某層網絡的重要性越高，則該層的信息對其他層的影響越大。該方法采用層重要性和節點相似度得到統一的矩陣，再用單層網絡社區發現方法得到最終的劃分結果。

4.1.2 劃分聚合

基于劃分聚合的方法主要包括主模塊度最大化（principal modularity maximization，PMM）[31]、共識聚類[32]、ABACUS[33]等。

Tang 等人[31]提出PMM 方法。該方法包括兩步：第一步是提取每層網絡的模塊度矩陣的特征向量并獲得級聯的向量，然后采用PCA（principal component analysis）得到一個較低維的嵌入，捕獲網絡所有維度（層）上的主模式；第二步是對所有節點的低維嵌入表示執行k-means算法，以找出離散的社區劃分。

共識聚類（consensus clustering）[32]方法先對每層網絡進行社區劃分，然后計算一個共識矩陣A，矩陣的元素為兩個節點處于同一社區劃分的網絡層數。例如，兩個節點在兩層網絡上都在同一個社區，那么Aij就為2。最后通過共識矩陣不斷聚合不同層網絡的社區，直到得到一個統一的社區劃分。

ABACUS[33]是另一種基于劃分聚合的方法，首先使用傳統的社區發現方法在每層網絡上分別檢測社區，然后將每個節點標記為由層號ls及其在該層網絡上所屬的社區Cs，k組成的項（ls，Cs，k），最后應用頻繁閉項集挖掘算法進行合并，得到最終的社區劃分結果。

不過，由于每一層網絡中節點之間的交互方式都是不同的，簡單地聚合網絡數據或者劃分結果將會丟失每層網絡的獨特性。例如：基于網絡聚合的方法可能會丟失每層網絡的部分結構信息，而基于劃分聚合的方法則忽視了不同層社區存在異質性。因此，越來越多的研究者嘗試對傳統方法進行擴展，以直接用于多層網絡的社區發現。

4.2 基于擴展的方法

基于擴展的方法是指將單層網絡的社區發現方法直接擴展到多層網絡，這是目前多層網絡社區發現的主流方向。本文將該類方法分為以下幾種：基于多層模塊度的方法、基于多層聚類的方法、基于張量分解的方法和基于多層動力學的方法。

4.2.1 基于多層模塊度的方法

Mucha 等人[34]通過定義多層模塊度來檢測多層網絡中的社區。多層模塊度Qmultislice定義如下：

其中，As表示第s層網絡的鄰接矩陣，Cjsr表示節點vj在s層和r層之間的耦合邊，表示節點vj在第s層上的度，表示第s層上的總邊數，表示節點j跨越不同層的度；γs為分辨率以控制每層網絡的社區規模和數量，如果節點vi和節點vj的社區分布相同，則δ（gis，gir）=1，否則為0。優化該函數進行復合社團挖掘，即每一層網絡得到一個劃分結果。

在此基礎上，Ma 等人[35]進一步提出了多層模塊度密度（式（4）），以解決模塊度的分辨率限制問題。定義如下：

盡管基于多層模塊度的方法能有效地對多層網絡進行社區發現，但是設置的參數較多，計算復雜性較高，不太適用于大規模網絡數據。

4.2.2 基于多層聚類的方法

第二類方法是將單層網絡中基于節點聚類的社區發現方法擴展到多層網絡。

Bródka 等人[36]提出了利用跨層邊聚類系數（cross layered edge clustering coefficient，CLECC）檢測多層社交網絡中的社區，最終每層網絡分別得到一個社區劃分結果。該方法的思想是，節點之間的多層共同鄰居數量越多，節點越可能在同一社區。CLECC的定義如式（6），表示為任意節點u和v（u，v∈V）的共同多層鄰居數與所有多層鄰居數之間的比例。

其中，Φ（?，α）表示給定節點在至少α層上的鄰居集合，α參數值可以根據網絡的密度差異進行調整。

Hmimida等人[37]將單層網絡社區發現方法Licod[38]擴展到多層網絡，命名為Mux-Licod，利用多層網絡的信息獲得節點的唯一社區劃分結果。Licod 的基本思想是找到稱為種子的特定節點，圍繞這些節點逐步發現社區。與Licod 類似，Mux-Licod 首先尋找若干領袖節點，即比大多數直接鄰居具有更高度中心性的節點；然后對所有的領袖節點進行聚類，獲得初始社區的集合；再計算任一節點到任意社區的所有領袖節點的多層最短路徑（式（7））來估計該節點到該社區的隸屬度；最后，用秩聚合（rank aggregation）函數合并相鄰節點的社區隸屬度得到最終的社區劃分結果。

Alimadadi等人[39]擴展了單層標簽傳播算法（LPA），得到了多層LPA。方法首先為所有節點指定一個唯一的標簽，然后逐輪更新節點的標簽，直到收斂。節點標簽的更新規則是：對于某一個節點，統計其所有的跨層鄰居節點（式（8））的標簽，將出現個數最多的標簽賦給當前節點。當個數最多的標簽不唯一時，則進行隨機選擇。

其中，Γ（i）total是節點vi在所有層上的鄰居的集合，σ∈[0，1]是相似度閾值，sim（?）是可選的相似度函數（如Jaccard 相似性度量等）。

Afsarmanesh 和Magnani[40]將單層網絡社區發現方法CPM[25]擴展到多層網絡。該方法首先針對多層網絡定義了k-m-AND-clique，表示具有k個節點的多層網絡中的子圖，該子圖包括來自m個不同層的至少m個不同的k-clique（大小為k的完全子圖）的組合；然后將每個k-m-AND-clique 看作一個節點，如果兩個cliques 之間至少共享k-1 個節點和m條邊，則把它們連接起來。如果這些連通的cliques 之間至少共享m條邊，則它們至少在一個社區中。

Interdonato等人[41]提出了一種多層網絡上的局部社區發現方法ML-LCD（multi-layer local community detection）。在全局信息未知的情況下，通過優化局部社區函數（即內部鏈接密度和外部鏈接密度比）標識特定節點所在的社區。最后通過將特定層的貢獻值與鏈接密度比進行線性組合將局部社區函數擴展到多層網絡。

4.2.3 基于張量分解的方法

非負矩陣分解的思想已被用于單層網絡社區發現[42-43]。相應地，有研究者采用張量（tensor）表示和分析多層網絡的譜特性，并提出了基于張量分解的社區發現方法[44-45]，用于得到唯一的社區劃分結果。Esraa 等人[44]提出了一種基于張量的時域多層網絡社區檢測算法，用于識別和跟蹤腦網絡社區的結構。該框架研究跨不同興趣區域（region of interest，ROI）構建的fMRI（functional magnetic resonance imaging）連接網絡中社區的時間演變，使用張量的Tucker 分解找到最能描述社區結構的子空間。

Gauvin 等人[45]將時間網絡的時變鄰接矩陣表示為三向張量，將該張量近似為具有相關活動時間序列的節點社區的項之和，然后利用非負張量因子分解技術提取時間網絡的社區活動結構。

4.2.4 基于多層動力學的方法

M-Infomap[46]是一種基于網絡流壓縮的方法，是Infomap 方法[24]在多層網絡的擴展。該方法首先將多層網絡表示為具有狀態節點的多路復用網絡，然后在網絡中放置隨機游走者，構造轉移概率，在圖上進行層內或層間隨機游走生成序列，再對序列進行層次編碼，最小化平均編碼長度直到收斂為止。該方法最終為每一層網絡得到一種社區劃分結果。

LART（locally adaptive random transitions）[47]是另一種基于隨機游走的方法，該方法允許游走者走到多層網絡中的其他層，隨機游走的轉移概率取決于任意給定節點所在層之間的局部拓撲相似性。當在單層網絡中游走時，LART 就會退化為經典的Walktrap[48]算法。

綜上所述，在已有的多層網絡社區發現方法中，一部分方法旨在得到節點的最終社區劃分結果，如基于聚合的方法（PMM，ABACUS）、基于張量分解的方法等；另一部分方法則是為每層網絡得到各自的劃分結果，如基于多層模塊度的方法、基于多層聚類的方法（CLECC、Mux-Licod）、基于動力學的方法MInfomap 等。事實上，每層網絡一個社區劃分意味著節點可以屬于多個不同類型的社區。因此，這一系列的方法也可用于節點的重疊社區劃分。然而，多層網絡中的每一層也可能存在重疊的社區結構，目前這一方面的工作還很欠缺。本文僅調研到Ebrahimi等人[49]提出的基于多目標函數優化的多層網絡重疊社區發現方法。

表2是本文對目前已有的16種多層網絡社區發現方法的總結，主要從實現機制、層間相關性、優點、局限性、適用網絡、算法復雜性等方面進行了分析和比較。

Table 2 Comparison of multi-layer network community discovery methods表2 多層網絡社區發現方法的比較

5 性能比較實驗

本文在11 個真實的多層網絡數據集以及1 個模擬的多層網絡數據集上對5 個代表性方法及其基準方法進行了驗證和比較。

5.1 數據集

各數據集的節點、邊和層數的統計信息見表3。其中，所有真實數據集分別來自兩個多層網絡數據集網站（https：//comunelab.fbk.eu/data.php 和http：//multilayer.it.uu.se/datasets.html），包含了不同類型、規模、層數和密集度的網絡。最后一個數據集SLDS（simulated dataset 的縮寫）是本文使用Bazzi 等人[50]提出的算法構造的模擬數據集。

Table 3 Statistics of datasets表3 數據集的統計信息

Florentine 網絡描述了佛羅倫薩市名門望族之間存在的關系，節點表示家族，層數表示商業關系和婚姻關系。Tailorshop 網絡中節點為裁縫店的工人，關系為他們之間的工作和友誼互動。Aucs 數據集描述某大學研究部門的61 名員工節點（包括教授、博士后、博士生和行政人員）之間的Facebook 關系、午餐關系、合作關系、休閑關系和工作關系。Fao Trade 是FAO（聯合國糧食及農業組織）統計的世界各國食品進出口網絡，其中節點表示國家，邊表示各國的進出口貿易關系。Ckmpims 數據集由美國4 個城鎮的246名醫生組成，主要討論網絡關系對醫生用藥決策的影響，三層網絡包括：（1）通常找誰獲取用藥建議；（2）經常與誰討論；（3）與誰關系最好。London Transport 是倫敦市的交通網絡，根據站點之間的連通方式分為三層：（1）地下通路；（2）地上通路；（3）DLR。Euair 數據集是歐洲航空交通網絡，每層表示不同航線。Pierreauger 數據集表示了天文臺科學家之間的協作關系，每一層代表一種協作任務。Ff-Tw-Yt數據集來自于Friendfeed 社交媒體，用戶節點之間存在發布消息、評論消息等多種關系。Drosophila 是果蠅的基因遺傳交互網絡，每一層表示一種遺傳交互方式。ArXiv 是研究主題為networks 的協作網絡，每一種研究類別代表一層網絡。

5.2 比較方法與評價指標

本文對5 個具有代表性的多層網絡社區發現方法進行驗證，分別為：網絡聚合方法（Aggregation）[25]、PMM[26]、多層模塊度（modularity quantity of multislice，Q-MS）[28]、CLECC[30]、M-Infomap[38]。此外，還增加了各方法的基準方法作為對比。基準方法是指不考慮層間交互，對每一層網絡社區劃分的結果求平均。

在社區發現領域，常用的評價指標有標準化互信息（normalized mutual information，NMI）[51]、模塊度（modularity）[2]和調整蘭德系數（adjusted Rand index，ARI）[52]等。當數據集真實的社區劃分（即groudtruth）已知時，可以使用NMI 指標（式（9））和ARI 指標（式（10））來評價社區劃分結果。當數據集中真實的社區結果未知時，本文采用多層網絡模塊度[34]作為方法的評價指標。

其中，P（wk）、P（cj）、P（wk?cj）分別表示樣本屬于聚類簇wk、cj和同時屬于兩者的概率。

其中，ai表示樣本屬于a聚類簇第i類的數量，bj表示樣本屬于b聚類簇第j類的數量，nij表示樣本同時屬于a聚類簇第i類和b聚類簇第j類的數量。

對于多層網絡社區發現，可以采用類似的評價方法。由于有些方法是每層網絡得到一個劃分結果，對此本文是將各層的指標取均值得到最終的結果。

5.3 實驗結果

圖4 展示了5種方法在模擬數據集上的NMI 和ARI 比較。圖中表明，Q-MS 和M-Infomap 兩個方法的社區劃分效果較好，它們直接在多層網絡上劃分社區，能夠充分利用層間的關系；PMM 方法是對各層的劃分結果進行聚合，未能很好利用層間相關性，效果不如前兩者；CLECC 方法使用啟發式的多層共同鄰居數進行聚類，其效果依賴于網絡的自身特性；Aggregation 方法表現最差，說明網絡聚合方法丟失了最多的信息。

Fig.4 Comparison of NMI and ARI of various methods on simulated dataset圖4 各方法在模擬數據集上的NMI和ARI比較

隨后，本文在真實的數據集上對各方法在多層模塊度Qmultislice指標上的表現進行了比較（見表4）。表中的加粗數字表示性能最優，下劃線數字表示性能次優。結果表明，Q-MS 和M-Infomap 在不同規模的數據集上的總體表現依然最優；PMM 在小規模稠密網絡中的劃分效果更好，但在大規模稀疏網絡中的效果較差；CLECC 的表現最不穩定，說明該方法對于網絡類型的依賴程度較高。

圖5 對比了各方法及其基準方法在Ff-Tw-Yt 數據集上的多層模塊度指標值。

Table 4 Comparison of Qmultislice of various methods on datasets表4 各方法在數據集上的多層模塊度比較

Fig.5 Comparison of Qmultislice of various methods on Ff-Tw-Yt dataset圖5 各方法在Ff-Tw-Yt數據集上的多層模塊度比較

結果表明，與未考慮層間相關性的基準方法相比，每種方法的多層模塊度指標都有了顯著提高，說明學習層間相關性對多層網絡社區發現的性能至關重要。其中，Q-MS 和M-Infomap 方法的提升幅度最為明顯，說明這兩種方法能較好地學到層間相關性。

最后，本文比較了各方法在Ff-Tw-Yt 數據集上的運行時間（見圖6）。其中，Aggregation 方法是將多層聚合為一層之后再進行社區發現，大大簡化了網絡結構，因此運行最快；Q-MS 通過計算節點分配社區后的模塊度增益來優化目標函數，收斂也較快；PMM 通過PCA 對特征向量降維，可有效減少聚類時間；M-Infomap 通過隨機游走來捕獲層內和層間的信息流，時間復雜度較高；CLECC 通過刪除邊聚集系數最小的邊來獲得層級結構，每次刪除之后需要重新計算各邊的系數，因此時間復雜度非常高。

Fig.6 Comparison of running time of various methods on Ff-Tw-Yt dataset圖6 各方法在Ff-Tw-Yt數據集上的運行時間比較

6 結束語

本文系統性地介紹了多層網絡社區發現的研究現狀，總結了已有方法的特點，并通過實驗對代表性方法的性能進行驗證和比較。

盡管多層網絡社區發現已經引起了越來越多的關注，但由于網絡數據在類型、規模、演變方面的復雜性，目前該領域仍然存在諸多的挑戰。主要體現在以下三方面。

（1）如何更好地學習網絡結構和層間關系

已有的方法直接使用網絡的拓撲結構信息（例如多層鄰居、多層模塊度、跨層隨機游走等），其性能嚴重依賴于網絡的類型，而且是啟發式地學習層間關系。目前，隨著網絡表示學習技術（特別是圖神經網絡[53]）的興起，節點的自動嵌入技術能夠為多層網絡社區發現帶來新的思路。

（2）如何提高可擴展性，以適應大規模網絡

大部分已有方法（如基于張量分解的方法）的復雜性較高，難以擴展至大規模網絡。最近有方法采用粗化策略并保持原始的社區效應，用于在大規模多層網絡中發現社區，具有一定的可行性[54]。此外，圖池化[55]方法也能起到類似的作用。

（3）如何適應動態變化的多層網絡

網絡在不斷動態變化，節點的社區結構也應不斷調整。大部分已有的方法是針對靜態網絡設計，有些方法[44-45]是將單層動態網絡轉化為多層網絡來學習社區結構，但是針對動態的多層網絡社區發現方法目前還很欠缺。