王飛程 周鈺穎 閔 勇

(浙江工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 浙江 杭州 310023)

0 引 言

網(wǎng)絡(luò)中鏈路預(yù)測的目標是根據(jù)已知的網(wǎng)絡(luò)信息預(yù)測丟失或潛在的鏈路。鏈路預(yù)測有著廣泛的關(guān)注和應(yīng)用，例如：在生物學(xué)領(lǐng)域，其可以預(yù)測基因網(wǎng)絡(luò)和蛋白質(zhì)網(wǎng)絡(luò)中的隱藏關(guān)系，有助于提高實驗成功率，開辟藥物開發(fā)的新途徑；在復(fù)雜網(wǎng)絡(luò)分析中，其可以用作準確分析復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的強大補充工具。近年來，鏈路預(yù)測還被用于預(yù)測在線社交網(wǎng)絡(luò)的關(guān)系[1]、學(xué)術(shù)網(wǎng)絡(luò)的論文類型、犯罪網(wǎng)絡(luò)中犯罪分子的聯(lián)系，以及電子商務(wù)中客戶的偏好等。同時，鏈路預(yù)測有助于理解復(fù)雜網(wǎng)絡(luò)的演化機制發(fā)現(xiàn)和利用。由于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的內(nèi)部特征差距非常大，因此很難比較各種機制的優(yōu)缺點，而鏈路預(yù)測恰好能為網(wǎng)絡(luò)演化機制[2]的比較提供一個簡單而獨特的平臺，推動復(fù)雜網(wǎng)絡(luò)演化模型的理論研究。

以往關(guān)于鏈路預(yù)測的工作主要集中在單關(guān)系網(wǎng)絡(luò)，即網(wǎng)絡(luò)中只包含單一類型的關(guān)系。然而許多現(xiàn)實世界的關(guān)系系統(tǒng)被描述為包含多種聯(lián)系的多關(guān)系網(wǎng)絡(luò)[3]。在這樣的網(wǎng)絡(luò)中，不同類型的邊表示個體之間的不同關(guān)系，例如朋友、親戚、同事。每一對關(guān)系之間存在相互影響，且對于不同的關(guān)系對，這種影響可能有所不同。例如：一個人與他同事的朋友建立聯(lián)系會比與他親戚的朋友建立聯(lián)系的可能性更高。在這種情況下，“同事”關(guān)系對“朋友”關(guān)系的影響大于“親屬”關(guān)系。對于這種多關(guān)系網(wǎng)絡(luò)的鏈路預(yù)測，需要綜合考慮不同關(guān)系之間的相關(guān)性和影響力。單關(guān)系網(wǎng)絡(luò)的鏈路預(yù)測方法不適用于多關(guān)系網(wǎng)絡(luò)，因為這些方法只考慮單一關(guān)系而忽略整個結(jié)構(gòu)以及不同關(guān)系之間的影響，期望在多關(guān)系的網(wǎng)絡(luò)中有效地利用多面性來增強鏈路預(yù)測結(jié)果。

到目前為止，人們對于單層網(wǎng)絡(luò)的鏈路預(yù)測已經(jīng)做了大量的研究和總結(jié)，對于多層網(wǎng)絡(luò)鏈路預(yù)測有了一些可行的方法，但是很少有人進行系統(tǒng)地整理。針對這個問題，本文提出了一個多層網(wǎng)絡(luò)鏈路預(yù)測方法的分類框架，歸納了現(xiàn)有的多層網(wǎng)絡(luò)鏈路預(yù)測方法，同時對鏈路預(yù)測一些具有可比性的方法進行了比較。

1 單層網(wǎng)絡(luò)鏈路預(yù)測技術(shù)

考慮一個無向單層網(wǎng)絡(luò)G(V,E)，其中：V是節(jié)點集，E是邊集。U表示所有可能邊的全集U=|V|×(|V|-1)/2，|V|表示節(jié)點集V的個數(shù)，不存在的邊集為U-E。鏈路預(yù)測的任務(wù)是預(yù)測邊集合U-E中存在的一些丟失的邊(或者在將來可能存在的邊)。為了測試算法的準確性，邊集E被分成兩部分：被當(dāng)作已知信息的訓(xùn)練集ET和被當(dāng)作缺失鏈接的測試集EP。顯然ET∪EP=E，ET∩EP=?。給定一種鏈路預(yù)測方法，等效地給出每個未觀察到的鏈路(u,v)∈U-ET一個得分Suv，進而將所有未連接的節(jié)點對按照分數(shù)從大到小排序，排在前面的節(jié)點對出現(xiàn)連邊的概率最大。

在專業(yè)文獻中已經(jīng)提出了大量單層鏈路預(yù)測技術(shù)。文獻[4]總結(jié)并比較了若干具有代表性的單關(guān)系網(wǎng)絡(luò)鏈路預(yù)測方法，包括基于相似性的方法、基于最大似然估計的方法和基于概率模型的算法?；谙嗨菩缘姆椒俣ü?jié)點傾向于與其他類似的節(jié)點形成鏈接，如果兩個節(jié)點連接到類似的節(jié)點或者根據(jù)給定的距離函數(shù)在網(wǎng)絡(luò)中鄰近，那么兩個節(jié)點是相似的。常見的基于相似性的方法包括共同鄰居(CN)[5]、Adamic-Adar指標(AA)[5]、資源分配指標(RA)[6]、優(yōu)先鏈接指標(PA)[7]、Jaccard指標(JA)[8]、Salton指標[9]、Sorenson、LHN-I指標[10]、局部路徑指標(LP)[6，11]和Katz指標[12]等。基于最大似然估計的方法雖然精確度較高，但是不適用于規(guī)模較大的網(wǎng)絡(luò)?；诟怕誓Ｐ偷姆椒ㄍǔＯ冉⒁粋€含有一組可調(diào)參數(shù)的模型，繼而使用優(yōu)化策略尋找最優(yōu)的參數(shù)值，使得所得到的模型能夠更好地再現(xiàn)真實網(wǎng)絡(luò)的結(jié)構(gòu)和關(guān)系特征[13]。網(wǎng)絡(luò)中兩個未連邊的節(jié)點對連邊的概率等于在該組最優(yōu)參數(shù)下它們之間產(chǎn)生連邊的條件概率，這些概率值可以用來排列潛在的鏈接，與基于相似性的方法類似。

為了衡量不同算法的優(yōu)劣，通常使用兩個評價指標來量化預(yù)測算法的準確性，分別是AUC[14]和Precision[15]。AUC根據(jù)整個列表評估算法的性能，從而提供所有未觀察到的鏈接的等級。AUC的值表示每次隨機從測試集中選取一條鏈接與隨機選擇的不存在的鏈接比較，測試集EP中的鏈接得分高于從不存在的鏈接集合U-E中隨機選擇的一個鏈接得分的可能性。在n次獨立的比較中，如果有n′次測試集中的鏈接具有更高的分數(shù)，有n″次具有相同的得分，則AUC的值表示為：

(1)

Precision只關(guān)注排在前L位的邊是否預(yù)測準確，定義為在前L個預(yù)測鏈接中被準確預(yù)測的比例，精確度越高則表示準確性越高。若有Lr條鏈接是正確的(Lr條鏈接在EP集合中)，則精確度(P)表示為：

(2)

綜上所述，人們對單層網(wǎng)絡(luò)鏈路預(yù)測進行了較為充分的研究，但是對于多層網(wǎng)絡(luò)鏈路預(yù)測卻面臨新的問題和挑戰(zhàn)。

2 多層網(wǎng)絡(luò)

多層網(wǎng)絡(luò)明確地包含多個連接層，構(gòu)成由不同關(guān)系(活動、類別等)鏈接互連的系統(tǒng)。每個層包含一種關(guān)系(活動、類別)，并且相同的節(jié)點(實體)可以具有不同類型的交互(每層中不同的鄰居集合)。如今，多層網(wǎng)絡(luò)模型已經(jīng)應(yīng)用到許多領(lǐng)域，包括社會科學(xué)、技術(shù)系統(tǒng)和經(jīng)濟學(xué)等。在未來，生物學(xué)和生物醫(yī)學(xué)也將會更加充分地利用多層模型。

多層網(wǎng)絡(luò)相較于單層網(wǎng)絡(luò)，要考慮的問題更加復(fù)雜。單層網(wǎng)絡(luò)只需要考慮單層網(wǎng)絡(luò)中的鏈接，而多層網(wǎng)絡(luò)不僅要考慮各層的層內(nèi)鏈接，還要考慮各個層之間存在的聯(lián)系和影響，即層間關(guān)系，如圖1所示。

圖1 單層網(wǎng)絡(luò)(左)與多層網(wǎng)絡(luò)(右)對比

2.1 網(wǎng)絡(luò)定義

(3)

(4)

因此多層網(wǎng)絡(luò)可以建立數(shù)學(xué)模型[16]，表示為M=(VM,EM)，其中:

(5)

(6)

2.2 網(wǎng)絡(luò)類型

多層網(wǎng)絡(luò)包括多路復(fù)用網(wǎng)絡(luò)[17]、時序網(wǎng)絡(luò)[18]、互動網(wǎng)絡(luò)[19]、多維網(wǎng)絡(luò)[20]、相互依賴的網(wǎng)絡(luò)[21]、多級網(wǎng)絡(luò)[22]和超圖[23]等在內(nèi)的多種類型。由于本文鏈路預(yù)測方法基本上只涉及多路復(fù)用網(wǎng)絡(luò)和時序網(wǎng)絡(luò)，因此這里只介紹這兩種網(wǎng)絡(luò)類型。

1) 多路復(fù)用網(wǎng)絡(luò)(多重網(wǎng)絡(luò))。一個m層的多路復(fù)用網(wǎng)絡(luò)M是所有層{Gα;α∈{1,2,…,m}}的集合，每一層由一個(有向或無向，加權(quán)或不加權(quán))圖Gα=(V,Eα)構(gòu)成，其中V=V1=V2=…=Vm，即所有層擁有相同的節(jié)點，層間關(guān)系Eαβ={(v,v);v∈V}}。

3 多層網(wǎng)絡(luò)鏈路預(yù)測

3.1 問題描述與評價方法

3.2 多層網(wǎng)絡(luò)鏈路預(yù)測分類

雖然單層網(wǎng)絡(luò)的鏈路預(yù)測技術(shù)已經(jīng)在不同領(lǐng)域得到了大量的應(yīng)用，但是對于多層網(wǎng)絡(luò)的鏈路預(yù)測研究仍然較少。多層網(wǎng)絡(luò)相較于單層網(wǎng)絡(luò)，最大的區(qū)別在于多層網(wǎng)絡(luò)在考慮層內(nèi)關(guān)系的基礎(chǔ)上還需考慮層間關(guān)系。圖2為多層網(wǎng)絡(luò)的鏈路預(yù)測方法技術(shù)分類。

圖2 多層網(wǎng)絡(luò)鏈路預(yù)測方法分類技術(shù)

在多層網(wǎng)絡(luò)鏈路預(yù)測過程中，各個方法都用到了多層網(wǎng)絡(luò)的特征或?qū)傩?，?對現(xiàn)階段多層網(wǎng)絡(luò)鏈路預(yù)測方法中運用到的一些具有代表性的屬性或特征進行了總結(jié)。

表1 多層網(wǎng)絡(luò)屬性/特征表

續(xù)表1

3.3 基于單層方法擴展

該分類擴展了單層網(wǎng)絡(luò)鏈路預(yù)測的方法，主要通過預(yù)測層與目標層之間的關(guān)聯(lián)，找出預(yù)測層對目標層的重要程度(即權(quán)重)，結(jié)合預(yù)測層的層間信息和層內(nèi)信息，對目標層進行鏈路預(yù)測。

3.3.1層內(nèi)關(guān)系提取方法

層內(nèi)關(guān)系提取方法可以基于現(xiàn)有的單層鏈路預(yù)測方法(包括CN、RA和AA等)直接獲得，也可以利用多個測量方法得到多個未連接節(jié)點對的排序列表，組合排序列表獲得單個聚合排序列表，得到節(jié)點對層內(nèi)關(guān)系親密程度的排序。這里介紹幾種排序聚合的方法。

1) Borda排序[24]。Borda排序是一種經(jīng)典的絕對定位排序方法。首先為每個排序列表中的每個節(jié)點對分配一個Borda分數(shù)，最后整合得到一個聚合排序列表。Borda得分越高，則節(jié)點對存在的可能性越高。對于一組排序列表L=[L1,L2,…,Ln]，Li表示其中一個測量方法得到的列表，Li(u,v)表示節(jié)點對(u,v)在列表Li中的排名，最高排名節(jié)點對的值為0，n表示節(jié)點對個數(shù)，節(jié)點對(u,v)在列表Li中的Borda得分為：

BLi(u,v)=n-Li(u,v)

(7)

節(jié)點對(u,v)總Borda得分如下，從而得到一個完整的聚合列表：

(8)

2) Kemeny排序[25]。Kemeny排序是一種相對定位方法，主要基于計算兩個輸入列表中相反排名的元素對的數(shù)量。首先通過輸入列表或者一些經(jīng)典聚合方法(如Borda排序)獲得初始排列。計算每一個初級排列的得分，該得分等于該排列與所有輸入列表之間的距離之和。K(π,Li)表示π和Li兩個列表中擁有相反排名的元素對的數(shù)量，其中π是初始排列。通過SK(π,L1,L2,…,Ln)衡量排列的優(yōu)劣，具有最低分數(shù)的排列被認為是最佳方案，定義如下：

K(π,Li)=|(x,y) s.t.π(x)<π(y)&Li(x)>Li(y)|

(9)

(10)

3.3.2層間關(guān)系提取方法

層間關(guān)系即層相關(guān)性提取可概括為以下方法和指標。

1) 基于極大似然的方法[26]。該方法在提取層間關(guān)系時，將目標層與預(yù)測層中的重疊鏈路(相同節(jié)點之間同時存在鏈接)作為衡量預(yù)測層權(quán)重的標準，重疊鏈路越多，則權(quán)重越高。根據(jù)每條邊在所有預(yù)測層中的存在性(1表示存在，0表示不存在)，結(jié)合權(quán)重，得到每條邊的分數(shù)。分數(shù)越大，則在目標層中存在的可能性越大?；跇O大似然的方法同時提取了層間關(guān)系和層內(nèi)關(guān)系。全局重疊方法[27]基于極大似然方法類似，引入了一個全局重疊率(GOR)來提取預(yù)測層和目標層之間的層相關(guān)性，公式表示為：

(11)

全局重疊方法和基于極大似然的方法都是從預(yù)測層和目標層的重疊鏈接出發(fā)，但是方法本質(zhì)仍然存在差異?；谒迫坏姆椒ㄡ槍蝹€邊，直接通過所有預(yù)測層中鏈接的存在性給目標層的鏈接分配可能性；而全局重疊方法針對所有的邊，得到的僅僅是層間相關(guān)性。

2) 皮爾遜相關(guān)系數(shù)(PCC)[27]。PCC是一種衡量層相關(guān)性的方法。將兩個層當(dāng)作被考慮的變量，得到層相關(guān)程度。

3) 層重建方法[28]。其將目標層和預(yù)測層的信息以鄰接矩陣的形式表示，利用特征向量和特征值代表網(wǎng)絡(luò)結(jié)構(gòu)特征，用兩層間相似的特征向量數(shù)量量化得到目標層和預(yù)測層的層相關(guān)性。

4) 度相關(guān)性[29]。節(jié)點在各層上的度可能不同。從節(jié)點的度出發(fā)，可以捕獲各個層之間的相關(guān)性。

5) 中心性[30]。節(jié)點的中心性表明了它們在網(wǎng)絡(luò)中的重要性和生命力，基于節(jié)點在節(jié)點之間最短路徑上出現(xiàn)的次數(shù)。

6) 聚類系數(shù)相似度[31]。其用來度量網(wǎng)絡(luò)中節(jié)點趨向于聚集在一起的程度。

7) 鄰居的平均相似度[29]。對于一個節(jié)點u，tα(u)表示節(jié)點u在層α中所有的鏈接數(shù)，tβ(u)表示節(jié)點u在β中的所有鏈接數(shù)，tαβ(u)表示節(jié)點u在層α和層β中同時存在的鏈接數(shù)，k表示節(jié)點的度。鄰居的平均相似度定義為：

(12)

同時，如果考慮到網(wǎng)絡(luò)層中鏈接總數(shù)對于ASN值的影響——層包含的鏈接越多，則它包含的信息很可能相對較多，因此有非對稱鄰居平均形似度指標定義如下：

(13)

式中：α表示目標層；β表示預(yù)測層。

3.4 基于模型建立的方法

3.4.1基本信念模型

基本信念模型[32]以基本信念分配(A Basic Belief Assignment,BBA)的概念來量化邊的不確定度，即邊存在的可能性，信念值介于0和1之間，量化了鏈接存在的可能性。首先，將每個層當(dāng)作獨立的數(shù)據(jù)來源，借鑒共同鄰居的方法，從網(wǎng)絡(luò)的所有層中收集來自相鄰節(jié)點的數(shù)據(jù)。然后，根據(jù)其可靠性評估從每一層收集來的數(shù)據(jù)，再根據(jù)網(wǎng)絡(luò)中特定類型的同時鏈接的分布修改所得到的基本信念分配值。存在未連接節(jié)點對(u,v)，對于一個預(yù)測層，如果目標層中u和v的共同鄰居與該預(yù)測層中兩點的共同鄰居完全重合，則采用合取規(guī)則修改信念值，表明這個預(yù)測層是高度可靠的；如果預(yù)測層中只出現(xiàn)部分共同鄰居，則使用析取規(guī)則，表明這個預(yù)測層至少有一部分是可靠的；如果預(yù)測層中完全沒有出現(xiàn)目標層中的共同鄰居，則表明這個層可以被忽略。

3.4.2隨機塊模型

隨機塊模型可分為以節(jié)點為基本單位和以鏈接為基本單位的兩種模型[33]。該方法基于隨機塊模型的概率推理[34]，同時描述所有層的信息，在預(yù)測目標層時充分利用了整個網(wǎng)絡(luò)中包含的信息。因為兩個方法類似，因此下面只介紹基于節(jié)點為基本單位的隨機塊模型。

基于節(jié)點為基本單位的隨機塊模型將節(jié)點和層分別分組，每個節(jié)點和層可以同時屬于多個組，通過節(jié)點、層屬于某組的概率以及節(jié)點對在各個預(yù)測層上的互動概率得到目標層上該節(jié)點對鏈路存在的可能性，節(jié)點對(u,v)在目標層α中的相似度可表示為：

(14)

式中：θig1表示節(jié)點u屬于組g1的概率；θvg2表示節(jié)點v屬于組g2的概率；ηlg3表示層l屬于g3的概率；pg1g2g3(α)表示組g1中的節(jié)點u與組g2中的節(jié)點v在組g3中的層α上聯(lián)系的概率。

3.4.3馬爾可夫模型變形

該模型使用特征級聯(lián)的無限階乘隱馬爾可夫模型，對各節(jié)點在不同層中的隸屬關(guān)系進行建模[35]，從而對層內(nèi)和層間鏈路進行預(yù)測。

3.4.4 GCN-GAN模型

GCN-GAN模型是一種新的非線性模型，可應(yīng)用于動態(tài)加權(quán)網(wǎng)絡(luò)[36]。該模型利用了圖卷積網(wǎng)絡(luò)(GCN)，長短期記憶(LSTM)和生成對抗網(wǎng)絡(luò)(GAN)。首先利用GCN獲取各個時間快照的拓撲結(jié)構(gòu)，然后使用LSTM來表征動態(tài)網(wǎng)絡(luò)的演變特征。在這個過程中，GAN用于增強模型生成下一個加權(quán)網(wǎng)絡(luò)快照的能力。

3.5 基于機器學(xué)習(xí)的方法

該方法提取預(yù)測層層間特征和層內(nèi)特征以及目標層的層內(nèi)特征，使用機器學(xué)習(xí)，包括樸素貝葉斯、邏輯回歸、支持向量機、K-近鄰算法、決策樹等分類器對有無鏈路進行分類，從而完成鏈路預(yù)測。在此過程中，重點在于特征提取。多層網(wǎng)絡(luò)的特征多種多樣，特征的選取與研究對象、網(wǎng)絡(luò)特點等密不可分，具有靈活性和可變性，下面列舉了一些具有代表性的特征。

3.5.1層內(nèi)特征

層內(nèi)特征可概括為以下幾部分：

1) 層內(nèi)特征涵蓋了3.3.1節(jié)中提到的層內(nèi)關(guān)系以及經(jīng)典的頁面排序算法(PageRank)[37]，此處不再贅述。

2) 單層監(jiān)督排名聚合值。使用多個單層鏈路預(yù)測方法，包括CN、AA和RA等，分別得出鏈路存在的可能性大小。排名聚合通過使用不同的單層鏈路預(yù)測方法得到多個排名列表，使用排名聚合組合這些排序列表獲得單個列表，得到聚合值。

3) 單層重疊率[38]表示為：

(15)

式中：Γ(u)表示節(jié)點u的鄰居；|Γ(u)|表示節(jié)點u的鄰居數(shù)，即節(jié)點的度。

4) 聲譽值和樂觀值[39]。適用于有向網(wǎng)絡(luò)，每個鏈接有相應(yīng)的符號，任何鏈接都有正號或者負號，如圖3所示。

圖3 聲譽值和樂觀值示意圖

(16)

(17)

5) 節(jié)點對間最短路徑數(shù)量[40]。該特征利用廣度優(yōu)先搜索算法[41]，在無向網(wǎng)絡(luò)中確定節(jié)點對之間最短路徑的數(shù)量。該過程迭代進行，在每一個深度，計算并更新到未訪問節(jié)點的最短路徑數(shù)。

6) 節(jié)點對簇內(nèi)與簇間公共鄰居比例[40]。這里用到了聚類的概念，先用一些已有的聚類方法[42]將節(jié)點分成多個不同的小團體，也就是簇，簇中的各個節(jié)點聯(lián)系更為密切。如果兩個節(jié)點的共同鄰居與兩個節(jié)點屬于同一個簇，稱其為簇內(nèi)鄰居，否則稱其為簇間鄰居。

3.5.2層間特征

層間特征與層間關(guān)系有些不同，層間關(guān)系用來表示全局層間信息，即層與層之間的總體相關(guān)性(基于層)；層間特征用來定義局部層間信息，即兩個未連接節(jié)點之間的層間相關(guān)性(基于節(jié)點)。下面列舉特征：

1) 元路徑。在多層網(wǎng)絡(luò)中，兩個對象可以通過穿過網(wǎng)絡(luò)的不同層或包括不同類型的對象的路徑進行連接[43]。元路徑用來表示兩個節(jié)點之間的跨層路徑。首先確定兩個節(jié)點之間元路徑的長度和類型，然后使用諸如廣度優(yōu)先搜索或深度優(yōu)先搜索等方式遍歷網(wǎng)絡(luò)找到元路徑，從中提取有意義的特征。

2) 多層Adamic/Adar指標。多層網(wǎng)絡(luò)Adamic/Adar指標是單層鏈路預(yù)測Adamic/Adar指標的擴展，Hristova等[38]在文獻中給出定義如下：

(18)

式中：ΓGNi表示多層網(wǎng)絡(luò)中節(jié)點i的所有鄰居節(jié)點的集合。

3) 多層重疊率(層與層之間邊的重疊率)[44]表示為：

(19)

4) 交互性指標[38]表示為：

(20)

5) 所有層平均聚合值[46]。基于單層監(jiān)督排名聚合值，用于計算所有層上特征的平均值，定義如下：

(21)

式中：X(u,v)是一個拓撲屬性值。

6) 所有層中的值的熵聚合。節(jié)點度熵(Product of node degree entropy,PNE)基于度熵[46]。度熵E(u)和節(jié)點度熵有如下定義：

(22)

PNE(u,v)=E(u)·E(v)

(23)

另外，存在一個基于拓撲屬性的熵，被稱為Xent，表示為：

(24)

7) 全網(wǎng)絡(luò)相似性指標。該指標假定兩個實體之間的吸引力與它們之間相互作用的重要性成正比[47]，具有局限性，適用于社交互動信息網(wǎng)絡(luò)和地理位置網(wǎng)絡(luò)結(jié)合的多層網(wǎng)絡(luò)。定義如下：

(25)

3.6 典型應(yīng)用

本節(jié)呈現(xiàn)了幾個多層網(wǎng)絡(luò)鏈路預(yù)測的具體應(yīng)用，包括靜態(tài)多重網(wǎng)絡(luò)，時序網(wǎng)絡(luò)和動態(tài)多重網(wǎng)絡(luò)等鏈路預(yù)測。表2對靜態(tài)多重網(wǎng)絡(luò)鏈路預(yù)測方法進行了定性地對比，表3對現(xiàn)有的動態(tài)多重網(wǎng)絡(luò)進行了大致的比較。

表2 靜態(tài)多重網(wǎng)絡(luò)鏈路預(yù)測方法對比表

表3 動態(tài)多重網(wǎng)絡(luò)鏈路預(yù)測方法對比表

續(xù)表3

3.6.1靜態(tài)多重網(wǎng)絡(luò)的應(yīng)用

針對多重社交網(wǎng)絡(luò)，Yao等[27]、Abdolhosseini-Qomi等[28]和Sharma等[26]基于單層方法進行擴展；Hristova等[38]、Jalili等[48]、Mandal等[40]采用了機器學(xué)習(xí)的分類方法，提取不同的特征對鏈路有無進行了二元分類。其中Hristova等[38]使用隨機森林分類器(Random Forest classifier)；Jalili等[48]使用并比較了支持向量機(SVM)、K最近鄰(KNN)和樸素貝葉斯三種分類算法，實驗得出SVM的分類結(jié)果較好；Mandal等[40]使用了樸素貝葉斯方法。而Najari等[49]結(jié)合了基于單層的方法和機器學(xué)習(xí)，使用邏輯回歸的分類算法進行了鏈路預(yù)測。

Yao等[27]利用層間關(guān)系和層內(nèi)關(guān)系，提出了一個基于多重網(wǎng)絡(luò)層相關(guān)性的節(jié)點相似度指標(NSILR)用于鏈路預(yù)測。對于一個節(jié)點對(u,v)而言，首先根據(jù)現(xiàn)有的單層鏈路預(yù)測方法(CN、RA、AA、LP和Katz等)計算每層中該節(jié)點對的相似性，包括目標層和預(yù)測層。然后通過測量層間相關(guān)性，得到節(jié)點u和v在目標層中存在鏈接的可能性大小。

該方法提出的基于多重網(wǎng)絡(luò)層相關(guān)性的節(jié)點相似度指標(NSILR)被定義為：

(26)

在實驗過程中采用時間復(fù)雜度較低的局部相似性度量方法和來自其他層的層間信息，獲得了比時間復(fù)雜度較高的全局和準局部度量更好的性能，同時驗證了皮爾遜相關(guān)系數(shù)(PCC)在某些復(fù)用網(wǎng)絡(luò)中擁有比全局重疊率(GOR)更好的性能。NISLR指數(shù)同時考慮了層內(nèi)信息和層間信息，成功地在一個七層多路復(fù)用網(wǎng)絡(luò)上進行了鏈路預(yù)測。

該方法根據(jù)網(wǎng)絡(luò)的差異，得到層間關(guān)系和層內(nèi)關(guān)系在鏈路預(yù)測中的最佳比重，獲得較高的預(yù)測性能，具有較強的擴展性和靈活性，可以適應(yīng)較多層靜態(tài)網(wǎng)絡(luò)的鏈路預(yù)測。同時其預(yù)測性能受限于層相關(guān)性，層越相關(guān)，則預(yù)測性能越高。

Najari等[49]提出了一個基于層間相似性的鏈路預(yù)測框架(Linkprediction Accounting Interlayer Similarity，LPIS)，結(jié)合了基于單層鏈路預(yù)測方法的擴展和機器學(xué)習(xí)的方法，提取層內(nèi)特征，通過度相關(guān)性、中心性、聚類系數(shù)相似度和鄰居的平均相似度等得到層間關(guān)系，完成鏈路預(yù)測。層間關(guān)系通過式(27)轉(zhuǎn)變?yōu)殒溄哟嬖诘目赡苄裕?/p>

(27)

最后將層內(nèi)特征和層間關(guān)系相結(jié)合，得到節(jié)點對存在的可能性：

(28)

對照上述NISLR方法，可以發(fā)現(xiàn)兩個方法之間有許多相似之處。兩者都包含充分的層間信息和層內(nèi)信息，通過一個可調(diào)參數(shù)φ來平衡層間關(guān)系和層內(nèi)關(guān)系，但是對于層間關(guān)系的提取方法存在差異。LPIS方法分別在雙層網(wǎng)絡(luò)Twitter-Foursquare網(wǎng)絡(luò)和Twitter-Instagram網(wǎng)絡(luò)、五層線上線下交流網(wǎng)絡(luò)和37層歐洲航空運輸網(wǎng)絡(luò)中進行了實驗，得到了良好的效果，相比NISLR方法具有更高的可信度和可擴展性。

Sharma等[26]研究加權(quán)復(fù)用網(wǎng)絡(luò)中的鏈路預(yù)測，使用網(wǎng)絡(luò)中所有其他層的信息，預(yù)測目標層處的鏈路以及權(quán)重[26]。對于所有預(yù)測層，可能性是指目標層對于該預(yù)測層的依賴程度，使用基于似然的方法被單獨計算，目標層中存在鏈接的可能性是單層可能性的組合。

除了提出鏈路預(yù)測的方法，Sharma等[26]還對權(quán)重進行了預(yù)測。對于一對將來可能存在的節(jié)點對，權(quán)重取決于連接該節(jié)點對的邊和兩個節(jié)點的鄰居[50]。權(quán)重的表達式為：

(29)

(30)

(31)

式中：u和v是被權(quán)重預(yù)測的節(jié)點對；A和B分別代表u和v分數(shù)最高的鄰居；Wuv表示節(jié)點對(u，v)的權(quán)重；WAu和SAu分別表示A和u之間鏈接的權(quán)重和分數(shù)。

Sharma等[26]提出了在加權(quán)網(wǎng)絡(luò)中的鏈路預(yù)測和權(quán)重預(yù)測方法，預(yù)測的權(quán)重和實際權(quán)重偏差較小，能夠應(yīng)用于一些加權(quán)網(wǎng)絡(luò)的場景。但是局限性較大，預(yù)測性能只能在特定的多路復(fù)用網(wǎng)絡(luò)上得到驗證，而且沒有充分利用預(yù)測層的層內(nèi)信息。

層重建方法[28](Layer Reconstruction Method,LRM)利用層重建指標，使用目標層和預(yù)測層的結(jié)構(gòu)特征量化層間關(guān)系和層內(nèi)關(guān)系，對目標層進行重建，完成鏈路預(yù)測。該方法最大的優(yōu)點在于信息冗余，即使鏈路預(yù)測缺失率較高，也能保證鏈路預(yù)測的相對準確性。

Hristova等[38]、Jalili等[48]和Mandal等[40]均使用機器學(xué)習(xí)研究了Twitter-Foursquare網(wǎng)絡(luò)，但只是提取了不同的特征。Hristova等[38]提取社交互動網(wǎng)絡(luò)Twitter的特征包括提及次數(shù)[51]、共同標簽數(shù)、單層重疊率以及單層Adamic/Adar指標；在線地理網(wǎng)絡(luò)Foursquare的特征包括節(jié)點同地點出現(xiàn)的可能性以及節(jié)點常去地點之間的距離。多層特征(即層間特征)包括多層Adamic/Adar指標、全網(wǎng)絡(luò)相似性指標和多層重疊率和交互性指標。該方法提取的特征充分和全面，考慮了每一層的特性以及復(fù)合后的多層網(wǎng)絡(luò)特性，從局部和全局方面進行特征提取，提高了預(yù)測性能，但同時增加了算法復(fù)雜度。Jalili等[48]提取了每個節(jié)點的屬性(層內(nèi)關(guān)系)和元路徑(層間關(guān)系)特征。其中節(jié)點的屬性包括節(jié)點的共同鄰居CN、聲譽值和樂觀值。該方法提出的跨層元路徑特征提取簡單可行，算法復(fù)雜度較低，但性能受限于網(wǎng)絡(luò)的密集程度，對于稀疏網(wǎng)絡(luò)，找不到許多公共相鄰節(jié)點，導(dǎo)致元路徑較少，機器學(xué)習(xí)的分類性能較差。Mandal等[40]利用了共同鄰居的數(shù)量、節(jié)點對之間的邊數(shù)量、簇內(nèi)與簇間公共鄰居比例和最短路徑數(shù)量等特征，相較于使用元路徑的方法更為簡單，準確率也較高。三者僅僅是在Twiiter-Foursquare網(wǎng)絡(luò)中進行研究和實驗，針對性強，對于社交網(wǎng)絡(luò)的多重網(wǎng)絡(luò)鏈路預(yù)測啟發(fā)較大，但同時社交網(wǎng)絡(luò)的特色較為明顯，導(dǎo)致應(yīng)用范圍不廣，很難將社交網(wǎng)絡(luò)存在的特征擴展到不同的網(wǎng)絡(luò)中。

針對更多層的復(fù)合科學(xué)合作網(wǎng)絡(luò)，Pujari等[45]同樣通過提取層內(nèi)特征和層間特征進行鏈路預(yù)測。層內(nèi)特征包括單層監(jiān)督排名聚合值，多層特征(即層間特征)包括所有層平均聚合值以及所有層中的值的熵聚合。該方法開創(chuàng)性地在多路復(fù)用網(wǎng)絡(luò)上應(yīng)用排名聚合來組合多個拓撲測量，提升預(yù)測性能，但是算法復(fù)雜性較高，對于大型數(shù)據(jù)集的有效性較低。

3.6.2時序網(wǎng)絡(luò)的鏈路預(yù)測

時序網(wǎng)絡(luò)是隨著時間動態(tài)變化的網(wǎng)絡(luò)，因此鏈路預(yù)測的過程更為復(fù)雜。Hajibagheri等[52]提出了時序網(wǎng)絡(luò)鏈路預(yù)測框架(Multiplex Link Prediction,MLP)。MLP框架包括邊賦值、時間鏈接結(jié)構(gòu)和排名聚合三個組件。

首先，MLP框架使用基于似然的方法計算跨層依賴性，得到邊集的分數(shù)(即為邊集賦值)。然后，使用時間衰減函數(shù)來模擬網(wǎng)絡(luò)動態(tài)，為每個節(jié)點相似性度量生成復(fù)合時間分數(shù)矩陣[53]。給定T時間的網(wǎng)絡(luò)歷史，從而捕獲協(xié)同進化過程中的時間依賴性。令{simt(i,j),t=t0+1,t0+2,…,t0+T}是由連續(xù)時間片T的滑動窗口上的節(jié)點相似性度量生成的相似性得分矩陣。聚合加權(quán)后的相似性矩陣構(gòu)造如下：

(32)

式中：參數(shù)θ∈[0,1]表示先前時間段的權(quán)重，在當(dāng)前時間t+1之前，根據(jù)快照的重要性修改θ的值。

最后采用Borda排序的方法將來自多個拓撲度量的信息收集到一個評分矩陣中，為潛在的鏈接進行排序。Borda排序利用所有快照中鏈路的不同排序列表，得到聚合排序。

該方法考慮了網(wǎng)絡(luò)的動態(tài)變化，引入了時間衰減模型，模擬了多路網(wǎng)絡(luò)協(xié)同進化，可以準確地預(yù)測時序網(wǎng)絡(luò)中的鏈路，有效地融合不同拓撲信息(邊和節(jié)點的特征、節(jié)點相似性等)。進行Borda排名聚合，算法復(fù)雜度較低，可應(yīng)用于許多領(lǐng)域的大規(guī)模時序網(wǎng)絡(luò),比如在銷售領(lǐng)域可以用來分析實時需求尋求企業(yè)最大化利潤，在工業(yè)領(lǐng)域可以智能運維，提高各個環(huán)節(jié)的穩(wěn)定性等。

3.6.3加權(quán)動態(tài)網(wǎng)絡(luò)的應(yīng)用

Lei等[36]提出GCN-GAN模型解決加權(quán)動態(tài)網(wǎng)絡(luò)中的鏈路預(yù)測問題。該方法同時考慮了動態(tài)網(wǎng)絡(luò)中潛在的非線性特征和鏈路權(quán)重，充分利用加權(quán)動態(tài)網(wǎng)絡(luò)的動態(tài)性、拓撲結(jié)構(gòu)和演化模式來改善動態(tài)鏈路預(yù)測的性能。因為鏈路權(quán)重和動態(tài)性在實際網(wǎng)絡(luò)中都是必不可少的，而如今大部分方法并未將兩者結(jié)合起來，因此這個方法對于鏈路預(yù)測的發(fā)展具有啟發(fā)性和創(chuàng)新性。

3.6.4動態(tài)多重網(wǎng)絡(luò)的應(yīng)用

Tarres-Deulofeu等[33]提出的隨機塊模型，適用于任何多層網(wǎng)絡(luò)。該方法打破了多層網(wǎng)絡(luò)鏈路預(yù)測的局限性。

Junuthula等[54]長期研究動態(tài)網(wǎng)絡(luò)，有針對性地研究了友誼網(wǎng)絡(luò)和互動網(wǎng)絡(luò)形成的多重網(wǎng)絡(luò)，利用友誼網(wǎng)絡(luò)和互動網(wǎng)絡(luò)之前的快照對互動網(wǎng)絡(luò)中的未來動態(tài)鏈接進行了預(yù)測。該方法在鏈路預(yù)測分析時，需要先分析每個網(wǎng)絡(luò)的特征。在友誼網(wǎng)絡(luò)中，鏈接通常只需要進行一次預(yù)測；在互動網(wǎng)絡(luò)中，鏈接需要重復(fù)交互，也就是說，人們可能會互動一段時間之后停止互動然后又恢復(fù)互動。因此，考慮互動網(wǎng)絡(luò)時，需要同時考慮未來可能形成的邊和可能消失的邊。雖然Junuthula等[54]研究的同樣是友誼網(wǎng)絡(luò)和互動網(wǎng)絡(luò)，與Twitter和Foursquare網(wǎng)絡(luò)類似，但是其不再局限于一個狀態(tài)下的網(wǎng)絡(luò)，而擴展為一段時間內(nèi)產(chǎn)生動態(tài)變化的多重網(wǎng)絡(luò)，考慮到兩個網(wǎng)絡(luò)的不同特性，尤其是互動網(wǎng)絡(luò)互動的間隔性，導(dǎo)致單獨一次鏈路預(yù)測不足以說明問題，需要持續(xù)性地預(yù)測。該方法考慮到此問題，因此使得分析的結(jié)果更為可靠。

Yasami等[35]針對動態(tài)多重網(wǎng)絡(luò)，考察了整個網(wǎng)絡(luò)演化過程中的層演化過程(層的出生/死亡和生命周期)，使用圖模型中的馬爾可夫模型變形，完成了動態(tài)多層網(wǎng)絡(luò)的鏈路預(yù)測。該方法的全局意識較強，出發(fā)點較高，相較Junuthula等[54]方法僅針對性地服務(wù)于兩個社交網(wǎng)絡(luò)，其模擬重現(xiàn)各個網(wǎng)絡(luò)，可應(yīng)用于大部分動態(tài)多重網(wǎng)絡(luò)?，F(xiàn)如今存在的許多網(wǎng)絡(luò)本質(zhì)上就是動態(tài)多重網(wǎng)絡(luò)，因此研究分析動態(tài)多重網(wǎng)絡(luò)具有重大的意義。

4 結(jié) 語

本文總結(jié)了多層網(wǎng)絡(luò)鏈路預(yù)測方法研究與發(fā)展，包括基于單層網(wǎng)絡(luò)方法的擴展、基于機器學(xué)習(xí)的方法和建立模型的方法。前兩者均考慮了兩個方面的因素——層間關(guān)系和層內(nèi)關(guān)系。難點在于對層間關(guān)系的提取，即衡量層與層之間的關(guān)系親疏。利用極大似然估計、重疊率等方法衡量一個層對另一個層的重要性，從而得到各個預(yù)測層對于目標層的重要性差異，可獲得好的鏈路預(yù)測結(jié)果。也可通過提取多層網(wǎng)絡(luò)中的多層特征，利用機器學(xué)習(xí)對鏈路有無進行分類。建立模型的方法通過模擬、架構(gòu)整個網(wǎng)絡(luò)來進行鏈路預(yù)測。其中圖概率模型在鏈路預(yù)測中較為常用的是隱馬爾可夫模型，因為隱馬爾可夫模型不需要模型的狀態(tài)序列，因此其適應(yīng)性較強。近幾年出現(xiàn)的圖卷積神經(jīng)網(wǎng)絡(luò)，對于較為復(fù)雜的多重網(wǎng)絡(luò)，能充分地利用網(wǎng)絡(luò)的各個特性，提高鏈路預(yù)測的質(zhì)量，雖然如今研究較少，但也是未來發(fā)展的趨勢。

實驗表明，相比逐個分析單一網(wǎng)絡(luò)，上述的各個方法都表現(xiàn)出更好的預(yù)測效果，具有更低的錯誤率。這些方法已經(jīng)研究發(fā)現(xiàn)了一些多層網(wǎng)絡(luò)中的特征和屬性，并利用這些特征和屬性進行鏈路預(yù)測。多層鏈路預(yù)測的結(jié)果好壞存在很多原因，雖然主要在于方法的優(yōu)劣，但與分析的網(wǎng)絡(luò)性質(zhì)等也有關(guān)系。

現(xiàn)有的大部分研究主要致力于研究靜態(tài)多重網(wǎng)絡(luò)，對動態(tài)多重網(wǎng)絡(luò)的研究較少。目前多數(shù)方法僅限于對兩個網(wǎng)絡(luò)的分析，且大部分分析偏向于社交網(wǎng)絡(luò)，分析的數(shù)據(jù)集較少，樣本比較單一，特殊性較強，擴展性較弱，提出的方法很難擴展到其他的網(wǎng)絡(luò)中。因此，考慮更多層真實的動態(tài)大規(guī)模網(wǎng)絡(luò)、進一步整合可用的數(shù)據(jù)、增強擴展性以及降低算法復(fù)雜度都是未來的目標。此外，傳統(tǒng)機器學(xué)習(xí)以及深度學(xué)習(xí)雖然已經(jīng)被使用了很長一段時間，并在各種環(huán)境下提供了可靠的性能，但其在鏈路預(yù)測領(lǐng)域的應(yīng)用才剛剛起步，提取的特征人為干預(yù)較強，仍值得深入研究以提高其在實際應(yīng)用中的適用性。