動態(tài)網(wǎng)絡(luò)鏈接預(yù)測研究

郝宵榮，王 莉

(太原理工大學(xué) 大數(shù)據(jù)學(xué)院，太原 030600)

現(xiàn)實(shí)生活中的網(wǎng)絡(luò)經(jīng)常會因?yàn)樾碌膶?shí)體和鏈接的加入與消失導(dǎo)致網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和某些表達(dá)信息(例如，中心實(shí)體的改變等)不斷地發(fā)生演化。在挖掘和分析演化網(wǎng)絡(luò)的信息時，鏈接預(yù)測問題成為了一項非常重要的任務(wù)。動態(tài)網(wǎng)絡(luò)鏈接預(yù)測任務(wù)不僅從理論方面支撐了許多領(lǐng)域研究，同時從實(shí)踐方面還擁有廣泛的應(yīng)用價值。在理論上，該任務(wù)從提供動態(tài)網(wǎng)絡(luò)建模的理論支撐和評估動態(tài)網(wǎng)絡(luò)演化模型的優(yōu)劣兩方面幫助更好地理解網(wǎng)絡(luò)底層的演化機(jī)制[1]；在應(yīng)用上，研究者們針對領(lǐng)域需求，研究不同的動態(tài)網(wǎng)絡(luò)鏈接預(yù)測方法：社會媒體網(wǎng)絡(luò)中，通過預(yù)測不同實(shí)體之間的鏈接，完成推薦、營銷等任務(wù)[2]；學(xué)術(shù)網(wǎng)絡(luò)中，基于鏈接預(yù)測技術(shù)預(yù)測學(xué)者們之間未來是否進(jìn)行學(xué)術(shù)研究合作[3]；生物關(guān)系網(wǎng)絡(luò)中，鏈接預(yù)測用來研究蛋白質(zhì)網(wǎng)絡(luò)之間的相互作用，對研究各種生命特征具有重要意義[2]；知識圖譜中[4]，鏈接預(yù)測通過獲取數(shù)據(jù)中新的實(shí)體鏈接和關(guān)聯(lián)規(guī)則等信息，進(jìn)行深度知識推理，從而提高大規(guī)模運(yùn)算速率。

網(wǎng)絡(luò)數(shù)據(jù)的高維稀疏性、非線性變化等多種因素使動態(tài)網(wǎng)絡(luò)鏈接預(yù)測任務(wù)變得更加復(fù)雜，但由于該任務(wù)的必要性和重要性，仍吸引了大批學(xué)者的關(guān)注。目前，大多數(shù)學(xué)者們主要基于動態(tài)網(wǎng)絡(luò)的歷史信息，推斷實(shí)體之間在未來形成鏈接的可能性。其本質(zhì)是在網(wǎng)絡(luò)中實(shí)體數(shù)量不變的情況下，研究未來這些實(shí)體之間存在鏈接的概率。

動態(tài)網(wǎng)絡(luò)鏈接問題可形式化描述，一個動態(tài)網(wǎng)絡(luò)可以表示成

筆者通過分析近幾年國內(nèi)外動態(tài)網(wǎng)絡(luò)鏈接預(yù)測相關(guān)研究工作，從所使用的技術(shù)路線的不同，主要分為以下兩個方面：一種是基于時間快照的方法，將動態(tài)網(wǎng)絡(luò)看成由多個不同的靜態(tài)歷史快照組成，通過對歷史快照進(jìn)行建模分析，進(jìn)而探索未來時間片中鏈接的狀態(tài)；另一種是基于時序感知網(wǎng)絡(luò)，主要通過建模網(wǎng)絡(luò)中鏈接的時序變化信息來預(yù)測下一時刻鏈接可能出現(xiàn)的概率。同時基于上述研究內(nèi)容，提出了當(dāng)前研究仍然存在的挑戰(zhàn)性問題。最后綜合考慮動態(tài)網(wǎng)絡(luò)鏈接預(yù)測的發(fā)展和目前存在的問題，對未來的研究提供了新的研究建議。

1 基于歷史快照的動態(tài)鏈接預(yù)測

基于歷史快照的研究方法主要是將動態(tài)網(wǎng)絡(luò)按照一定的時間段劃分成多個歷史快照，每個歷史快照代表那段時期網(wǎng)絡(luò)的狀態(tài)，通常稱這個時間段為時間窗口。每個時間窗口的網(wǎng)絡(luò)快照被統(tǒng)一成固定的拓?fù)錉顟B(tài)[5]?；诿總€歷史快照上的拓?fù)浼捌渌畔ⅲ芯空邆儾捎貌煌牟呗?，預(yù)測未來時刻網(wǎng)絡(luò)的鏈接狀態(tài)。

1.1 基于相似性指標(biāo)

由于靜態(tài)網(wǎng)絡(luò)中基于相似性指標(biāo)的鏈接預(yù)測方法計算簡單，且獲得了很好的預(yù)測效果，一些學(xué)者擴(kuò)展該方法到動態(tài)網(wǎng)絡(luò)研究中。該類方法通常使用時序預(yù)測模型來綜合考慮歷史快照的信息。GüNES et al[6]使用不同的相似性指標(biāo)計算歷史快照中節(jié)點(diǎn)對的相似性分?jǐn)?shù)，同時聯(lián)合鏈接交互的次數(shù)得到歷史快照的得分矩陣，之后將各個歷史快照的得分矩陣輸入到時序預(yù)測模型中預(yù)測最后一張快照的得分矩陣，得分越高，越容易形成鏈接。最近，BASU et al[7]通過設(shè)計特征實(shí)現(xiàn)鏈接的預(yù)測，將節(jié)點(diǎn)對的不同相似性指標(biāo)分?jǐn)?shù)、三種類型節(jié)點(diǎn)對(鏈接隨時間片穩(wěn)定不變的節(jié)點(diǎn)對數(shù)，鏈接隨時間片出現(xiàn)的節(jié)點(diǎn)對數(shù)，鏈接隨時間片消失的節(jié)點(diǎn)對數(shù)——包含一直沒有鏈接和鏈接被刪除的情況)的概率作為特征，并將所有歷史快照的特征矩陣輸入到時序預(yù)測模型中獲得最后一個時間片中節(jié)點(diǎn)對的特征，最后訓(xùn)練分類器預(yù)測最后一張時間片中鏈接的狀態(tài)。這些方法往往固定好歷史快照的相似性矩陣，隨后便完全依賴于相似性矩陣本身設(shè)計時序函數(shù)，這種只單一地捕獲網(wǎng)絡(luò)的時序特征，缺乏快照內(nèi)部節(jié)點(diǎn)關(guān)聯(lián)信息和不同快照之間鏈接變化的有效交互，導(dǎo)致無法更準(zhǔn)確地捕獲到網(wǎng)絡(luò)的動態(tài)演變信息。于是，NAJARI et al[8]利用快照內(nèi)部特征和快照間相似度來獲得鏈接存在的最終概率。其中，預(yù)測快照內(nèi)部鏈接分?jǐn)?shù)采用多種經(jīng)典相似性指標(biāo)獲取，快照間相似度的計算由預(yù)測鏈接在兩個快照中共有鄰居的概率與歷史快照中鏈接存在的相似性分?jǐn)?shù)的乘積得到。當(dāng)歷史快照的數(shù)量大于2時，則計算所有快照間相似度之和，最后綜合預(yù)測快照內(nèi)部特征和快照間相似度得到預(yù)測快照中鏈接形成的概率，結(jié)果得到明顯提升。

1.2 基于矩陣分解

為了獲得更高的準(zhǔn)確率，AHMED et al[9]從矩陣分解的角度提出了DeepEye，通過對歷史快照的鄰接矩陣進(jìn)行非負(fù)矩陣分解，獲得每個快照的潛在空間表示矩陣和系數(shù)矩陣；隨后，他們又設(shè)計了一致的低維潛在空間表示矩陣和低維系數(shù)矩陣來表示有效保留網(wǎng)絡(luò)的拓?fù)湫畔?，其目?biāo)是要最小化分解得到的潛在空間表示矩陣和該矩陣的損失。在計算每個矩陣時，先固定三個矩陣，通過最小化損失來不斷迭代更新，求取另外一個矩陣。最后一張時間片的相似矩陣由之前更新得到的系數(shù)矩陣取行向量的相似值得到。該方案證明了潛在的矩陣特征可以有效且更好地表達(dá)網(wǎng)絡(luò)的動態(tài)性。更進(jìn)一步地，LEI et al[10]提出自適應(yīng)多重非負(fù)矩陣因子分解(AM-NMF)模型，在分析其在各種網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用時，全面解決了時間鏈路預(yù)測問題。該模型結(jié)合了多個簡單NMF組件來學(xué)習(xí)動態(tài)網(wǎng)絡(luò)的統(tǒng)一低維表示。為進(jìn)一步考慮單個網(wǎng)絡(luò)快照的拓?fù)浣Y(jié)構(gòu)與整個動態(tài)網(wǎng)絡(luò)之間的關(guān)系，引入了一種新的自適應(yīng)參數(shù)，該參數(shù)伴隨著網(wǎng)絡(luò)表示矩陣的變化而相應(yīng)改變，從而自動調(diào)整不同時間片的網(wǎng)絡(luò)表示對整個網(wǎng)絡(luò)表示的相對貢獻(xiàn)。隨后為了更好地捕獲動態(tài)網(wǎng)絡(luò)的非線性特征，文獻(xiàn)[11]的作者首先對歷史快照的鄰接矩陣進(jìn)行非負(fù)矩陣分解，接著集成不同的時序預(yù)測方法，包括Holt-Winters[12]，VAR[13]和LSTM(long short-term memory,LSTM[14])預(yù)測未來時間片的鄰接矩陣，并證明三種時序預(yù)測方法中LSTM預(yù)測的結(jié)果更好。在面對大規(guī)模稀疏數(shù)據(jù)時，該類方法由于需要設(shè)計高維的矩陣，將面臨著增量計算的困難性和訓(xùn)練速度的低效性等問題。

1.3 基于深度學(xué)習(xí)模型

基于動態(tài)網(wǎng)絡(luò)深度模型的方法主要通過將網(wǎng)絡(luò)的歷史快照信息輸入到深度嵌入模型中，用以預(yù)測未來時刻快照的鏈接狀態(tài)。

生成模型受限玻爾茲曼機(jī)因其能夠進(jìn)行嵌入學(xué)習(xí)，開始被用于捕獲動態(tài)網(wǎng)絡(luò)的非線性特征[15]。LI et al[16]采用受限玻爾茲曼機(jī)學(xué)習(xí)歷史時間片的低維嵌入向量，并融入鄰居的影響以捕獲結(jié)構(gòu)信息，其中鄰居的影響因子通過計算局部鄰居存在概率的期望獲得。最后，結(jié)合歷史快照的信息和鄰居的影響因子共同預(yù)測最后一個時刻的網(wǎng)絡(luò)狀態(tài)。SAM DE WINTER et al[17]基于靜態(tài)網(wǎng)絡(luò)表征學(xué)習(xí)方法node2vec[18]學(xué)習(xí)歷史快照中節(jié)點(diǎn)的表示向量，未來時刻快照的邊表示通過拼接歷史快照中對應(yīng)節(jié)點(diǎn)向量的Hadamard乘積得到，并采用監(jiān)督學(xué)習(xí)的方式預(yù)測未來時刻邊的狀態(tài)。

然而，這些研究不足以捕捉網(wǎng)絡(luò)的動態(tài)性變化。長短期記憶(long short-term memory,LSTM)[14]和門控循環(huán)單元(gate recurrent unit,GRU)[19]等循環(huán)神經(jīng)網(wǎng)絡(luò)被用于建模動態(tài)網(wǎng)絡(luò)的時序特征。dyngraph2vec[20]設(shè)計了三種不同的模型來捕獲網(wǎng)絡(luò)的動態(tài)性，第一個模型簡單使用編解碼器對歷史快照的鄰接矩陣進(jìn)行低維表征，之后解碼預(yù)測未來時刻的鄰接矩陣；第二個模型將歷史快照的鄰接矩陣輸入到多層LSTM編解碼器中，預(yù)測最后時間片的表征；第三個模型結(jié)合了前兩種模型，先將歷史快照的鄰接矩陣通過編碼器編碼得到表征向量，之后輸入到LSTM網(wǎng)絡(luò)中，將預(yù)測得到的最后一個時間片的表示進(jìn)一步輸入到解碼器中得到未來時間片的鄰接矩陣。實(shí)驗(yàn)結(jié)果表明，通過第三種模型獲得的平均準(zhǔn)確率最好。隨后，LEI et al[21]基于加權(quán)動態(tài)網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測。首先利用GCN[22]捕獲每個網(wǎng)絡(luò)快照拓?fù)浣Y(jié)構(gòu)的特征；然后，將學(xué)習(xí)到的網(wǎng)絡(luò)表示特征輸入到LSTM網(wǎng)絡(luò)中，捕獲具有多個連續(xù)時間片的加權(quán)動態(tài)網(wǎng)絡(luò)的演化模式；最后，在對抗性訓(xùn)練的基礎(chǔ)上，利用GAN[23]生成了高質(zhì)量、可信的圖形快照。由于上述模型缺乏對局部結(jié)構(gòu)信息的考慮，LI et al[24]進(jìn)一步提出了深度動態(tài)網(wǎng)絡(luò)嵌入模型，該模型將節(jié)點(diǎn)的高維稀疏鄰接向量輸入到GRU神經(jīng)網(wǎng)絡(luò)中來捕獲節(jié)點(diǎn)層次的動態(tài)性變化特征，同時加入了節(jié)點(diǎn)之間的交互作用對目標(biāo)函數(shù)進(jìn)行約束，使其包含局部結(jié)構(gòu)信息。其中，邊的交互約束通過節(jié)點(diǎn)對之間交互的頻率和經(jīng)過GRU編碼后節(jié)點(diǎn)對向量的距離得到。雖然該類研究方法可以獲得較高的預(yù)測準(zhǔn)確率，但由于選擇的時間快照窗口是固定的，而網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化的時間段不是固定的。因此該類方法無法更好地應(yīng)對連續(xù)、快速變化的網(wǎng)絡(luò)結(jié)構(gòu)。

2 基于時間感知的動態(tài)鏈接預(yù)測

網(wǎng)絡(luò)中鏈接的強(qiáng)度受到多種因素的影響，大多數(shù)情況下，鏈接存在的概率與兩個節(jié)點(diǎn)之間保持聯(lián)系的時間有著強(qiáng)烈的關(guān)系[25]。因此，一些研究方法單獨(dú)對鏈接變化建模時序信息，實(shí)現(xiàn)動態(tài)網(wǎng)絡(luò)的鏈接預(yù)測。

2.1 基于時序分?jǐn)?shù)

早期加入時序信息進(jìn)行鏈接預(yù)測的方法，主要通過融入時序權(quán)重，計算不同節(jié)點(diǎn)間鏈接關(guān)系的相似度分?jǐn)?shù)，其中相似分?jǐn)?shù)越高，越容易形成鏈接[26]。TYLENDA et al[27]在論文協(xié)作網(wǎng)中考慮了三種不同的影響因子作為鏈接的權(quán)重，其中關(guān)于時間的影響因子通過用戶之間最近合作論文發(fā)布的時間來獲得，用戶的未來可能合作對象根據(jù)節(jié)點(diǎn)與不同鄰居的鏈接強(qiáng)度系數(shù)排序獲得。同一時期，HUANG et al[28]混合了時序預(yù)測分?jǐn)?shù)和靜態(tài)鏈接相似分?jǐn)?shù)，該文基于歷史鏈接的交互次數(shù)，采用時序預(yù)測模型，預(yù)測未來鏈接存在的分?jǐn)?shù)，計為時序分?jǐn)?shù)；同時將不同時期歷史快照的鄰接矩陣加和得到一個矩陣，變換為二值矩陣后，應(yīng)用相似性指標(biāo)(例如，共同鄰居)獲取得分矩陣，通過綜合兩種方法得到最后的鏈接概率矩陣。隨后，SOARES et al[29]設(shè)計了更多的時序預(yù)測模型(包括移動平均，線性指數(shù)平滑等)來更好地描述網(wǎng)絡(luò)的演變特性。為了進(jìn)一步提升鏈接的準(zhǔn)確性，一些研究者引入了新的時序分?jǐn)?shù)，不僅捕捉鏈接強(qiáng)度的相似分?jǐn)?shù)，同時還捕捉了節(jié)點(diǎn)在不同時間戳之間的交互分?jǐn)?shù)(例如：節(jié)點(diǎn)a在t1時刻，b在t2時刻，a和b之間所有共同鄰居的共現(xiàn)頻率加權(quán)之和作為鏈接時序交互分?jǐn)?shù))[30]和不同鏈接類型的時序分?jǐn)?shù)(對鏈接在不同時刻的多種狀態(tài)施加獎勵分?jǐn)?shù))[31]等。近來，一些學(xué)者應(yīng)用時序信息到鏈接權(quán)重上，作為隨機(jī)游走轉(zhuǎn)移的概率來計算節(jié)點(diǎn)間交互的信息率，高的信息率更容易形成鏈接[25]。AHMED et al[32]首次將不同的快照通過時序衰減函數(shù)(確保更近的快照更重要)組合成一個加權(quán)圖作為概率矩陣，之后進(jìn)行局部隨機(jī)游走獲得采樣節(jié)點(diǎn)序列，對這些采樣得到的節(jié)點(diǎn)集，分別計算相似分?jǐn)?shù)。隨后，AHMED和CHEN[33]擴(kuò)展該方法到不確定網(wǎng)絡(luò)中。緊接著，一些新的思想開始被融入到動態(tài)網(wǎng)絡(luò)中計算相似性分?jǐn)?shù)。LIU et al[34]基于信息傳播的思想，首先在動態(tài)演化圖中利用Dijkstra算法找到節(jié)點(diǎn)與圖中所有節(jié)點(diǎn)的最短路徑，并轉(zhuǎn)化為傳播概率，添加傳播概率大于設(shè)定值的最大路徑影響集，兩個節(jié)點(diǎn)的最大路徑影響集的交集記為共同影響集，相似性分?jǐn)?shù)的計算為：目標(biāo)預(yù)測鏈接中節(jié)點(diǎn)分別與共同影響集中節(jié)點(diǎn)的影響分?jǐn)?shù)的乘積。然而，這些方法僅簡單利用了時間特征，并且大多數(shù)研究使用復(fù)雜的方法，卻不能有效地學(xué)習(xí)動態(tài)網(wǎng)絡(luò)的演化過程。

2.2 基于表示學(xué)習(xí)

隨著表示學(xué)習(xí)的發(fā)展，JIANG et al[35]基于Trans E模型，對中間關(guān)系的信息融入時序轉(zhuǎn)移矩陣信息來約束知識庫網(wǎng)絡(luò)的嵌入，在嵌入過程中同時優(yōu)化基于翻譯機(jī)制的約束和時序信息的約束。NGUYEN et al[36]將時間系數(shù)作為權(quán)重參數(shù)置于網(wǎng)絡(luò)中，通過隨機(jī)游走選擇時序遞增的節(jié)點(diǎn)，節(jié)點(diǎn)的嵌入向量通過優(yōu)化節(jié)點(diǎn)表征函數(shù)來得到，之后融合節(jié)點(diǎn)的表示形成邊的表示進(jìn)行分類預(yù)測。

SAJADMANESH et al[37]首次將連續(xù)時間網(wǎng)絡(luò)和異質(zhì)網(wǎng)絡(luò)聯(lián)合起來進(jìn)行鏈接預(yù)測。該文設(shè)計了基于元路徑的時序感知特征，通過元路徑的方式來捕獲異質(zhì)網(wǎng)絡(luò)的信息。其中時序感知按照結(jié)點(diǎn)對的生成時間和消亡時間進(jìn)行定義，同時將得到的基于元路徑的時序感知特征輸入到基于自編碼器的循環(huán)神經(jīng)網(wǎng)絡(luò)中，用于獲取具有時序性的節(jié)點(diǎn)對的低維表示。最后又設(shè)計了非參數(shù)模型將得到的鏈接特征表示融合為單一的特征表示，通過計算在某個時間段內(nèi)形成關(guān)系的概率，實(shí)現(xiàn)鏈接預(yù)測。近幾年，LIU et al[38]將時序表示學(xué)習(xí)應(yīng)用到多關(guān)系網(wǎng)絡(luò)中，通過對每個時期的網(wǎng)絡(luò)分別應(yīng)用SVD分解得到節(jié)點(diǎn)的嵌入向量，之后采用Hawkes過程建模具有時序信息的關(guān)系序列，最后通過結(jié)合節(jié)點(diǎn)嵌入的乘積和關(guān)系序列來獲得鏈接的預(yù)測概率，該模型在大規(guī)模網(wǎng)絡(luò)上獲得不錯的鏈接預(yù)測效果。此類方法基于表示學(xué)習(xí)，設(shè)計融入了更多的時序特征信息，同時也獲得了更好的預(yù)測效果。然而該類方法不能更好地解釋每個時序特征，設(shè)計實(shí)現(xiàn)一種具有可解釋性的模型可以幫助更好地改進(jìn)表示學(xué)習(xí)得到的時序特征，以便得到最佳的預(yù)測性能。

3 面臨的挑戰(zhàn)和未來研究方向

3.1 異質(zhì)動態(tài)網(wǎng)絡(luò)鏈接預(yù)測

隨著網(wǎng)絡(luò)數(shù)據(jù)的稀疏性、復(fù)雜性、時序性以及規(guī)模擴(kuò)大等問題的出現(xiàn)，涉及復(fù)雜關(guān)聯(lián)的大規(guī)模異質(zhì)性真實(shí)網(wǎng)絡(luò)給鏈接預(yù)測帶來了新的挑戰(zhàn)。異質(zhì)網(wǎng)絡(luò)包含了不同類型的節(jié)點(diǎn)和邊，且不同類的對象均蘊(yùn)含著豐富的語義信息，需要從多個維度來刻畫不同類對象的意義。因此，如何有效地抽取和利用異質(zhì)網(wǎng)絡(luò)中不同類對象的多維特征信息，并有效地融合這些信息，以便全面地學(xué)習(xí)動態(tài)網(wǎng)絡(luò)的時序特征成為了一個巨大的挑戰(zhàn)。

3.2 不確定性動態(tài)網(wǎng)絡(luò)鏈接預(yù)測

在實(shí)際生活中，常常因?yàn)楦鞣N不同的原因?qū)е戮W(wǎng)絡(luò)數(shù)據(jù)信息采集的不精確，采用該類數(shù)據(jù)得到的網(wǎng)絡(luò)稱之為不確定性網(wǎng)絡(luò)。在不確定性網(wǎng)絡(luò)研究中，節(jié)點(diǎn)被認(rèn)為是確定存在的，而每條邊的存在則有一定的概率。由于在不確定性網(wǎng)絡(luò)中，建模節(jié)點(diǎn)對的相似性需要枚舉更多的可能性情況，這也導(dǎo)致了該類網(wǎng)絡(luò)實(shí)現(xiàn)鏈接預(yù)測的困難性。

3.3 準(zhǔn)確性、高效性和可擴(kuò)展性

大數(shù)據(jù)時代的到來產(chǎn)生了越來越多復(fù)雜的網(wǎng)絡(luò)數(shù)據(jù)，同時也導(dǎo)致了現(xiàn)有動態(tài)網(wǎng)絡(luò)鏈接預(yù)測模型的準(zhǔn)確性和執(zhí)行效率的降低，且大多數(shù)網(wǎng)絡(luò)模型只在特定的網(wǎng)絡(luò)結(jié)構(gòu)中表現(xiàn)良好，當(dāng)涉及到其他領(lǐng)域中不同的網(wǎng)絡(luò)結(jié)構(gòu)時，其表現(xiàn)力將發(fā)生不同程度的下降。因此，如何設(shè)計一個通用、靈活和高效的網(wǎng)絡(luò)模型用于動態(tài)網(wǎng)絡(luò)鏈接預(yù)測仍然是一個很大的挑戰(zhàn)。

4 結(jié)束語

本文從研究動態(tài)網(wǎng)絡(luò)鏈接預(yù)測的兩種角度入手，分別闡述了基于歷史快照和基于時間感知建模動態(tài)網(wǎng)絡(luò)鏈接預(yù)測的不同方法。每種方法按不同類別研究的先后順序展現(xiàn)動態(tài)網(wǎng)絡(luò)鏈接預(yù)測的研究發(fā)展情況。并在此基礎(chǔ)上總結(jié)了目前尚未完全解決的幾大研究挑戰(zhàn)，希望為今后的研究方向提供借鑒和參考。