劉林峰 于子興 祝賀

（南京郵電大學(xué)計(jì)算機(jī)學(xué)院 南京 210023）

隨著時(shí)代的進(jìn)步，網(wǎng)絡(luò)的概念逐漸多元化，衍生出如互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、經(jīng)濟(jì)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等各種網(wǎng)絡(luò)形式.在現(xiàn)實(shí)世界中，網(wǎng)絡(luò)扮演著重要的角色，網(wǎng)絡(luò)可以將現(xiàn)實(shí)世界中的具體問題抽象描述為一個(gè)復(fù)雜的網(wǎng)絡(luò)系統(tǒng).網(wǎng)絡(luò)可以分為靜態(tài)網(wǎng)絡(luò)和動(dòng)態(tài)網(wǎng)絡(luò)2 類，現(xiàn)實(shí)世界中絕大多數(shù)網(wǎng)絡(luò)都屬于動(dòng)態(tài)網(wǎng)絡(luò)，這些網(wǎng)絡(luò)中的節(jié)點(diǎn)、鏈路都會(huì)隨著時(shí)間的推移而消失或出現(xiàn).此外，網(wǎng)絡(luò)中鏈路代表著不同實(shí)體之間產(chǎn)生的行為或者偏向，所以分析并預(yù)測(cè)這些網(wǎng)絡(luò)中的鏈路具有重要的意義.

網(wǎng)絡(luò)的鏈路預(yù)測(cè)通常是指預(yù)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的潛在關(guān)系，如何提高預(yù)測(cè)性能一直是網(wǎng)絡(luò)科學(xué)的一個(gè)挑戰(zhàn).性能優(yōu)異的鏈路預(yù)測(cè)方法能夠更好地理解網(wǎng)絡(luò)的演變，從網(wǎng)絡(luò)中提煉出更有價(jià)值的信息，比如蛋白質(zhì)相互作用網(wǎng)絡(luò)中[1]，酵母菌與蛋白質(zhì)之間80%的相互作用不為人知，如果在已知網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)足夠精確的鏈路預(yù)測(cè)方法再進(jìn)行預(yù)測(cè)指導(dǎo)實(shí)驗(yàn)，就能夠提高實(shí)驗(yàn)成功率、降低測(cè)試成本.

移動(dòng)社會(huì)網(wǎng)絡(luò)[2]是一種典型的動(dòng)態(tài)網(wǎng)絡(luò)，如果將網(wǎng)絡(luò)映射到圖中，則節(jié)點(diǎn)代表人或?qū)嶓w，鏈路代表節(jié)點(diǎn)間的聯(lián)系.由于這種聯(lián)系具有時(shí)間特征，所以導(dǎo)致了網(wǎng)絡(luò)的高度動(dòng)態(tài)性和復(fù)雜性.

移動(dòng)社會(huì)網(wǎng)絡(luò)的鏈路預(yù)測(cè)可以預(yù)測(cè)人與人之間的交互，分析這種交互可以一定程度上得知一個(gè)人的交往或性格傾向，甚至能夠判斷該用戶可能需要的服務(wù).比如出租車司機(jī)可以更加容易在合適的地點(diǎn)找到乘客，陌生人之間更容易找到意氣相投的朋友，賣家能夠更加精準(zhǔn)地為買家提供他們所需的商品.精準(zhǔn)的鏈路預(yù)測(cè)能夠?yàn)橐苿?dòng)社會(huì)網(wǎng)絡(luò)降低資源開銷，給人們的生活帶來極大的便利.圖1 為一個(gè)移動(dòng)社會(huì)網(wǎng)絡(luò)示意圖，比如在道路上用戶通過藍(lán)牙或車載局域網(wǎng)絡(luò)進(jìn)行通信，在小區(qū)里人們使用智能設(shè)備接入WiFi 信號(hào)點(diǎn)進(jìn)行信息交互，也可以通過無線信號(hào)接入互聯(lián)網(wǎng)并連接服務(wù)器，由服務(wù)器來控制用戶之間的通信.

Fig.1 Example diagram of mobile social network圖1 移動(dòng)社會(huì)網(wǎng)絡(luò)示意圖

1 相關(guān)工作

鏈路預(yù)測(cè)的目的在于根據(jù)網(wǎng)絡(luò)的歷史信息來預(yù)測(cè)未來的網(wǎng)絡(luò)結(jié)構(gòu)，這可以更好地理解網(wǎng)絡(luò)的演變，發(fā)掘網(wǎng)絡(luò)中有價(jià)值的信息.

目前，鏈路預(yù)測(cè)方法主要分為3 種：基于節(jié)點(diǎn)相似性的鏈路預(yù)測(cè)方法、基于矩陣分解的鏈路預(yù)測(cè)方法、基于機(jī)器學(xué)習(xí)的鏈路預(yù)測(cè)方法.

1.1 基于節(jié)點(diǎn)相似性的鏈路預(yù)測(cè)方法

基于節(jié)點(diǎn)相似性的鏈路預(yù)測(cè)方法是指基于網(wǎng)絡(luò)中節(jié)點(diǎn)的結(jié)構(gòu)信息、屬性信息和行為去評(píng)估節(jié)點(diǎn)間的相似度，若節(jié)點(diǎn)間的相似度越高，則表明該對(duì)節(jié)點(diǎn)越相似，即產(chǎn)生鏈路的可能性越大.

目前廣泛應(yīng)用于靜態(tài)網(wǎng)絡(luò)的鏈路預(yù)測(cè)指標(biāo)有很多，例如共同鄰居算法（common neighbors,CN）[3]、資源分配指標(biāo)（resource allocation index,RA）[4].在此基礎(chǔ)上，文獻(xiàn)[5]基于節(jié)點(diǎn)相似性算法和事件檢測(cè)算法提出一種社會(huì)網(wǎng)絡(luò)事件鏈路預(yù)測(cè)方法，該方法對(duì)不同網(wǎng)絡(luò)的演變性進(jìn)行統(tǒng)一評(píng)價(jià)，并依此建立事件檢測(cè)模型，并利用該模型完成鏈路預(yù)測(cè).文獻(xiàn)[6]提出了基于節(jié)點(diǎn)度和聚類系數(shù)的共同鄰居緊密度指數(shù)，認(rèn)為節(jié)點(diǎn)的共同鄰居之間的關(guān)系越緊密，節(jié)點(diǎn)間連接的可能性就越高.文獻(xiàn)[7]考慮了用戶活動(dòng)和其共同的鄰居，并定義了局部和全局鏈路預(yù)測(cè)算法對(duì)節(jié)點(diǎn)之間的相似度進(jìn)行評(píng)估.文獻(xiàn)[8]重點(diǎn)關(guān)注了鏈路方向在鏈路預(yù)測(cè)問題中的作用，認(rèn)為雙向鏈路可能包含更多的網(wǎng)絡(luò)信息，并發(fā)現(xiàn)具有雙向鏈路的小部分節(jié)點(diǎn)更有可能通過雙向鏈路連接到共同的鄰居.文獻(xiàn)[9]認(rèn)為現(xiàn)有的計(jì)算節(jié)點(diǎn)相似度方法中公共鄰居的數(shù)量只描述了一種定量關(guān)系，沒有考慮給定網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，于是引入節(jié)點(diǎn)度的概念和社區(qū)結(jié)構(gòu)的思想，提出了局部親和結(jié)構(gòu)，然后與其他相似度指標(biāo)在不同網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，最終提高了鏈路預(yù)測(cè)精準(zhǔn)度.

文獻(xiàn)[3-9]中的預(yù)測(cè)方法主要在拓?fù)渥兓徛虬l(fā)生變化較少的網(wǎng)絡(luò)中性能較好，因此當(dāng)應(yīng)用場(chǎng)景中網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間頻繁發(fā)生變化時(shí)，預(yù)測(cè)效果大大削弱.

1.2 基于矩陣分解的鏈路預(yù)測(cè)方法

基于矩陣分解的鏈路預(yù)測(cè)方法是指利用矩陣分解得到的低秩矩陣來解決鏈路預(yù)測(cè)問題.其中，矩陣通常由鄰接矩陣或提取的其他網(wǎng)絡(luò)結(jié)構(gòu)信息矩陣組成.目前，矩陣分解主要有奇異值分解、非負(fù)矩陣分解和概率矩陣分解.

文獻(xiàn)[10]提出了一種動(dòng)態(tài)網(wǎng)絡(luò)的鏈路預(yù)測(cè)方法，該方法從第一張網(wǎng)絡(luò)快照中得到特征矩陣，并求解其低秩矩陣.然后，根據(jù)后續(xù)網(wǎng)絡(luò)快照不斷更新低秩矩陣，最終利用差值估算未來時(shí)刻節(jié)點(diǎn)之間鏈路的可能性.文獻(xiàn)[11]指出，現(xiàn)有的鏈路預(yù)測(cè)算法缺乏對(duì)社會(huì)信息網(wǎng)絡(luò)中的拓?fù)湫畔⒑头峭負(fù)湫畔⒌挠行诤希虼嘶谟脩糁黝}信息定義了用戶主題相似度指數(shù)，并基于該指數(shù)構(gòu)造主題相似度矩陣，然后將目標(biāo)網(wǎng)絡(luò)的信息和主題相似度矩陣融合到概率矩陣分解框架中，并在此基礎(chǔ)上得到網(wǎng)絡(luò)節(jié)點(diǎn)的表示，最后根據(jù)得到的隱含特征表示計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)之間產(chǎn)生鏈路的概率.文獻(xiàn)[12]將動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間變化的特性融合到非負(fù)矩陣分解中，提出了一種非負(fù)矩陣分解迭代規(guī)則，然后根據(jù)矩陣分解的結(jié)果得到網(wǎng)絡(luò)的相似度矩陣，從而完成了鏈路預(yù)測(cè).文獻(xiàn)[13]采用非負(fù)矩陣分解的方法提取了時(shí)間序列圖的潛在特征，采用Holt-Winters 時(shí)間序列預(yù)測(cè)方法學(xué)習(xí)，并提取潛在特征的時(shí)域信息，以此較好地解決了鏈路預(yù)測(cè)問題.

基于矩陣分解的鏈路預(yù)測(cè)方法主要是對(duì)網(wǎng)絡(luò)的鄰接矩陣進(jìn)行低秩分解，通過迭代分解矩陣，提取動(dòng)態(tài)網(wǎng)絡(luò)的時(shí)變特征.然而在大規(guī)模動(dòng)態(tài)網(wǎng)絡(luò)中，迭代矩陣分解會(huì)導(dǎo)致極高的時(shí)間復(fù)雜度，會(huì)增加系統(tǒng)的響應(yīng)時(shí)間和影響用戶的使用體驗(yàn).

1.3 基于機(jī)器學(xué)習(xí)的鏈路預(yù)測(cè)方法

基于機(jī)器學(xué)習(xí)的預(yù)測(cè)方法是指利用機(jī)器學(xué)習(xí)算法從一定角度提取網(wǎng)絡(luò)中數(shù)據(jù)的特征，從而實(shí)現(xiàn)鏈路預(yù)測(cè).

文獻(xiàn)[14]考慮到個(gè)體偏好可能是形成鏈路的主要原因，將效用分析概念引入到鏈路預(yù)測(cè)問題中，并關(guān)注了鏈路形成過程中潛在變量的演變過程.由此，將鏈路預(yù)測(cè)問題定義為一個(gè)帶有潛在變量的機(jī)器學(xué)習(xí)過程，并采用期望最大化算法來解決鏈路預(yù)測(cè)問題.文獻(xiàn)[15]應(yīng)用圖卷積網(wǎng)絡(luò)（graph convolutional network,GCN）、長(zhǎng)短期 記憶網(wǎng) 絡(luò)（long short-term memory,LSTM）和生成對(duì)抗網(wǎng)絡(luò)（generative adversarial network,GAN）提取加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)中鏈路變化的非線性特征，并利用GCN 獲取每個(gè)快照的局部特征，然后利用LSTM 來提取動(dòng)態(tài)網(wǎng)絡(luò)的演化特征，以此提高了預(yù)測(cè)模型的準(zhǔn)確性.文獻(xiàn)[16]針對(duì)單鏈鏈路預(yù)測(cè)指標(biāo)普適性較差的問題，提出了一種基于密度峰值聚類的自適應(yīng)鏈路預(yù)測(cè)方法.該方法采用不同的鏈路預(yù)測(cè)指標(biāo)作為鏈路的屬性，并利用聚類分析將鏈路預(yù)測(cè)問題轉(zhuǎn)化為分類問題.文獻(xiàn)[17]將關(guān)系主題模型和貝葉斯深度學(xué)習(xí)框架相結(jié)合，構(gòu)建了關(guān)系深度學(xué)習(xí)模型，然后推導(dǎo)出廣義變分推理算法來學(xué)習(xí)變量，并完成鏈路預(yù)測(cè).文獻(xiàn)[18]將多節(jié)點(diǎn)鏈路預(yù)測(cè)問題轉(zhuǎn)化為模式分類問題，通過對(duì)網(wǎng)絡(luò)進(jìn)行劃分獲得一系列網(wǎng)絡(luò)快照，并計(jì)算每個(gè)快照的狀態(tài)圖，然后構(gòu)建基于卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network,CNN）的預(yù)測(cè)模型，提取圖的演變特征，從而實(shí)現(xiàn)了多節(jié)點(diǎn)的鏈路預(yù)測(cè).文獻(xiàn)[19]將動(dòng)態(tài)網(wǎng)絡(luò)劃分為一系列時(shí)間序列快照，利用自動(dòng)編碼器和LSTM 構(gòu)建模型，以此實(shí)現(xiàn)鏈路預(yù)測(cè).文獻(xiàn)[20]分析了動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)的特性，提出了時(shí)間感知多關(guān)系鏈路預(yù)測(cè)的特征集，然后構(gòu)建并訓(xùn)練了基于隨機(jī)深層森林的預(yù)測(cè)模型，并對(duì)特定類型的鏈路進(jìn)行了預(yù)測(cè).

基于機(jī)器學(xué)習(xí)的鏈路預(yù)測(cè)方法是通過大量數(shù)據(jù)訓(xùn)練深度學(xué)習(xí)模型，再使用訓(xùn)練完畢的模型對(duì)網(wǎng)絡(luò)完成鏈路預(yù)測(cè).然而真實(shí)數(shù)據(jù)的復(fù)雜性以及動(dòng)態(tài)網(wǎng)絡(luò)的稀疏性嚴(yán)重影響了模型的訓(xùn)練效果，導(dǎo)致模型預(yù)測(cè)性能下降.

針對(duì)上述研究現(xiàn)狀，本文提出了一種用于移動(dòng)社會(huì)網(wǎng)絡(luò)的鏈路預(yù)測(cè)模型（encoder-GRUs-decoder,EGRUs-D），能夠較好地解決真實(shí)數(shù)據(jù)高維度、非線性所造成的鏈路預(yù)測(cè)困難，同時(shí)還能緩解數(shù)據(jù)稀疏性導(dǎo)致模型訓(xùn)練時(shí)可能產(chǎn)生局部最優(yōu)的問題.由于采用了自動(dòng)編碼器的結(jié)構(gòu)，該模型可以幾乎無損地學(xué)習(xí)網(wǎng)絡(luò)表示，并根據(jù)所提取的信息重構(gòu)網(wǎng)絡(luò)圖.經(jīng)過編碼器模塊降維后的數(shù)據(jù)更容易被堆疊的門控循環(huán)單 元（gated recurrent unit,GRU）模塊學(xué) 習(xí).本文在KONECT 的3 個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn).結(jié)果表明，相比于其他方法，E-GRUs-D 模型預(yù)測(cè)性能良好，且在訓(xùn)練效率方面優(yōu)勢(shì)明顯.本文主要貢獻(xiàn)有2 個(gè)方面：

1）提出了一種E-GRUs-D 深度學(xué)習(xí)模型來預(yù)測(cè)移動(dòng)社會(huì)網(wǎng)絡(luò)中的鏈路，自動(dòng)編碼器結(jié)構(gòu)能夠以較少的損耗學(xué)習(xí)網(wǎng)絡(luò)表示，同時(shí)在輸入時(shí)降低數(shù)據(jù)維度以減少堆疊GRU 模塊的工作量，并在輸出時(shí)能夠根據(jù)提取的特征還原數(shù)據(jù)維度.GRUs 模塊能夠有效學(xué)習(xí)數(shù)據(jù)的時(shí)變特征，保證了預(yù)測(cè)結(jié)果的準(zhǔn)確性.

2）E-GRUs-D 模型在保持預(yù)測(cè)準(zhǔn)確率良好的基礎(chǔ)上，極大地縮短了訓(xùn)練時(shí)間.通過改變不同隱藏層單元的數(shù)量，能夠適用不同規(guī)模的網(wǎng)絡(luò)，具有較好的可擴(kuò)展性.

2 方法描述

2.1 問題定義

在固定時(shí)間間隔下生成的一系列快照?qǐng)D可以用來表示一個(gè)移動(dòng)社會(huì)網(wǎng)絡(luò).

定義1.移動(dòng)社會(huì)網(wǎng)絡(luò).假設(shè)有一組圖序列（G1,G2,…,Gt），其中Gk＝（V，Ek）表示移動(dòng)社會(huì)網(wǎng)絡(luò)的第k張快照?qǐng)D.V表 示節(jié)點(diǎn)集 合，Ek?V×V表 示第k時(shí)刻快照中節(jié)點(diǎn)的鏈路情況.假設(shè)Ak表示圖Gk的鄰接矩陣，若節(jié)點(diǎn)vi和節(jié)點(diǎn)vj在時(shí)刻k產(chǎn)生鏈路，則矩陣Ak的元素ak;i,j＝1，否則ak;i,j＝0.

在靜態(tài)網(wǎng)絡(luò)中，鏈路預(yù)測(cè)主要根據(jù)已觀測(cè)到的鏈路分布來尋找實(shí)際存在的未知鏈路.而預(yù)測(cè)動(dòng)態(tài)網(wǎng)絡(luò)時(shí)則需要利用網(wǎng)絡(luò)的歷史信息，尋找網(wǎng)絡(luò)演變的規(guī)律.由于鄰接矩陣能夠簡(jiǎn)化網(wǎng)絡(luò)中節(jié)點(diǎn)鏈路情況的描述，所以本文模型的輸入和輸出將以鄰接矩陣的形式進(jìn)行設(shè)置.雖然這些相鄰時(shí)刻的網(wǎng)絡(luò)圖聯(lián)系較為密切，也許僅僅通過上一時(shí)刻圖Gt-1也能預(yù)測(cè)下一時(shí)刻圖Gt中節(jié)點(diǎn)的鏈路狀況，但是這種預(yù)測(cè)方法存在一定的缺陷，因?yàn)閳DGt中包含的特征太少，并且隨著時(shí)間的推移，網(wǎng)絡(luò)結(jié)構(gòu)會(huì)不斷發(fā)生改變，所以只使用一張圖預(yù)測(cè)時(shí)效果不佳，故本文使用一組長(zhǎng)度為N的圖序列（Gt-N,Gt-(N-1),…,Gt-1）來預(yù)測(cè)下一時(shí)刻網(wǎng)絡(luò)圖Gt.

定義2.移動(dòng)社會(huì)網(wǎng)絡(luò)的鏈路預(yù)測(cè).定義一組長(zhǎng)度為N的圖序列S，其中S＝（Gt-N,Gt-(N-1),…,Gt-1），本文使用E-GRUs-D 模型學(xué)習(xí)網(wǎng)絡(luò)的演變，使得輸入圖序列S后可獲得圖Gt.

移動(dòng)社會(huì)網(wǎng)絡(luò)鏈路變化示例圖如圖2 所示.假設(shè)圖2（a）為時(shí)刻t＝1 的網(wǎng)絡(luò)鏈路情況，圖2（b）為時(shí)刻t＝2 的網(wǎng)絡(luò) 鏈路情 況.在下一時(shí)刻，邊E（1,4）和 邊E（5,3）消失，而邊E（4,5）和邊E（1,5）出現(xiàn)，在鄰接矩陣上則可體現(xiàn)為對(duì)應(yīng)元素由0 變?yōu)?，或者由1 變?yōu)?.通過鄰接矩陣可以清晰地觀測(cè)到鏈接的出現(xiàn)或消失.本文主要通過節(jié)點(diǎn)的歷史信息來預(yù)測(cè)目標(biāo)時(shí)刻可能出現(xiàn)的鏈路，如果將這一過程映射到鄰接矩陣上，即觀察矩陣中哪些元素的數(shù)值由0 變?yōu)?.

Fig.2 Example diagram of link changes in mobile social network圖2 移動(dòng)社會(huì)網(wǎng)絡(luò)鏈路變化示例圖

2.2 E-GRUs-D 模型

本文提出了一種用于移動(dòng)社會(huì)網(wǎng)絡(luò)鏈路預(yù)測(cè)的深度學(xué)習(xí)模型E-GRUs-D，該模型如圖3 所示.E-GRUs-D 由自動(dòng)編碼器模塊和GRUs 模塊組成.GRUs 模塊中包含多個(gè)GRU 細(xì)胞，如圖4 所示，其中H0表示初始時(shí)刻的候選狀態(tài)數(shù)值，Ht-1為最后一個(gè)GRU 細(xì)胞的輸出，即最終提取到的時(shí)變特征.（Xt-N,Xt-(N-1),…,Xt-1）表示（Gt-N,Gt-(N-1),…,Gt-1）降維度處理后的輸入圖序列.

循環(huán)神經(jīng)網(wǎng)絡(luò)（recurrent neural network,RNN）的變體有2 種：GRU 和LSTM，它們的數(shù)據(jù)輸入方式也與RNN 相似，通過這種依次輸入并記憶再輸入的循環(huán)方式，能夠較好地增強(qiáng)數(shù)據(jù)之間的聯(lián)系，提高模型在處理時(shí)間序列時(shí)的預(yù)測(cè)性能.此外，由于GRU 細(xì)胞結(jié)構(gòu)的簡(jiǎn)潔性，其訓(xùn)練效率比LSTM 更勝一籌.

基于自動(dòng)編碼器的特性，本文將編碼器部分和解碼器部分分別放置于模型的輸入端和輸出端，在自動(dòng)編碼器模塊之間加入GRUs 模塊來提取數(shù)據(jù)的時(shí)變性.

1）自動(dòng)編碼器結(jié)構(gòu).自動(dòng)編碼器能夠以無監(jiān)督學(xué)習(xí)的方式以較低損耗的代價(jià)學(xué)習(xí)網(wǎng)絡(luò)表示，其核心思想是實(shí)現(xiàn)函數(shù)y（x）=x的功能，即模型的輸入等于模型輸出.因此，將編碼器放在模型的輸入端來捕捉高階非線性的網(wǎng)絡(luò)結(jié)構(gòu)，將解碼器放在模型的輸出端，使提取到的時(shí)變特征還原到先前的維度，并嵌入到網(wǎng)絡(luò)的鄰接矩陣中.由于初步輸出的矩陣中元素?cái)?shù)值為0 的個(gè)數(shù)遠(yuǎn)遠(yuǎn)大于元素?cái)?shù)值為1 的個(gè)數(shù)，這可能導(dǎo)致解碼器更傾向于忽略那些數(shù)值為1 的元素，即那些已經(jīng)存在的鏈路，所以需要引導(dǎo)解碼器更注重于先前數(shù)值為1 的元素去構(gòu)建矩陣.編碼器的執(zhí)行過程表示為：

Fig.3 E-GRUs-D model structure圖3 E-GRUs-D 模型結(jié)構(gòu)

Fig.4 GRUs module details圖4 GRUs 模塊細(xì)節(jié)

式（1）中，si表示輸入序列S的第i張圖的鄰接矩陣.式（2）中，We;k和be;k表示第k層編碼器的權(quán)值矩陣和偏置矩陣，表示第k層編碼器輸入第i張圖產(chǎn)生的輸出.式（3）中，Ye;k表示第k層編碼器輸入整個(gè)序列時(shí)產(chǎn)生的輸出.對(duì)于編碼器層激活函數(shù)的選取，本文保存了自動(dòng)編碼器結(jié)構(gòu)的默認(rèn)設(shè)置，仍選取ReLU作為其激活函數(shù).

編碼器部分和解碼器部分互為鏡像結(jié)構(gòu)，它接收GRUs 模塊學(xué)習(xí)而來的特征，重構(gòu)先前的空間結(jié)構(gòu)并將它們映射到鄰接矩陣內(nèi)，該過程表示為：

式（4）中，U表示GRUs 結(jié)構(gòu)的輸出，即提取到的特征.式（5）中，Wd;k和bd;k表示第k層解碼器的權(quán)值矩陣和偏置矩陣，Yd;k表示第k層解碼器的輸出.該結(jié)構(gòu)仍和編碼器結(jié)構(gòu)一樣，選取ReLU作為其激活函數(shù).式（6）中 σ表示激活函數(shù)Sigmoid，這是為了在解碼器的最后一層實(shí)現(xiàn)歸一化處理.

2）GRUs 結(jié)構(gòu).雖然自動(dòng)編碼器結(jié)構(gòu)能夠處理高階非線性類型的數(shù)據(jù)，但并不能捕捉圖序列中的時(shí)間特征.GRU 作為RNN 的變體，能夠?qū)W習(xí)動(dòng)態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)的歷史信息，其結(jié)構(gòu)簡(jiǎn)潔，又能在提取效率上優(yōu)于LSTM.因此本文使用此結(jié)構(gòu)作為該模型的隱藏層提取數(shù)據(jù)的時(shí)變特征.一個(gè)GRU 細(xì)胞由2 種門組成，分別是重置門和更新門.GRU 對(duì)于輸入值的處理程度主要依靠候選狀態(tài)Ht和隱藏候選狀態(tài)這2 個(gè)變量決定，隱藏候選狀態(tài)決定著候選狀態(tài)，而候選狀態(tài)影響著時(shí)刻tGRU 的輸出保留了多少歷史時(shí)刻的輸入.首先，數(shù)據(jù)輸入到GRU 中經(jīng)過重置門，通過輸出重置值Rt來重置當(dāng)前時(shí)刻的隱藏候選狀態(tài)，該過程定義為

其中，Xt表示時(shí)刻t的輸入；Rt表示時(shí)刻t的輸出；Ht-1表示時(shí)刻t-1 的候選狀態(tài)，當(dāng)t=0 時(shí)一般取默認(rèn)值或設(shè)置為0；Wr表示重置門的權(quán)值矩陣；[,]表示2 個(gè)向量相連操作；“· ”表示矩陣點(diǎn)乘，其運(yùn)算結(jié)果為標(biāo)量；σ表示重置門的激活函數(shù)Sigmoid.

在同一時(shí)刻，輸入數(shù)據(jù)流入更新門，更新門會(huì)更新當(dāng)前的狀態(tài)信息，以決定對(duì)歷史信息的保留程度，該過程定義為

式（8）中，Zt表示時(shí)刻t更新門的輸出，Wz表示更新門的權(quán)值矩陣.然后，更新門根據(jù)重置值Rt和更新值Zt對(duì)隱藏候選狀態(tài)和候選狀態(tài)Ht進(jìn)行操作，該過程定義為

最后GRU 根據(jù)候選狀態(tài)Ht輸出結(jié)果，該過程表示為

由式（7）～（11）可知，當(dāng)Zt=1時(shí)，GRU 會(huì)完全摒棄過去的候選狀態(tài)即歷史信息；當(dāng)Zt=0時(shí)，GRU 會(huì)完全復(fù)制當(dāng)前時(shí)刻的上一時(shí)刻的候選狀態(tài).重置門用于控制前一時(shí)刻有多少信息被寫入到當(dāng)前的隱藏候選狀態(tài)中，重置門的值越小，則的值越小，即前一時(shí)刻的信息被寫入當(dāng)前時(shí)刻的信息就越少.更新門用于控制前一時(shí)刻的狀態(tài)信息被帶入到當(dāng)前時(shí)刻狀態(tài)中的程度，更新門的值越大，則式（10）對(duì)的側(cè)重就越強(qiáng)，即前一時(shí)刻的狀態(tài)信息被帶入的越多.通過這種模式，GRU 細(xì)胞能夠?qū)v史信息有選擇地保留.雖然單個(gè)GRU 層已經(jīng)初步具備學(xué)習(xí)節(jié)點(diǎn)歷史信息的能力，然而效果并不是很理想，為了充分利用GRU 在時(shí)間處理方面的優(yōu)秀能力，本文將根據(jù)輸入圖序列的長(zhǎng)度N，將多個(gè)GRU 串聯(lián)起來，這種串聯(lián)堆疊的GRUs 模塊可以更好地處理具有時(shí)變特性的網(wǎng)絡(luò)，從而有效提高模型預(yù)測(cè)的準(zhǔn)確率.

3）隱藏層節(jié)點(diǎn)數(shù)量的設(shè)置.隱藏層節(jié)點(diǎn)的數(shù)量與模型提取數(shù)據(jù)特征的能力密不可分，不同節(jié)點(diǎn)數(shù)量的隱藏層具有不同的提取能力.如果節(jié)點(diǎn)數(shù)量設(shè)置太少，則提取能力不足，容易增加模型重構(gòu)數(shù)據(jù)時(shí)的誤差；反之，則會(huì)增加模型的復(fù)雜度，產(chǎn)生多余的資源開銷，并且容易出現(xiàn)過擬合問題.節(jié)點(diǎn)數(shù)量的設(shè)置主要由下列公式確定：

式（12）和式（13）中，Sn表示隱藏層節(jié)點(diǎn)的數(shù)量，m表示模型的輸入維度，n表示模型的輸出維度，考慮到數(shù)據(jù)集的大小和計(jì)算開銷，本文選擇式（13）來計(jì)算隱藏層節(jié)點(diǎn)的數(shù)量.

4）梯度算法的設(shè)置.梯度算法決定了模型的收斂速度.E-GRUs-D 模型使用的是Keras 庫(kù)中的Adadelta優(yōu)化器，由于Adadelta 能夠根據(jù)漸變更新的移動(dòng)窗口調(diào)整學(xué)習(xí)速率，所以相比于傳統(tǒng)的SGD 隨機(jī)梯度下降優(yōu)化器，Adadelta 具有更強(qiáng)魯棒性，且在設(shè)定的模型訓(xùn)練次數(shù)完畢之前，Adadelta 能夠保持對(duì)參數(shù)的學(xué)習(xí)，同時(shí)無需設(shè)置其初始學(xué)習(xí)率，從而避免了設(shè)置參數(shù)時(shí)的主觀性.

2.3 訓(xùn)練過程

在線性回歸問題中，L2范數(shù)常常被用來測(cè)量2 個(gè)樣本的相似度.然而如果僅僅使用該范數(shù)作為本文模型的損失函數(shù)，并不能很好地解決矩陣稀疏性所造成的過擬合現(xiàn)象.為了處理這一問題，應(yīng)當(dāng)把反向傳播的重點(diǎn)放在現(xiàn)存的鏈路上而非不存在的鏈路上.本文采用了文獻(xiàn)[20]所提供的損失函數(shù)Ltotal，該函數(shù)由基礎(chǔ)損失函數(shù)L和L2范數(shù)組成：

其中，L2范數(shù)通常用來避免模型進(jìn)入過擬合狀態(tài)；α為超參數(shù)，其取值范圍是0～1；基礎(chǔ)損失函數(shù)L表示預(yù)測(cè)值和標(biāo)簽值的差值并求和.

基于理論出發(fā)，鄰接矩陣At的元素值取值為0或者1.然而實(shí)際生成的數(shù)值均為小數(shù).為了獲得有效的鄰接矩陣元素值，首先對(duì)這些小數(shù)進(jìn)行歸一化處理，即在輸出層放置1 個(gè)Sigmoid 函數(shù).然后進(jìn)行一層過濾，若矩陣元素at;i,j＞ 0.5，則令at;i,j=1，即近似表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在鏈路，反之，令at;i,j＝0，即表示不存在鏈路.

對(duì)于模型的收斂，本文主要根據(jù)損失函數(shù)數(shù)值變動(dòng)的幅度進(jìn)行判斷.如果在模型訓(xùn)練100 輪之后，損失函數(shù)的數(shù)值不再顯著變化（保留小數(shù)點(diǎn)后3 位不再變化），則判定模型收斂.由于本文采用的數(shù)據(jù)集規(guī)模適中，且GRU 模塊參數(shù)較少，所以模型更容易達(dá)到收斂但同時(shí)易產(chǎn)生過擬合問題.

2.4 抗噪性分析

離群點(diǎn)作為數(shù)據(jù)集中的一種異常點(diǎn)，它的產(chǎn)生可能由于數(shù)據(jù)格式異常、數(shù)據(jù)內(nèi)容異常和事件偶然性造成的異常.對(duì)于前2 種異常的發(fā)生，本文在數(shù)據(jù)集預(yù)處理時(shí)已經(jīng)進(jìn)行規(guī)避，但對(duì)于第3 種異常情況，比如首次見面的人之間偶然產(chǎn)生的短暫且不具備重復(fù)性的對(duì)話，為了保證數(shù)據(jù)集的真實(shí)性，本文未將其從數(shù)據(jù)集中排除.因此造成了不同數(shù)據(jù)集之間分布的優(yōu)劣，導(dǎo)致各個(gè)數(shù)據(jù)集形成的網(wǎng)絡(luò)在周期性上具有一定的差異，而這種差異會(huì)對(duì)模型的訓(xùn)練造成影響，從而導(dǎo)致預(yù)測(cè)結(jié)果的不同.

2.5 空間復(fù)雜度分析

1）LSTM 主要維護(hù)4 套參數(shù)，分別是輸入門參數(shù)、輸出門參數(shù)、遺忘門參數(shù)和候選狀態(tài)參數(shù)，每套參數(shù)都由輸入?yún)?shù)input_size、輸出參數(shù)output_size、偏移項(xiàng)參數(shù)bias以及隱藏層參數(shù)hidden_size共4 部分組成，則LSTM 參數(shù)總量Num為

由于任意時(shí)刻LSTM 的輸出y均為ht，并未產(chǎn)生額外的映射，所以

假設(shè)LSTM 的輸入維度為p×g，隱藏層的節(jié)點(diǎn)數(shù)為p，則最終LSTM 的空間復(fù)雜度為

2）GRU 主要維護(hù)3 套參數(shù)，分別是重置門參數(shù)、更新門參數(shù)和候選狀態(tài)參數(shù)，每套參數(shù)都有其輸入和輸出以及偏移項(xiàng)，由于GRU 和LSTM 均為RNN 的變體，所以GRU 的參數(shù)計(jì)數(shù)過程與LSTM 相同，則最終GRU 的空間復(fù)雜度為

LSTM 和GRU 作為RNN 的變體，均能夠捕捉數(shù)據(jù)的時(shí)間關(guān)聯(lián)性，并且能夠有效抑制梯度消失或爆炸，但是LSTM 的參數(shù)量約為RNN 的4 倍，而GRU的參數(shù)量只有RNN 的3 倍，所以在模型復(fù)雜度方面，GRU 更加簡(jiǎn)潔，同時(shí)這也是GRU 模型在訓(xùn)練時(shí)更不容易出現(xiàn)過擬合問題的原因.因此，在相同的數(shù)據(jù)集下GRU 的訓(xùn)練效率相比于LSTM 大大提高.

3 實(shí) 驗(yàn)

本文所提出的模型將基于KONECT 的3 個(gè)移動(dòng)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行評(píng)估，并與其他3 種基準(zhǔn)方法進(jìn)行比較.

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

本文使用了3 個(gè)現(xiàn)實(shí)生活中的移動(dòng)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集，這些數(shù)據(jù)集均涉及人與人之間的交互記錄.在這些網(wǎng)絡(luò)圖中，節(jié)點(diǎn)代表參與者，而邊則表示與他人之間的聯(lián)系.數(shù)據(jù)集的部分具體信息如表1 所示.

Table 1 Basic Information for the Three Datasets表1 3 種數(shù)據(jù)集的基本信息

1）HyperText[21].該數(shù)據(jù) 集記錄 了2009 年ACM超文本會(huì)議中出席人之間面對(duì)面會(huì)談的情況，該會(huì)議于2009 年6 月29 日在意大利都靈舉辦，為期3 天.在該網(wǎng)絡(luò)中，節(jié)點(diǎn)代表會(huì)議出席人，邊代表出席人之間至少存在20s 以上的對(duì)話，并且每條邊都標(biāo)注了接觸發(fā)生的時(shí)間.

2）Infectious[21].該數(shù)據(jù)集記錄了2009 年在都柏林科學(xué)畫廊舉辦的《傳染：遠(yuǎn)離》展覽會(huì)期間人們之間的交流情況.在該網(wǎng)絡(luò)中，節(jié)點(diǎn)代表了畫展的參觀者，邊表示參觀者之間產(chǎn)生了至少20 s 以上的接觸，并且記錄了發(fā)生時(shí)間.

3）Haggle[21].該數(shù)據(jù)集記錄了人們?cè)谝欢▍^(qū)域攜帶無線智能設(shè)備生活，并與他人產(chǎn)生往來的情況.在該網(wǎng)絡(luò)中，節(jié)點(diǎn)和邊代表的含義與網(wǎng)絡(luò)HyperText 和網(wǎng)絡(luò)Infectious 相同，并且同樣記錄了接觸的發(fā)生時(shí)間.不同的是，在Haggle 網(wǎng)絡(luò)中，同一時(shí)刻可能產(chǎn)生多條邊.

在輸入數(shù)據(jù)之前，要先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理.首先，對(duì)數(shù)據(jù)集按照時(shí)間戳大小進(jìn)行排序，保證模型所獲取的歷史信息的連續(xù)性和正確性.然后，排除數(shù)據(jù)異常值，如空值或殘缺值.再次，按照固定時(shí)間間隔為每個(gè)數(shù)據(jù)集生成快照，即將整個(gè)數(shù)據(jù)集劃分為一系列網(wǎng)絡(luò)圖，由于數(shù)據(jù)集中記錄的相鄰時(shí)刻鏈路產(chǎn)生的時(shí)間差均為20 s，所以固定時(shí)間間隔設(shè)置為20 s.考慮到存在同一時(shí)刻可能產(chǎn)生多條鏈路的情況，將同一時(shí)刻產(chǎn)生的鏈路歸屬到同一個(gè)圖中.本文將抽象的圖轉(zhuǎn)化為具體的鄰接矩陣，每個(gè)鄰接矩陣的維度設(shè)置為各個(gè)數(shù)據(jù)集對(duì)應(yīng)的參加人數(shù)，為了保證數(shù)據(jù)集的充足和數(shù)據(jù)之間的時(shí)間關(guān)聯(lián)性，每個(gè)樣本以滑動(dòng)窗口的形式進(jìn)行創(chuàng)建，滑動(dòng)窗口的長(zhǎng)度等同于輸入圖序列長(zhǎng)度N，即每個(gè)樣本的格式均為（Gt-N,Gt-(N-1),…,Gt）.實(shí)驗(yàn)中N=10，矩陣序列（Gt-10,Gt-9,…,Gt）作為一個(gè)樣本，在該樣本中，前10 個(gè)矩陣作為模型的輸入，最后1 個(gè)矩陣作為此次輸入的標(biāo)簽.每個(gè)矩陣中，存儲(chǔ)著當(dāng)前時(shí)間的節(jié)點(diǎn)信息，若人們之間存在交談，則相應(yīng)的矩陣元素?cái)?shù)值設(shè)置為1，否則設(shè)置為0.在極端條件下，即某一時(shí)刻沒有任何人產(chǎn)生交談?dòng)涗洠瑒t生成零矩陣.本文按照鏈路產(chǎn)生的時(shí)間順序，將前75%的數(shù)據(jù)集設(shè)置為訓(xùn)練集，將后25%的數(shù)據(jù)集設(shè)置為測(cè)試集，同時(shí)遵循滑動(dòng)窗口規(guī)則，盡可能多地創(chuàng)建樣本，最終從數(shù)據(jù)集中提取出320 張網(wǎng)絡(luò)快照?qǐng)D，其中前240 張快照?qǐng)D作為訓(xùn)練集使用，后80 張快照?qǐng)D作為測(cè)試集使用.

3.2 基準(zhǔn)方法

為了驗(yàn)證E-GRUs-D 模型的性能，本文使用了3種基準(zhǔn)方法與該模型進(jìn)行對(duì)比，包括靜態(tài)網(wǎng)絡(luò)的鏈路預(yù)測(cè)方法node2vec[22]、深度學(xué)習(xí)模型DDNE[23]和深度學(xué)習(xí)模型E-LSTM-D[19].

1）node2vec[22].node2vec 是一種綜合考量深度優(yōu)先搜索鄰域和廣度優(yōu)先搜索鄰域的圖嵌入（graph embedding）方法.該方法常用于靜態(tài)網(wǎng)絡(luò)，它將網(wǎng)絡(luò)中節(jié)點(diǎn)的鏈路情況進(jìn)行降維.在低維空間中，如果1對(duì)節(jié)點(diǎn)對(duì)應(yīng)的向量距離越短，則表明2 個(gè)節(jié)點(diǎn)的相似性就越高，即這對(duì)節(jié)點(diǎn)產(chǎn)生鏈路的可能性越高.

2）DDNE[23].該模型借鑒了自動(dòng)編碼器結(jié)構(gòu)，模型的核心部分是2 個(gè)GRU 層，其中一層作為編碼器使用，另一層作為解碼器使用，編碼器模塊負(fù)責(zé)學(xué)習(xí)數(shù)據(jù)的時(shí)間變化特性，解碼器模塊則負(fù)責(zé)將提取的特征嵌入到未來網(wǎng)絡(luò)結(jié)構(gòu)中.

3）E-LSTM-D[19].該模型使用了自動(dòng)編碼器和長(zhǎng)短期記憶網(wǎng)絡(luò)結(jié)合的方式構(gòu)造模型，編碼器負(fù)責(zé)簡(jiǎn)化數(shù)據(jù)，解碼器負(fù)責(zé)還原數(shù)據(jù)維度.隱藏層為多個(gè)LSTM 串聯(lián)組成，用來提取數(shù)據(jù)特征.

基于數(shù)據(jù)集的規(guī)模和對(duì)比實(shí)驗(yàn)，首先將隱藏層層數(shù)設(shè)置為2，然后根據(jù)式（13）設(shè)置隱藏層節(jié)點(diǎn)數(shù)量.輸入層編碼器節(jié)點(diǎn)數(shù)量取默認(rèn)值128，由于輸出層的輸出形狀要求與最終輸出的鄰接矩陣形狀相同，所以解碼器層節(jié)點(diǎn)數(shù)量設(shè)置為各數(shù)據(jù)集中的總參與人數(shù).參數(shù)的具體設(shè)置如表2 所示.

Table 2 Number of Hidden Layer Nodes Under Each Dataset表2 各數(shù)據(jù)集下隱藏層節(jié)點(diǎn)的數(shù)量

3.3 評(píng)價(jià)指標(biāo)

1）混淆矩陣（confusion matrix）.該指標(biāo)是一個(gè)標(biāo)準(zhǔn)混淆矩陣，如圖5 所示.

在混淆矩陣中，預(yù)測(cè)類別為1 的為正樣本（Positive），預(yù)測(cè)類別為0 的為負(fù)樣本（Negative）.真陽(yáng)率TPR表示所有真實(shí)類別為1 的樣本中預(yù)測(cè)類別為1 的占比，偽陽(yáng)率FPR表示所有真實(shí)類別為0 的樣本中預(yù)測(cè)類別為1 的占比.TPR和FPR分別定義為：

其中TP表示模型正確預(yù)測(cè)為正樣本的次數(shù)，F(xiàn)P表示模型錯(cuò)誤預(yù)測(cè)為正樣本的次數(shù)，F(xiàn)N表示模型錯(cuò)誤預(yù)測(cè)為負(fù)樣本的次數(shù)，TN表示正確預(yù)測(cè)為負(fù)樣本的次數(shù).根據(jù)TPR和FPR則能繪制出接收者操作特征曲 線（receiver operating characteristic curve,ROC）.其中TPR作為縱坐標(biāo)軸，F(xiàn)PR作為橫坐軸.

2）AUC指標(biāo).AUC通常用于衡量靜態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法的準(zhǔn)確性，其表示ROC 下的面積，表示模型正確預(yù)測(cè)為正樣本概率大于錯(cuò)誤預(yù)測(cè)為正樣本概率的可能性.假設(shè)在數(shù)據(jù)中有M個(gè)正樣本和 ?個(gè)負(fù)樣本，則共有M×? 對(duì)樣本.若有M1次出現(xiàn)正樣本和負(fù)樣本預(yù)測(cè)概率相同，有M2次出現(xiàn)正樣本預(yù)測(cè)概率值大于負(fù)樣本預(yù)測(cè)概率值，則AUC定義為

AUC數(shù)值越大則表明模型的預(yù)測(cè)性能越好.特別地，當(dāng)AUC=0.5 時(shí)表明對(duì)于不論真實(shí)類別是1 還是0 的樣本，模型預(yù)測(cè)為1 的概率是相等的.

3）錯(cuò)誤率ER.ER一般是指模型錯(cuò)誤預(yù)測(cè)的樣本數(shù)量占總樣本數(shù)量的比例，是一種通用的性能指標(biāo)，定義為

其中，at;i,j表示時(shí)刻t標(biāo)簽矩陣中第i行第j列的元素值，表示時(shí)刻t輸出矩陣中第i行第j列的元素值，Q代表總鏈路數(shù)，n代表輸出維度.

Fig.5 Confusion matrix圖5 混淆矩陣

3.4 實(shí)驗(yàn)結(jié)果

本文設(shè)置N＝10 作為E-GRUs-D，DDNE，E-LSTM-D這3 種模型的輸入序列長(zhǎng)度，由于node2vec 方法無法處理時(shí)間序列，故直接使用圖Gt-1去預(yù)測(cè)圖Gt，以此完成性能評(píng)估.

本文在評(píng)價(jià)指標(biāo)AUC和ER的基礎(chǔ)上對(duì)E-GRUs-D 模型和其他3 種基準(zhǔn)方法進(jìn)行了比較，并選取其中性能最好的2 種方法對(duì)比它們的模型訓(xùn)練時(shí)間，預(yù)測(cè)性能對(duì)比實(shí)驗(yàn)結(jié)果分別如表3 和表4 所示，模型訓(xùn)練時(shí)間對(duì)比實(shí)驗(yàn)結(jié)果如圖6 所示.

Table 3 AUC Evaluation Metric表3 AUC 評(píng)價(jià)指標(biāo)

Table 4 ER Evaluation Metric表4 ER 評(píng)價(jià)指標(biāo)

Fig.6 Comparison of training time圖6 訓(xùn)練時(shí)間對(duì)比

在表3 和表4 中，node2vec 方法的鏈路預(yù)測(cè)準(zhǔn)確率遠(yuǎn)遠(yuǎn)小于其他方法，這表明相比于用于動(dòng)態(tài)網(wǎng)絡(luò)鏈路預(yù)測(cè)的方法，node2vec 并不能很好地學(xué)習(xí)移動(dòng)社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的鏈路變化情況.總體而言，盡管ELSTM-D 模型的預(yù)測(cè)結(jié)果要略優(yōu)于E-GRUs-D 模型，但圖6 表明，在3 種不同數(shù)據(jù)集下，E-GRUs-D 模型的訓(xùn)練時(shí)間要遠(yuǎn)短于E-LSTM-D 模型，體現(xiàn)了在相同數(shù)據(jù)規(guī)模下，E-GRUs-D 模型在縮短訓(xùn)練時(shí)間上的優(yōu)勢(shì).

從實(shí)驗(yàn)結(jié)果來看，E-GRUs-D 模型在不同的網(wǎng)絡(luò)規(guī)模、網(wǎng)絡(luò)密度中都能夠得到較為理想的預(yù)測(cè)效果，雖然其預(yù)測(cè)性能略低于E-LSTM-D 模型，但是訓(xùn)練時(shí)間和計(jì)算效率得到顯著提高.此外，當(dāng)在數(shù)據(jù)集規(guī)模較小的情況下，E-GRUs-D 的預(yù)測(cè)準(zhǔn)確率超過了ELSTM-D 模型，該現(xiàn)象符合LSTM 和GRU 的特性：雖然GRU 和LSTM 內(nèi)部均和“門控”這一概念密不可分，但是GRU 內(nèi)部主要由2 個(gè)門進(jìn)行運(yùn)作，而LSTM內(nèi)部則由3 個(gè)門進(jìn)行運(yùn)作，得益于GRU 內(nèi)部構(gòu)造的簡(jiǎn)潔性，在數(shù)據(jù)集規(guī)模較小的情況下，GRU 的訓(xùn)練效果會(huì)優(yōu)于LSTM.

Fig.7 AUC values on different datasets圖7 不同數(shù)據(jù)集下AUC 值

Fig.8 ER values on different datasets圖8 不同數(shù)據(jù)集下ER 值

不同數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果如圖7 和圖8 所示.其中，實(shí)線是相應(yīng)數(shù)據(jù)集下模型在測(cè)試集中不同測(cè)試輪數(shù)的評(píng)價(jià)指標(biāo)結(jié)果，虛線表示其結(jié)果的平均值.從這2 個(gè)圖可知，本文所提出的E-GRUs-D 模型具有穩(wěn)定良好的預(yù)測(cè)效果，其中在Haggle 數(shù)據(jù)集下，預(yù)測(cè)的穩(wěn)定性相對(duì)于Infectious 數(shù)據(jù)集和HyperText 數(shù)據(jù)集較差，這是由于Infectious 和HyperText 這2 種網(wǎng)絡(luò)的演變更具有周期性，更易于模型的學(xué)習(xí)，從而可以得到穩(wěn)定性更強(qiáng)的預(yù)測(cè)結(jié)果.

模型預(yù)測(cè)結(jié)果波動(dòng)較大是因?yàn)閿?shù)據(jù)集中存在一些偏差點(diǎn)，比如首次見面的人之間偶然性的對(duì)話，由于在數(shù)據(jù)集中該節(jié)點(diǎn)對(duì)之間產(chǎn)生的數(shù)據(jù)較少，模型對(duì)于該信息無法進(jìn)行充分的學(xué)習(xí)，故模型測(cè)試時(shí)在某段數(shù)據(jù)上易表現(xiàn)出較大的波動(dòng).

如果忽略掉個(gè)別離群點(diǎn)，如Infectious 數(shù)據(jù)集對(duì)應(yīng)圖中的離群點(diǎn)，那么基于該數(shù)據(jù)集的預(yù)測(cè)結(jié)果在預(yù)測(cè)穩(wěn)定性、指標(biāo)平均值都較優(yōu)于其他2 個(gè)數(shù)據(jù)集，這是因?yàn)樵跀?shù)據(jù)規(guī)模上，Infectious 數(shù)據(jù)集要大于其他2 種數(shù)據(jù)集，它能夠提供給模型更加充足的信息，使模型提取到足夠的歷史信息，更好地訓(xùn)練得到網(wǎng)絡(luò)的時(shí)間變化特性.

3.5 參數(shù)設(shè)置實(shí)驗(yàn)

E-GRUs-D 模型的性能主要受到模型結(jié)構(gòu)和輸入圖序列長(zhǎng)度N的影響，下面將展開相關(guān)實(shí)驗(yàn).

1）模型結(jié)構(gòu)的影響.模型結(jié)構(gòu)主要由隱藏層節(jié)點(diǎn)數(shù)量和隱藏層層數(shù)決定，借助于式（13），隱藏層節(jié)點(diǎn)數(shù)量可以確定，所以本文在相同節(jié)點(diǎn)數(shù)量的條件下觀察隱藏層層數(shù)對(duì)預(yù)測(cè)結(jié)果的影響.

圖9 和圖10 為隱藏層層數(shù)對(duì)模型性能影響的實(shí)驗(yàn)結(jié)果.可知，在任何一種數(shù)據(jù)集下，當(dāng)隱藏層層數(shù)設(shè)置為1 時(shí)，模型的學(xué)習(xí)能力不足，所以必須通過增加層數(shù)來提升模型的學(xué)習(xí)能力；當(dāng)隱藏層層數(shù)設(shè)置為2 時(shí)預(yù)測(cè)效果最佳；當(dāng)層數(shù)設(shè)置為3 時(shí)，由于提取了過多無用的信息，并且計(jì)算量隨著層數(shù)增多而急劇增加，預(yù)測(cè)效果反而下降.

Fig.9 Influence of the number of hidden layers on AUC values圖9 隱藏層數(shù)對(duì)AUC 值的影響

Fig.10 Influence of the number of hidden layers on ER values圖10 隱藏層數(shù)對(duì)ER 值的影響

2）輸入圖序列長(zhǎng)度的影響.一般來說，輸入的圖序列越長(zhǎng)，其中包含的歷史信息就越多，模型能更好地學(xué)習(xí)網(wǎng)絡(luò)的演變，預(yù)測(cè)準(zhǔn)確率也越高.

然而，實(shí)驗(yàn)結(jié)果表明如果輸入的圖序列過長(zhǎng)，則其中可能會(huì)包含過多不相關(guān)的特征，導(dǎo)致資源浪費(fèi).因此，合適的輸入圖序列長(zhǎng)度對(duì)于模型的預(yù)測(cè)性能也至關(guān)重要.本文在各數(shù)據(jù)集下測(cè)試了N從5 到15變化時(shí)對(duì)模型性能的影響，實(shí)驗(yàn)結(jié)果如圖11 和圖12所示.對(duì)于規(guī)模較小的數(shù)據(jù)集HyperText 和數(shù)據(jù)集Haggle 而言，在N取值為11 之前，其預(yù)測(cè)性能隨著長(zhǎng)度的遞增而不斷提升，而N取值超過11 之后，性能開始降低，這是因?yàn)楫?dāng)輸入序列過長(zhǎng)，模型學(xué)習(xí)到過多冗余的歷史信息.由于Infectious 數(shù)據(jù)集規(guī)模較大，在整個(gè)過程中模型性能都隨著N的增加而增加，但在N取值為11 之后，模型的性能提升幅度減緩，需要注意的是，這種性能緩慢提升需要耗費(fèi)巨大的模型訓(xùn)練計(jì)算量.

Fig.12 Influence of the input sequence length on ER values圖12 輸入序列長(zhǎng)度對(duì)ER 值的影響

4 結(jié)論

本文提出了一種適用于移動(dòng)社會(huì)網(wǎng)絡(luò)鏈路預(yù)測(cè)的E-GRUs-D 模型，該模型的Encoder-Decoder 模塊能夠?qū)W習(xí)高階非線性的網(wǎng)絡(luò)結(jié)構(gòu)，從而降低了隱藏層的計(jì)算量，同時(shí)將提取的特征重構(gòu)至先前的維度并映射到目標(biāo)時(shí)刻網(wǎng)絡(luò)的鄰接矩陣中.GRUs 模塊的復(fù)數(shù)個(gè)GRU 串聯(lián)結(jié)構(gòu)，首先能使模型提取數(shù)據(jù)的時(shí)變特征；其次，和只有1 層GRU 相比，學(xué)習(xí)能力更強(qiáng)，有助于提升模型預(yù)測(cè)性能；而且由于自身結(jié)構(gòu)的簡(jiǎn)潔性，該方法在縮短訓(xùn)練時(shí)間方面要明顯優(yōu)于現(xiàn)有方法；還能通過調(diào)整節(jié)點(diǎn)數(shù)量，適用不同規(guī)模的網(wǎng)絡(luò)，具有良好的可擴(kuò)展性.大量的實(shí)驗(yàn)表明，對(duì)于移動(dòng)社會(huì)網(wǎng)絡(luò)的鏈路預(yù)測(cè)問題，該模型具有較為高效且準(zhǔn)確的預(yù)測(cè)性能.

E-GRUs-D 模型和E-LSTM-D 模型在相同數(shù)據(jù)集下，模型性能差距較小，但是由于GRU 擁有相對(duì)于LSTM 較低的模型復(fù)雜度，所以在模型訓(xùn)練效率方面更加優(yōu)秀.然而，不論是LSTM 還是GRU，只是相對(duì)于RNN 而言，更加能夠抑制梯度消失或爆炸，且作為RNN 的變體，有著和RNN 結(jié)構(gòu)同樣的弊端，即無法進(jìn)行并行計(jì)算，所以在數(shù)據(jù)量不斷劇增以及模型體量不斷增大的未來，我們的研究將更加注重模型本身的優(yōu)化，盡可能進(jìn)一步抑制梯度消失和提高模型運(yùn)算效率.

作者貢獻(xiàn)聲明：劉林峰提出指導(dǎo)性意見并修改論文；于子興提出算法思路和實(shí)驗(yàn)方案，完成實(shí)驗(yàn)并撰寫論文；祝賀負(fù)責(zé)收集實(shí)驗(yàn)數(shù)據(jù)和完善實(shí)驗(yàn)方案.