多層網絡鏈路預測研究進展

王飛程 周鈺穎 閔 勇

(浙江工業大學計算機科學與技術學院 浙江 杭州 310023)

0 引 言

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

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

到目前為止，人們對于單層網絡的鏈路預測已經做了大量的研究和總結，對于多層網絡鏈路預測有了一些可行的方法，但是很少有人進行系統地整理。針對這個問題，本文提出了一個多層網絡鏈路預測方法的分類框架，歸納了現有的多層網絡鏈路預測方法，同時對鏈路預測一些具有可比性的方法進行了比較。

1 單層網絡鏈路預測技術

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

在專業文獻中已經提出了大量單層鏈路預測技術。文獻[4]總結并比較了若干具有代表性的單關系網絡鏈路預測方法，包括基于相似性的方法、基于最大似然估計的方法和基于概率模型的算法。基于相似性的方法假定節點傾向于與其他類似的節點形成鏈接，如果兩個節點連接到類似的節點或者根據給定的距離函數在網絡中鄰近，那么兩個節點是相似的。常見的基于相似性的方法包括共同鄰居(CN)[5]、Adamic-Adar指標(AA)[5]、資源分配指標(RA)[6]、優先鏈接指標(PA)[7]、Jaccard指標(JA)[8]、Salton指標[9]、Sorenson、LHN-I指標[10]、局部路徑指標(LP)[6，11]和Katz指標[12]等。基于最大似然估計的方法雖然精確度較高，但是不適用于規模較大的網絡。基于概率模型的方法通常先建立一個含有一組可調參數的模型，繼而使用優化策略尋找最優的參數值，使得所得到的模型能夠更好地再現真實網絡的結構和關系特征[13]。網絡中兩個未連邊的節點對連邊的概率等于在該組最優參數下它們之間產生連邊的條件概率，這些概率值可以用來排列潛在的鏈接，與基于相似性的方法類似。

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

(1)

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

(2)

綜上所述，人們對單層網絡鏈路預測進行了較為充分的研究，但是對于多層網絡鏈路預測卻面臨新的問題和挑戰。

2 多層網絡

多層網絡明確地包含多個連接層，構成由不同關系(活動、類別等)鏈接互連的系統。每個層包含一種關系(活動、類別)，并且相同的節點(實體)可以具有不同類型的交互(每層中不同的鄰居集合)。如今，多層網絡模型已經應用到許多領域，包括社會科學、技術系統和經濟學等。在未來，生物學和生物醫學也將會更加充分地利用多層模型。

多層網絡相較于單層網絡，要考慮的問題更加復雜。單層網絡只需要考慮單層網絡中的鏈接，而多層網絡不僅要考慮各層的層內鏈接，還要考慮各個層之間存在的聯系和影響，即層間關系，如圖1所示。

圖1 單層網絡(左)與多層網絡(右)對比

2.1 網絡定義

(3)

(4)

因此多層網絡可以建立數學模型[16]，表示為M=(VM,EM)，其中:

(5)

(6)

2.2 網絡類型

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

1) 多路復用網絡(多重網絡)。一個m層的多路復用網絡M是所有層{Gα;α∈{1,2,…,m}}的集合，每一層由一個(有向或無向，加權或不加權)圖Gα=(V,Eα)構成，其中V=V1=V2=…=Vm，即所有層擁有相同的節點，層間關系Eαβ={(v,v);v∈V}}。

3 多層網絡鏈路預測

3.1 問題描述與評價方法

3.2 多層網絡鏈路預測分類

雖然單層網絡的鏈路預測技術已經在不同領域得到了大量的應用，但是對于多層網絡的鏈路預測研究仍然較少。多層網絡相較于單層網絡，最大的區別在于多層網絡在考慮層內關系的基礎上還需考慮層間關系。圖2為多層網絡的鏈路預測方法技術分類。

圖2 多層網絡鏈路預測方法分類技術

在多層網絡鏈路預測過程中，各個方法都用到了多層網絡的特征或屬性，表1對現階段多層網絡鏈路預測方法中運用到的一些具有代表性的屬性或特征進行了總結。

表1 多層網絡屬性/特征表

續表1

3.3 基于單層方法擴展

該分類擴展了單層網絡鏈路預測的方法，主要通過預測層與目標層之間的關聯，找出預測層對目標層的重要程度(即權重)，結合預測層的層間信息和層內信息，對目標層進行鏈路預測。

3.3.1層內關系提取方法

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

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

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

(7)

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

(8)

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

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

(9)

(10)

3.3.2層間關系提取方法

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

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

(11)

全局重疊方法和基于極大似然的方法都是從預測層和目標層的重疊鏈接出發，但是方法本質仍然存在差異。基于似然的方法針對單個邊，直接通過所有預測層中鏈接的存在性給目標層的鏈接分配可能性；而全局重疊方法針對所有的邊，得到的僅僅是層間相關性。

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

3) 層重建方法[28]。其將目標層和預測層的信息以鄰接矩陣的形式表示，利用特征向量和特征值代表網絡結構特征，用兩層間相似的特征向量數量量化得到目標層和預測層的層相關性。

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

5) 中心性[30]。節點的中心性表明了它們在網絡中的重要性和生命力，基于節點在節點之間最短路徑上出現的次數。

6) 聚類系數相似度[31]。其用來度量網絡中節點趨向于聚集在一起的程度。

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

(12)

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

(13)

式中：α表示目標層；β表示預測層。

3.4 基于模型建立的方法

3.4.1基本信念模型

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

3.4.2隨機塊模型

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

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

(14)

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

3.4.3馬爾可夫模型變形

該模型使用特征級聯的無限階乘隱馬爾可夫模型，對各節點在不同層中的隸屬關系進行建模[35]，從而對層內和層間鏈路進行預測。

3.4.4 GCN-GAN模型

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

3.5 基于機器學習的方法

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

3.5.1層內特征

層內特征可概括為以下幾部分：

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

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

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

(15)

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

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

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

(16)

(17)

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

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

3.5.2層間特征

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

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

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

(18)

式中：ΓGNi表示多層網絡中節點i的所有鄰居節點的集合。

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

(19)

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

(20)

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

(21)

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

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

(22)

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

(23)

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

(24)

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

(25)

3.6 典型應用

本節呈現了幾個多層網絡鏈路預測的具體應用，包括靜態多重網絡，時序網絡和動態多重網絡等鏈路預測。表2對靜態多重網絡鏈路預測方法進行了定性地對比，表3對現有的動態多重網絡進行了大致的比較。

表2 靜態多重網絡鏈路預測方法對比表

表3 動態多重網絡鏈路預測方法對比表

續表3

3.6.1靜態多重網絡的應用

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

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

該方法提出的基于多重網絡層相關性的節點相似度指標(NSILR)被定義為：

(26)

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

該方法根據網絡的差異，得到層間關系和層內關系在鏈路預測中的最佳比重，獲得較高的預測性能，具有較強的擴展性和靈活性，可以適應較多層靜態網絡的鏈路預測。同時其預測性能受限于層相關性，層越相關，則預測性能越高。

Najari等[49]提出了一個基于層間相似性的鏈路預測框架(Linkprediction Accounting Interlayer Similarity，LPIS)，結合了基于單層鏈路預測方法的擴展和機器學習的方法，提取層內特征，通過度相關性、中心性、聚類系數相似度和鄰居的平均相似度等得到層間關系，完成鏈路預測。層間關系通過式(27)轉變為鏈接存在的可能性：

(27)

最后將層內特征和層間關系相結合，得到節點對存在的可能性：

(28)

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

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

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

(29)

(30)

(31)

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

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

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

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

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

3.6.2時序網絡的鏈路預測

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

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

(32)

式中：參數θ∈[0,1]表示先前時間段的權重，在當前時間t+1之前，根據快照的重要性修改θ的值。

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

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

3.6.3加權動態網絡的應用

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

3.6.4動態多重網絡的應用

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

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

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

4 結 語

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

實驗表明，相比逐個分析單一網絡，上述的各個方法都表現出更好的預測效果，具有更低的錯誤率。這些方法已經研究發現了一些多層網絡中的特征和屬性，并利用這些特征和屬性進行鏈路預測。多層鏈路預測的結果好壞存在很多原因，雖然主要在于方法的優劣，但與分析的網絡性質等也有關系。

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