基于圖嵌入法的時序網(wǎng)絡(luò)鏈路預(yù)測研究

吳晨程，周銀座

(杭州師范大學(xué)阿里巴巴商學(xué)院，浙江 杭州 311121)

0 引言

當下，復(fù)雜網(wǎng)絡(luò)這一新興的交叉學(xué)科被越來越多的人作為分析手段來對現(xiàn)實世界進行數(shù)據(jù)挖掘[1-2].在復(fù)雜網(wǎng)絡(luò)理論中，鏈路預(yù)測[3]的方法對于還原網(wǎng)絡(luò)中缺失的信息以及挖掘網(wǎng)絡(luò)中潛在的結(jié)構(gòu)顯示出巨大的威力.

鏈路預(yù)測的傳統(tǒng)方法是基于機器學(xué)習[4]，這種解決思路是將鏈路預(yù)測看作機器學(xué)習中的分類問題，根據(jù)每一對節(jié)點之間的特征，將節(jié)點對分為正例和反例，即有連邊和無連邊.這種分類問題過度依賴網(wǎng)絡(luò)中的節(jié)點屬性，而節(jié)點的屬性值既難以獲取且無法保證其可靠性.由于以上弊端，基于節(jié)點相似性的鏈路預(yù)測算法得以發(fā)展，即兩個節(jié)點的相似性越大，它們之間存在邊的可能性就越大.基于節(jié)點相似性的鏈路預(yù)測算法主要有3類：基于局部信息的相似性指標[2,5-7]、基于路徑的相似性指標[7-9]、基于隨機游走的相似性指標[10-13].基于局部信息的相似性指標是指通過節(jié)點的局部信息(節(jié)點的度、共同鄰居數(shù)量等)計算得到的相似性指標，其計算復(fù)雜度較低，但代價是預(yù)測效果的相對降低.基于路徑的相似性指標是指利用要預(yù)測的兩個節(jié)點之間的路徑信息(節(jié)點之間的路徑數(shù)量、路徑中間節(jié)點的信息等)計算得到的相似度指標，該類指標在計算多階路徑信息的貢獻時，計算復(fù)雜度較高.基于隨機游走的相似性指標是基于隨機游走過程定義的，即假設(shè)一個粒子從某個初始節(jié)點出發(fā)，以一定的概率隨機游走到它的鄰居節(jié)點，然后繼續(xù)擴散，直到該粒子處在所有節(jié)點上的概率達到穩(wěn)定.這類指標很好地考慮到了網(wǎng)絡(luò)的全局信息，在推薦系統(tǒng)和社團發(fā)現(xiàn)中也有很好的應(yīng)用.

研究發(fā)現(xiàn)在鏈路預(yù)測算法中，粒子隨機游走的轉(zhuǎn)移概率僅僅取決于當前節(jié)點的度信息，而不關(guān)心其鄰居節(jié)點的網(wǎng)絡(luò)拓撲結(jié)構(gòu)特征，從而粒子下一時刻從當前節(jié)點轉(zhuǎn)移到任意鄰居節(jié)點的概率是相同的，具有較強的隨機性.然而真實的網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜多樣，粒子在隨機游走的過程中不一定是按照等概率的方式轉(zhuǎn)移，而應(yīng)該是一種有偏向的轉(zhuǎn)移，即粒子會傾向于從當前節(jié)點轉(zhuǎn)移到與當前節(jié)點更相似的鄰居節(jié)點上.基于節(jié)點拓撲結(jié)構(gòu)相似性的有偏向隨機游走，理論上應(yīng)該比具有強隨機性的隨機游走有更高的效率，對算法有更好的提升.

在鏈路預(yù)測的具體計算過程中，通常將網(wǎng)絡(luò)表示成鄰接矩陣進行存儲.這對于大型的網(wǎng)絡(luò)是一個不小的負擔.為了使這個方法能夠更有效地應(yīng)用到大型網(wǎng)絡(luò)中，研究使用了圖嵌入方法[14](Graph Embedding Method，GEM).該方法是將圖數(shù)據(jù)或者高維稠密的矩陣映射為低維稠密向量的方法，同時使原網(wǎng)絡(luò)中屬性接近或拓撲結(jié)構(gòu)相似的節(jié)點在向量空間上的位置也接近.這樣，通過降維的方法大大降低了計算的復(fù)雜度.例如，Mikolov等[15]在文獻中提出的Word2Vec神經(jīng)網(wǎng)絡(luò)語言模型在詞表示上取得了良好效果，Perozzi[16]在此基礎(chǔ)上提出DeepWalk算法，引入了深度學(xué)習，利用隨機游走采樣得到的節(jié)點序列類比于“句子”，將節(jié)點類比于“詞”，使用Word2Vec模型獲得節(jié)點表示向量，在網(wǎng)絡(luò)分析任務(wù)中獲得了較大的性能提升.隨著圖嵌入的廣泛應(yīng)用，后來相繼出現(xiàn)了基于簡單神經(jīng)網(wǎng)絡(luò)的LINE[17]，基于DeepWalk改進的Node2Vec[18]，基于空間相似性的Struc2Vec[19]等算法.

鏈路預(yù)測研究的真實網(wǎng)絡(luò)大多都會隨時間而變化，然而為了方便研究有時會將這種動態(tài)變化忽略，讓算法基于網(wǎng)絡(luò)的靜態(tài)特征去預(yù)測鏈路.然而，對于一些網(wǎng)絡(luò)而言，他們具有復(fù)雜的動態(tài)結(jié)構(gòu)和非線性的拓撲特征，這意味著有些鏈路會在下一時刻突然消失或出現(xiàn)[20].這種特性被稱為“時序性”.對于這類網(wǎng)絡(luò)，不僅要觀察網(wǎng)絡(luò)的拓撲特征，還要將時序性考慮進去.在較早的研究中，已經(jīng)有研究者對基于時序網(wǎng)絡(luò)的鏈路預(yù)測做了研究和總結(jié).Sarkar P[21]等人基于節(jié)點特征及節(jié)點周圍領(lǐng)域特征提出了一種非參數(shù)化的時序網(wǎng)絡(luò)鏈路預(yù)測方法.Butun E[22]等人提出基于鄰居和圖模式的拓撲指標方法，并應(yīng)用于有向、加權(quán)、時序的復(fù)雜網(wǎng)絡(luò)場景，有較好的性能表現(xiàn).Hyoungshick Kim[23]等人使用了度中心性來預(yù)測未來網(wǎng)絡(luò)中重要的節(jié)點.Catherine A. Bliss[24]等人整合網(wǎng)絡(luò)節(jié)點屬性信息和網(wǎng)絡(luò)拓撲結(jié)構(gòu)特征并提出了一種進化算法來提高鏈路預(yù)測的精確度.

基于上述問題和研究現(xiàn)狀，研究認為在現(xiàn)實網(wǎng)絡(luò)尤其是時序網(wǎng)絡(luò)中，使用隨機游走方式進行鏈路預(yù)測時，粒子轉(zhuǎn)移會受到網(wǎng)絡(luò)結(jié)構(gòu)和時間推移的影響從而進行有偏向的轉(zhuǎn)移，這種轉(zhuǎn)移方式具有較高的準確性，可以更好地考慮全局信息.本文基于以上分析，提出了一種基于圖嵌入法的時序網(wǎng)絡(luò)重啟隨機游走算法，通過實驗驗證此算法在時序網(wǎng)絡(luò)環(huán)境下有優(yōu)秀的預(yù)測精度，較傳統(tǒng)基準方法有較大的性能提升.

1 相關(guān)工作

本部分將介紹鏈路預(yù)測中經(jīng)典的基準指標、常見的圖嵌入算法以及鏈路預(yù)測的評價指標.

1.1 鏈路預(yù)測經(jīng)典指標

1)共同鄰居(Common Neighbors，CN)[5]

對于網(wǎng)絡(luò)中的節(jié)點x，定義其鄰居集合為Γ(x)，則兩個節(jié)點x和y的相似性定義為它們共同的鄰居數(shù)，即：

Sxy=|Γ(x)∩Γ(y)|.

其中wxz表示節(jié)點x和y的邊權(quán)，顯然若所有邊權(quán)都等于1，該指標就等同于無權(quán)的CN指標.

2)Adamic-Adar指標(AA)[6]

其中sz為節(jié)點的強度，強度定義為節(jié)點與其鄰居節(jié)點之間的連邊權(quán)重和.

3)資源分配(Resource Allocation，RA)[7]

RA指標認為沒有直接相連的兩個節(jié)點x和y，可以通過共同鄰居作為傳遞媒介從而傳遞資源.假設(shè)每個媒介都有一個單位的資源并且將平均分配傳給它的鄰居，則節(jié)點y接收的資源數(shù)即節(jié)點x和y的相似度，即：

4)偏好連接指標(Preferential Attachment，PA)[2]

在無標度網(wǎng)絡(luò)結(jié)構(gòu)中，一條新邊連接到節(jié)點x的概率正比于該節(jié)點的度，定義兩個節(jié)點間的偏好連接相似性為：

Sxy=kxky.

對于加權(quán)環(huán)境，定義含權(quán)的PA指標為：Sxy=∑i∈Γ(x)wix×∑j∈Γ(y)wjy=sxsy.

5)有重啟的隨機游走指標(Random Walk with Restart, RWR)[13]

πx(t+1)=α·PTπx(t)+(1-α)ex，

其中ex表示初始狀態(tài)，上式可以計算出穩(wěn)態(tài)解，公式如下：

πx=(1-α)(I-αPT)-1ex，

其中元素πx表示從節(jié)點x出發(fā)的粒子走到節(jié)點y的最終概率，并由此定義相似性：

1.2 圖嵌入方法

1)Word2vec

Word2vec是Google公司在2013年開放的一款用于訓(xùn)練詞向量的軟件工具，主要包括CBOW模型和Skip-Gram模型.前者通過訓(xùn)練上下文節(jié)點來預(yù)測中間詞，后者則相反，輸入中間詞從而得到上下文節(jié)點.模型是一個包含輸入層、投影層、輸出層的3層神經(jīng)網(wǎng)絡(luò)，如圖1所示.

圖1 CBOW模型(左)和Skip-Gram模型(右)Fig.1 CBOW model (the left) and Skip-Gram model (the left)

圖嵌入方法正是通過采集網(wǎng)絡(luò)的節(jié)點構(gòu)成節(jié)點序列，將節(jié)點序列類比成“句子”，使用Word2vec模型生成得到節(jié)點向量(相當于“詞”).通過這種方式得到的節(jié)點向量.因為考慮了節(jié)點的上下文信息，因此對于網(wǎng)絡(luò)分析任務(wù)有較大的性能提升.

2)Node2vec

Node2vec是一種經(jīng)典的圖嵌入方法，它通過隨機游走方式采集節(jié)點序列，并結(jié)合了深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)，可以更好地獲取網(wǎng)絡(luò)的全局信息.Node2vec的隨機游走策略為，給定當前頂點v，訪問下一個頂點x的概率為：

其中πvx是頂點v和頂點x之間未歸一化的轉(zhuǎn)移概率，Z為歸一化常數(shù).

Node2vec引入兩個超參數(shù)p，q來控制隨機游走策略.假設(shè)當前隨機游走經(jīng)過邊(t,v)到達節(jié)點v時，設(shè)πvx=αpq(t,x)·wuv,其中wuv是頂點v和x之間的權(quán)值：

其中dtx為頂點t和頂點x之間的最短距離.參數(shù)p是控制重復(fù)訪問剛剛訪問過的頂點概率，dtx=0表示頂點t就是剛剛訪問過的頂點x，若p值較高，則重復(fù)訪問的概率將會降低.參數(shù)q是控制游走向內(nèi)還是向外的概率，若q>1，隨機游走偏向于訪問跟節(jié)點t相近的節(jié)點(BFS)，若q<1，隨機游走偏向于訪問遠離節(jié)點t的節(jié)點(DFS).

1.3 評價指標

AUC(area under the receiver operating characteristic curve)[25]是衡量鏈路預(yù)測算法精確度最常用的指標.它是指在測試集中隨機選擇一條邊的分數(shù)值比隨機選擇的一條不存在的邊分數(shù)值高的概率.實驗時，每次隨機從測試集中選取一條邊，再從不存在的邊中隨機選擇一條，如果測試集中的邊分數(shù)值大于不存在的邊的分數(shù)值，那么就加1分，如果兩個分數(shù)值相等就加0.5分.這樣獨立比較n次，如果有n′次測試集中的邊分數(shù)值大于不存在的邊分數(shù)，有n″次兩分數(shù)值相等，那么AUC指標的定義為：

一般的，AUC越接近1，算法的精確度越高.

在時序網(wǎng)絡(luò)的鏈路預(yù)測計算中，移動窗口切片方法是選取訓(xùn)練集和測試集的一種方式.首先將時序網(wǎng)絡(luò)按照等量的時間間隔劃分為若干個時間切片.假定設(shè)置時間窗口大小為T，選取前T個時間切片作為訓(xùn)練集，第T+1時刻的時間切片作為測試集，計算得到一次AUC.接著將時間窗口移動一個單位，再計算得到AUC.當時間窗口到達最后一個切片為止，我們就得到了基于此時間窗口大小的每一次獨立的實驗的AUC，取平均值作為對應(yīng)時間窗口大小T的AUC.

2 基于圖嵌入法的時序網(wǎng)絡(luò)鏈路預(yù)測算法

本部分將介紹一種基于圖嵌入法的時序鏈路預(yù)測算法.該方法針對RWR指標中隨機游走的強隨機性問題做了改進，并引入了基于節(jié)點間拓撲結(jié)構(gòu)相似性的有偏向的轉(zhuǎn)移概率.下文將詳細敘述如何使用圖嵌入法計算得到這種轉(zhuǎn)移概率并如何改進原有的鏈路預(yù)測算法.

2.1 基于圖嵌入法的重啟隨機游走

圖嵌入法的核心思想是訓(xùn)練節(jié)點序列，生成低維的節(jié)點向量.節(jié)點序列的采集受不同圖嵌入算法的定義而有所不同，可以根據(jù)具體的網(wǎng)絡(luò)信息選擇合適的圖嵌入算法.而節(jié)點向量的訓(xùn)練過程綜合考慮了節(jié)點的“上下文信息”，即通過深度學(xué)習不斷訓(xùn)練節(jié)點的網(wǎng)絡(luò)結(jié)構(gòu)特征從而獲得最優(yōu)的向量表示，因此節(jié)點在向量空間上的相似性可以很好地表征節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)上的相似性.

本文以Node2vce為例，采集節(jié)點序列生成得到節(jié)點向量.定義任意節(jié)點x的向量表示為Φ(x)=[x1,x2,…,xd]，任意節(jié)點y的向量表示為Φ(y)=[y1,y2,…,yd]，考慮節(jié)點間的邊權(quán)后使用通用的余弦相似度指標可以量化兩個節(jié)點向量在向量空間上的相似程度，同時也可以表示節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)上的拓撲結(jié)構(gòu)相似性，給出定義1.

定義1網(wǎng)絡(luò)中任一節(jié)點x和節(jié)點y的潛在拓撲結(jié)構(gòu)相似性為：

其中余弦值越接近1，就表明夾角越接近0度，也就是兩個向量越相似，在網(wǎng)絡(luò)結(jié)構(gòu)上兩個節(jié)點越相似.wxy為節(jié)點x和節(jié)點y之間的邊權(quán)，在無權(quán)網(wǎng)絡(luò)環(huán)境下表示的是兩節(jié)點是否相連，相連為1，反之為0.

因為RWR指標的隨機游走轉(zhuǎn)移概率僅考慮節(jié)點的度信息而不關(guān)心節(jié)點的潛在拓撲結(jié)構(gòu)特征，所以本文將定義1中計算得到的節(jié)點拓撲結(jié)構(gòu)相似性加入隨機游走過程中，給出定義2的基于圖嵌入法模型的有偏向的隨機游走轉(zhuǎn)移概率.

定義2任意節(jié)點x與其任意鄰居節(jié)點y的轉(zhuǎn)移概率為：

其中A∈(0,1)，表示動力系數(shù)，即控制粒子隨機游走的動力，決定當前時刻是否進行隨機游走,從結(jié)果上看也決定了粒子隨機游走的范圍.當A=1時，粒子一直保持隨機游走動力，每次游走都將選擇當前節(jié)點的一個鄰居節(jié)點作為下一個游走目標，會盡可能地考慮全局信息；隨著A的值不斷縮小，粒子會更傾向于保持原地，進行相對局部的游走；當A=0時，粒子將永久停留在原地，這種情況是不符合常理的，這里僅作為參數(shù)的邊界.N(x)為節(jié)點x的鄰居節(jié)點集合，∑z∈N(x)CosSim(x,z)是歸一化因子.

2.2 時序網(wǎng)絡(luò)下的轉(zhuǎn)移概率

定義1和定義2都是基于靜態(tài)網(wǎng)絡(luò)環(huán)境下的定義，而現(xiàn)實網(wǎng)絡(luò)有很多是動態(tài)變化的.如果這種動態(tài)變化的規(guī)律可以被算法識別，那么就可以有效提高預(yù)測結(jié)果的精確度.

定義3給定時間窗口大小T的全局時序網(wǎng)絡(luò)隨機游走概率為：

其中，γ∈(0,1)表示阻尼因子，Pt表示當前時刻下的粒子有偏向轉(zhuǎn)移概率.

2.3 算法流程

本文提出的算法主要改進的是RWR指標的轉(zhuǎn)移概率，算法的主要原理同RWR，即通過引入重啟因子α進行隨機游走從而捕捉網(wǎng)絡(luò)的全局信息，進而預(yù)測網(wǎng)絡(luò)的鏈路.因為使用了圖嵌入方法計算有偏向轉(zhuǎn)移概率并基于時序網(wǎng)絡(luò)應(yīng)用，因此該算法被命名為基于圖嵌入法的時序網(wǎng)絡(luò)重啟隨機游走算法(Graph Embedding Temporal Random Walk with Restart，GETRWR)，其主要流程如下：

輸入：時序網(wǎng)絡(luò)G(V,Et,At)(t=t0,t0+1,…,t0+T-1)，重啟因子α∈(0,1)，動力系數(shù)A∈(0,1)，阻尼因子γ∈(0,1).

輸出：時序網(wǎng)絡(luò)相似性矩陣S.

②根據(jù)定義2計算每一時刻下的節(jié)點間轉(zhuǎn)移概率并更新Pt;

④Fori=1 tondo；

⑤WhileS不收斂 do；

⑥πx=(1-α)(I-αPT)-1ex;

⑦End While;

⑧End For;

⑨ReturnS.

3 實驗結(jié)果與分析

在本部分將使用真實網(wǎng)絡(luò)數(shù)據(jù)集對以上算法進行實驗驗證，并使用經(jīng)典的基準指標做性能對比.

3.1 實驗數(shù)據(jù)

Email：一家中型制造業(yè)企業(yè)員工間的郵件交流(2010.1.3—2010.10.1)；

FB：Facebook用戶間的論壇交互(2004.5.15—2004.10.26).

實驗數(shù)據(jù)是典型的時序網(wǎng)絡(luò)，其中節(jié)點與連邊隨時間變化而變化，網(wǎng)絡(luò)信息見表1.

表1 網(wǎng)絡(luò)的基本信息Tab.1 Basic information about the network

3.2 實驗結(jié)果與分析

根據(jù)實驗數(shù)據(jù)的時間跨度，按周為單位將數(shù)據(jù)集劃分為合適數(shù)量的時間切片，其中Email的時間切片數(shù)量為38個，F(xiàn)B的時間切片數(shù)量為22個.

3.2.1 預(yù)測結(jié)果

設(shè)置時間窗口T=10，動力系數(shù)A=0.1，阻尼因子γ=0.5，選擇經(jīng)典的鏈路預(yù)測指標CN、AA、RA、PA、RWR作為基準指標，選擇AUC作為評價指標.其中對于基準指標使用時序網(wǎng)絡(luò)的計算方法，即將歷史信息作為訓(xùn)練集，當前時刻的網(wǎng)絡(luò)作為測試集.實驗結(jié)果如表2所示.

表2 GETRWR與其他指標的預(yù)測效果(AUC)Tab.2 The predictive effect of GETRWR and other indicators

從整體上看，GETRWR表現(xiàn)符合預(yù)期，具有最優(yōu)的性能表現(xiàn)，預(yù)測準確率最高.其中對于RWR指標有明顯提升，尤其在Email數(shù)據(jù)集上預(yù)測效果提升了1.89%，說明有偏向的轉(zhuǎn)移在時序網(wǎng)絡(luò)中起到了積極作用.此外，在時序網(wǎng)絡(luò)中時間窗口的大小是非常重要的一個參數(shù)，其次動力系數(shù)和阻尼因子這兩個算法中的參數(shù)也對實驗結(jié)果有影響，因此分別對這3個參數(shù)控制變量進行實驗，觀察實驗結(jié)果.

3.2.2 時間窗口的影響

設(shè)置時間窗口大小T為變量，固定動力系數(shù)A=0.1，阻尼因子γ=0.5，實驗的AUC值隨時間窗口大小變化的趨勢如圖2所示.

當時間窗口T=1時，相當于預(yù)測模型僅使用前一時刻的網(wǎng)絡(luò)信息進行訓(xùn)練，因為包含的歷史信息過少從而預(yù)測效果最差.隨著時間窗口T的不斷增加，預(yù)測結(jié)果也隨之增長，這是因為時序網(wǎng)絡(luò)的節(jié)點信息變化較快，必須參考一定數(shù)量的歷史信息才能訓(xùn)練好時序模型，而獲取了一定數(shù)量的歷史信息后，預(yù)測結(jié)果會呈現(xiàn)一種穩(wěn)定的狀態(tài)，不會因為急需增加歷史信息而明顯變化.由圖可見，當T>10時，算法的預(yù)測效果趨于平穩(wěn).值得注意的是，GETRWR較RWR指標，除了T較小的情況外，預(yù)測效果均占優(yōu)勢，同樣說明了粒子在隨機游走中的有偏向轉(zhuǎn)移的重要性.此外，實驗發(fā)現(xiàn)CN、AA、RA在實驗數(shù)據(jù)集上的表現(xiàn)接近，說明了在這一類數(shù)據(jù)中，基于共同鄰居和懲罰大度節(jié)點的效果接近.

3.2.3 動力系數(shù)的影響

設(shè)置動力系數(shù)A為變量，固定時間窗口T=10，阻尼因子γ=0.5，實驗結(jié)果AUC隨動力系數(shù)變化的趨勢如圖3所示.

圖3 動力系數(shù)的影響Fig.3 The influence of dynamic coefficient圖4 阻尼因子的影響Fig.4 The influence of damping factor

對于不同的數(shù)據(jù)集，動力系數(shù)的最優(yōu)值也有所不同，對于本文選取的兩個網(wǎng)絡(luò)，動力系數(shù)的最優(yōu)值出現(xiàn)在0.1～0.3之間，這和具體的網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)，說明對于這類特征的網(wǎng)絡(luò)，粒子進行局部隨機游走的效果會更好.GETRWR算法中動力系數(shù)的大小對預(yù)測精度有較大的影響，因此可以通過實驗調(diào)參獲取最佳的動力系數(shù).

3.2.4 阻尼因子的影響

設(shè)置阻尼因子γ為變量，固定時間窗口T=10，動力系數(shù)A=0.1，實驗結(jié)果AUC隨阻尼因子變化的趨勢如圖4所示.

根據(jù)上文定義3的公式可知，當γ=1時，GETRWR在計算轉(zhuǎn)移概率時平等看待了所有的歷史時間切片，即最遠和最近的時間切片有相同的權(quán)重，這樣導(dǎo)致過于久遠的歷史信息對預(yù)測產(chǎn)生了干擾影響.而當γ過小時，歷史信息所占權(quán)重很低，從而導(dǎo)致預(yù)測效果不佳.圖4的結(jié)果也證明了當γ處于0.4～0.6之間時，算法的性能最高，說明了較為久遠的歷史信息雖然可能對預(yù)測結(jié)果帶來“誤導(dǎo)”，但也不可完全忽視.GETRWR算法中阻尼因子的大小對預(yù)測精度有較大的影響，因此對于實驗結(jié)果可以通過調(diào)參找到最佳的阻尼因子.

4 結(jié)論

時序網(wǎng)絡(luò)是鏈路預(yù)測研究中的一個重點，因為其特有的“時序性”，導(dǎo)致了常用的基于靜態(tài)網(wǎng)絡(luò)的方法不再高效適用.本文提出了一種新的時序網(wǎng)絡(luò)鏈路預(yù)測算法(GETRWR)，其中改進了鏈路預(yù)測中粒子隨機游走的傳統(tǒng)轉(zhuǎn)移方式，即定義了考慮節(jié)點拓撲結(jié)構(gòu)相似性后的有偏向轉(zhuǎn)移.研究使用圖嵌入法訓(xùn)練節(jié)點序列生成節(jié)點向量，可以從低維的向量空間上比較節(jié)點的拓撲結(jié)構(gòu)特征，基于此計算粒子在隨機游走過程中的有偏向轉(zhuǎn)移，并替換RWR中的轉(zhuǎn)移概率.此外，針對時序網(wǎng)絡(luò)的時序性特點，考慮歷史信息的影響，對于不同時刻的時間切片賦予不同的權(quán)重，將不同時刻下的粒子轉(zhuǎn)移概率融合成全局的轉(zhuǎn)移概率，基于這種轉(zhuǎn)移概率應(yīng)用的時序網(wǎng)絡(luò)鏈路預(yù)測算法有較高的性能表現(xiàn)，較基準指標有較大的提升.在下一步的研究中，會考慮有向網(wǎng)絡(luò)的情況，并比對更多的時序網(wǎng)絡(luò)數(shù)據(jù)集和現(xiàn)有的時序網(wǎng)絡(luò)鏈路預(yù)測方法.