陳可佳，陳利明，吳 桐

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

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

1 引言

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

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

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

2 多層網(wǎng)絡

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

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

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

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

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

Fig.1 Example of multiplex network圖1 多路網(wǎng)絡示例

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

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

Fig.2 Example of temporal network圖2 時間網(wǎng)絡示例

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

Fig.3 Example of interactive network圖3 交互網(wǎng)絡示例

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

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

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

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

在上述多層網(wǎng)絡中，對于多路網(wǎng)絡的研究最為廣泛。本文調研的多層網(wǎng)絡社區(qū)發(fā)現(xiàn)方法大多面向多路網(wǎng)絡，但也可以用于大部分其他類型的多層網(wǎng)絡中。

3 傳統(tǒng)社區(qū)發(fā)現(xiàn)方法

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

（1）圖劃分方法

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

（2）基于模塊度的方法

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

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

（3）譜方法

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

（4）基于動力學的方法

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

（5）重疊社區(qū)發(fā)現(xiàn)方法

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

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

本文在傳統(tǒng)單層網(wǎng)絡社區(qū)發(fā)現(xiàn)研究的基礎上，重點考察多層網(wǎng)絡中的社區(qū)發(fā)現(xiàn)方法。

4 多層網(wǎng)絡社區(qū)發(fā)現(xiàn)方法

根據(jù)多層網(wǎng)絡的類型及其應用場景，社區(qū)發(fā)現(xiàn)的目標可以是結合其他層的信息對每一層網(wǎng)絡分別進行社區(qū)劃分，也可以是融合多層網(wǎng)絡的信息獲得節(jié)點的唯一社區(qū)劃分結果。

本文調研了已有的多層網(wǎng)絡社區(qū)發(fā)現(xiàn)方法，根據(jù)方法的實現(xiàn)機制大致分為兩類：基于聚合的方法和基于擴展的方法。

4.1 基于聚合的方法

基于聚合的多層網(wǎng)絡社區(qū)發(fā)現(xiàn)方法又分為兩種：第一種稱為網(wǎng)絡聚合，是將多層網(wǎng)絡直接聚合成一個單層網(wǎng)絡，然后應用傳統(tǒng)的方法進行社區(qū)發(fā)現(xiàn)；第二種稱為劃分聚合，是在每層網(wǎng)絡上分別進行單層社區(qū)發(fā)現(xiàn)，再將所有層的社區(qū)劃分結果進行聚合。這兩種聚合方法均只得到節(jié)點的一種社區(qū)劃分結果。

4.1.1 網(wǎng)絡聚合

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

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

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

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

4.1.2 劃分聚合

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

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

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

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

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

4.2 基于擴展的方法

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

4.2.1 基于多層模塊度的方法

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

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

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

盡管基于多層模塊度的方法能有效地對多層網(wǎng)絡進行社區(qū)發(fā)現(xiàn)，但是設置的參數(shù)較多，計算復雜性較高，不太適用于大規(guī)模網(wǎng)絡數(shù)據(jù)。

4.2.2 基于多層聚類的方法

第二類方法是將單層網(wǎng)絡中基于節(jié)點聚類的社區(qū)發(fā)現(xiàn)方法擴展到多層網(wǎng)絡。

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

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

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

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

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

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

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

4.2.3 基于張量分解的方法

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

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

4.2.4 基于多層動力學的方法

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

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

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

表2是本文對目前已有的16種多層網(wǎng)絡社區(qū)發(fā)現(xiàn)方法的總結，主要從實現(xiàn)機制、層間相關性、優(yōu)點、局限性、適用網(wǎng)絡、算法復雜性等方面進行了分析和比較。

Table 2 Comparison of multi-layer network community discovery methods表2 多層網(wǎng)絡社區(qū)發(fā)現(xiàn)方法的比較

5 性能比較實驗

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

5.1 數(shù)據(jù)集

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

Table 3 Statistics of datasets表3 數(shù)據(jù)集的統(tǒng)計信息

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

5.2 比較方法與評價指標

本文對5 個具有代表性的多層網(wǎng)絡社區(qū)發(fā)現(xiàn)方法進行驗證，分別為：網(wǎng)絡聚合方法（Aggregation）[25]、PMM[26]、多層模塊度（modularity quantity of multislice，Q-MS）[28]、CLECC[30]、M-Infomap[38]。此外，還增加了各方法的基準方法作為對比?；鶞史椒ㄊ侵覆豢紤]層間交互，對每一層網(wǎng)絡社區(qū)劃分的結果求平均。

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

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

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

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

5.3 實驗結果

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

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

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

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

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

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

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

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

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

6 結束語

本文系統(tǒng)性地介紹了多層網(wǎng)絡社區(qū)發(fā)現(xiàn)的研究現(xiàn)狀，總結了已有方法的特點，并通過實驗對代表性方法的性能進行驗證和比較。

盡管多層網(wǎng)絡社區(qū)發(fā)現(xiàn)已經(jīng)引起了越來越多的關注，但由于網(wǎng)絡數(shù)據(jù)在類型、規(guī)模、演變方面的復雜性，目前該領域仍然存在諸多的挑戰(zhàn)。主要體現(xiàn)在以下三方面。

（1）如何更好地學習網(wǎng)絡結構和層間關系

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

（2）如何提高可擴展性，以適應大規(guī)模網(wǎng)絡

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

（3）如何適應動態(tài)變化的多層網(wǎng)絡

網(wǎng)絡在不斷動態(tài)變化，節(jié)點的社區(qū)結構也應不斷調整。大部分已有的方法是針對靜態(tài)網(wǎng)絡設計，有些方法[44-45]是將單層動態(tài)網(wǎng)絡轉化為多層網(wǎng)絡來學習社區(qū)結構，但是針對動態(tài)的多層網(wǎng)絡社區(qū)發(fā)現(xiàn)方法目前還很欠缺。