基于資源分配與圖嵌入加權的鏈路預測算法

萬楊曄,郭進利

(上海理工大學管理學院,上海 200093)

0 引 言

現(xiàn)實世界中不同實體之間的相互作用組成了各式各樣的網(wǎng)絡，實體之間的關系是不斷變化的，所以節(jié)點和連邊的增加或移除總在發(fā)生，導致網(wǎng)絡的高度動態(tài)和復雜，理解這些網(wǎng)絡的演化機制具有理論價值和實際意義。鏈路預測能處理網(wǎng)絡的結構和演化的問題，能根據(jù)節(jié)點屬性信息、結構特征來估計2個節(jié)點間存在鏈接的可能性[1]。在現(xiàn)實生活中，預測網(wǎng)絡中的缺失鏈接有著廣泛的應用。在京東、淘寶等線上購物網(wǎng)絡中，鏈路預測能根據(jù)用戶購物記錄或瀏覽記錄推薦用戶感興趣的商品；在生物領域，利用已知的蛋白質之間存在的相互作用關系[2]，準確預測蛋白質之間未知相互作用可以幫助人們大幅降低實驗成本并節(jié)省實驗時間；在線上社交網(wǎng)絡如微博中，通過用戶現(xiàn)有的關注關系，鏈路預測能挖掘出可能認識的朋友或感興趣的用戶[3]。

目前，基于相似性的鏈路預測方法在實際應用中較為常見，其計算簡單、精度較高并且對于同種類型結構的網(wǎng)絡都具有普遍良好的效果。這種相似性指標主要分3類，第1類是局部信息指標，這類指標大多在CN(Common Neighbors)指標上進行進一步的挖掘，如Adamic-Adar(AA)指標[4]給共鄰節(jié)點以度值對數(shù)倒數(shù)賦權，資源分配(Resource Allocation, RA)指標[5]也是以同樣思想以度值倒數(shù)賦權，CCLP (Clustering Coefficient based Link Prediction)指標[6]以共鄰的聚集系數(shù)之和表示出現(xiàn)鏈接的可能性等。第2類是路徑指標，主要有LP(Local Path)[7]、Katz指標[8]等，分別計算節(jié)點間不同長度的路徑。第3類是隨機游走指標，這類指標主要計算2節(jié)點間隨機游走所需步數(shù)或時間[9-11]，相比于局部信息和路徑指標有著更好的預測精度，但同時計算復雜度也變高。這些鏈路預測指標的研究都是在靜態(tài)無權網(wǎng)絡上進行的，相關研究表明，在加權網(wǎng)絡上結合網(wǎng)絡權重信息能有效提高預測效果。郭景峰等[12]提出了加權網(wǎng)絡上的多路徑節(jié)點傳輸?shù)南嗨菩?。白楊等[13]提出了局部圖與可靠路徑相結合的加權網(wǎng)絡預測算法。Zhu等[14]提出了加權互信息模型，結合了結構屬性和鏈接權重的優(yōu)點。Wu等[15]提出了加權的局部樸素貝葉斯模型，引入加權聚集系數(shù)來表示角色函數(shù)，將局部樸素貝葉斯模型擴展到加權網(wǎng)絡中。Xu等[16]基于路徑的貢獻提出了加權路徑熵算法。這些研究都展示了結合網(wǎng)絡權重信息的鏈路預測方法，都優(yōu)于無權網(wǎng)絡上的指標。上述加權預測算法都是基于網(wǎng)絡的自然權重信息，部分學者提出了對于網(wǎng)絡拓撲結構生成鏈接權重的鏈路預測算法。Wang等[17]在生物網(wǎng)絡中利用鏈接聚集系數(shù)表示鏈接權重來增強網(wǎng)絡的魯棒性，Zhu等[18]采用余弦度量的歸一化聚集系數(shù)構造加權網(wǎng)絡鏈路預測，袁榕等[19]提出了一種利用邊的聚集與擴散特性生成鏈接拓撲權重的WCD(Weight of Clustering and Diffusion)預測算法。這些研究都表明網(wǎng)絡的結構權重可以代替自然權重信息來進一步提升鏈路預測精度。

本文提出一種基于資源分配與圖嵌入加權的方法用于鏈路預測，由網(wǎng)絡的局部結構與高階結構信息生成結構權重。首先利用資源分配指標得到的相似性作為局部信息權重，再由DeepWalk算法得到的相似性作為高階結構信息權重，將局部信息RA權重與高階信息DeepWalk權重相結合表示網(wǎng)絡的拓撲結構權重，以這個結構權重進行加權鏈路預測，與3種不同類型的基于相似性的鏈路預測算法以及基于邊特性的WCD加權算法進行比較，在真實網(wǎng)絡數(shù)據(jù)集上的實驗結果表明，本文提出的加權算法能有效提高鏈路預測精度。

1 基本概念

1.1 問題描述

給定網(wǎng)絡G=(V,E),V表示節(jié)點集合，E表示連邊集合，若網(wǎng)絡中節(jié)點數(shù)為|V|，則網(wǎng)絡中最多有|V|(|V|-1)/2條連邊。網(wǎng)絡的鄰接矩陣用A來表示，若節(jié)點i與節(jié)點j之間有連邊，則aij=1，否則aij=0。ki表示節(jié)點i的度，Γ(i)表示節(jié)點i的鄰居節(jié)點集合。鏈路預測是為了找尋網(wǎng)絡中缺失的鏈接或者未來可能出現(xiàn)的鏈接，首先定義一個相似性指標，根據(jù)相似性指標分配給目標節(jié)點對(x,y)一個分數(shù)Sxy，分數(shù)大小與當前節(jié)點對存在缺失鏈接或未來出現(xiàn)鏈接的概率正相關。

1.2 基準指標

1)基于局部信息的共同鄰居CN指標。

2個節(jié)點擁有的共同鄰居數(shù)量越多，節(jié)點間出現(xiàn)鏈接的可能性越大，節(jié)點x與y之間的相似性定義為：

sxy=|Γ(x)∩Γ(y)|

(1)

其中，Γ(x)表示節(jié)點x的鄰居節(jié)點集合。

CN指標加權形式：

(2)

其中，wxy表示節(jié)點x與y之間連邊權重。

2)基于路徑的局部路徑LP指標[7]。

LP指標是在二階鄰居的基礎上加入了三階鄰居的影響，LP指標定義為：

(3)

其中，ε為調節(jié)系數(shù)，A為網(wǎng)絡的鄰接矩陣。

LP指標加權形式[10]：

(4)

其中，lx→y是從節(jié)點x到節(jié)點y的三階路徑，a和b是路徑lx→y上的節(jié)點。

3)基于隨機游走的重啟隨機游走RWR指標[9]。

重啟隨機游走是一個基于隨機游走定義的模型，選擇一個起始節(jié)點，隨機游走粒子在網(wǎng)絡上的每一步游走會出現(xiàn)2種情況，以概率c移動到一個隨機選擇的鄰點，或者以1-c的概率重新回到起始節(jié)點，粒子游走的公式如下：

πx(t+1)=cPTπx(t)+(1-c)ex

(5)

其中，P為粒子在網(wǎng)絡節(jié)點間轉移的概率矩陣，矩陣元素為Pxy=axy/kx，axy為網(wǎng)絡鄰接矩陣A中對應的元素，kx為節(jié)點x的度。ex為只有第x個元素為1的N維列向量，表示粒子的初始狀態(tài)，可計算式(5)迭代達到平穩(wěn)狀態(tài)的解為：πx=(1-c)(I-cPT)-1ex，πx是一個列向量，則RWR指標定義為2節(jié)點間相互轉移的概率之和：

(6)

2 鏈路預測算法

圖嵌入方法也被稱為網(wǎng)絡表示學習方法，能通過學習網(wǎng)絡拓撲結構特征，將網(wǎng)絡中的節(jié)點嵌入低維空間，得到網(wǎng)絡節(jié)點的低維稠密向量。圖嵌入得到節(jié)點向量后可以做網(wǎng)絡研究的一系列下游任務，如節(jié)點分類、鏈路預測等。常見的圖嵌入算法有DeepWalk[20]、Node2vec[21]、LINE[22]等。DeepWalk算法是將自然語言處理中的Word2Vec模型[23]應用在網(wǎng)絡上的一種圖嵌入算法。在自然語言處理中，少部分單詞作為常用單詞出現(xiàn)頻率高，大部分單詞出現(xiàn)頻率低，而在網(wǎng)絡上進行隨機游走時，一個節(jié)點在游走路徑上出現(xiàn)的頻率也與節(jié)點度相關，少部分度大的節(jié)點出現(xiàn)的頻率高，大部分度小的節(jié)點出現(xiàn)的頻率低。網(wǎng)絡節(jié)點在游走序列中出現(xiàn)的頻率與自然語言中單詞在句子中出現(xiàn)頻率都是服從相同的冪律分布特征的。基于這種相同的冪律分布特征，將Word2Vec模型應用到了網(wǎng)絡上，下面介紹DeepWalk算法的詳細步驟。先在網(wǎng)絡上選取一個節(jié)點作為起始節(jié)點做游走長度為t的隨機游走，得到一個節(jié)點序列，以這個節(jié)點為初始點重復采樣γ次。將所有節(jié)點采樣完成后，將節(jié)點序列作為輸入，導入Word2Vec中的Skip-Gram模型中，給節(jié)點序列的窗口大小設置為w，對于生成的節(jié)點向量Φ(vi)，最大化窗口中節(jié)點鄰居的概率，不斷訓練最終得到節(jié)點向量：

(7)

資源分配RA指標[5]是由復雜網(wǎng)絡中發(fā)生信息流傳遞或資源分配的物理過程所驅動的，信息流與資源在網(wǎng)絡節(jié)點對(x,y)上傳遞的過程中，它們的共同鄰居節(jié)點作為傳遞媒介，將信息流及資源根據(jù)自身鄰居個數(shù)平均分配，節(jié)點x到節(jié)點y的資源量定義為RA相似性：

(8)

資源分配指標很好地表示了2個節(jié)點間資源傳遞的過程，受此啟發(fā)，考慮用2個節(jié)點的資源分配指標構造鏈接的結構權重。

然而若單純以資源分配指標賦予目標節(jié)點對(x,y)間的連邊結構權重，如圖1所示，RA指標在網(wǎng)絡結構上只考慮到了節(jié)點x與y的一階共同鄰居a和b的信息，沒有計算網(wǎng)絡結構的更高階信息，例如節(jié)點c和d作為節(jié)點x與y的二階鄰居也會對x與y之間連邊權重產(chǎn)生影響，f和g等節(jié)點雖然不是目標節(jié)點對的共同鄰居，但作為目標節(jié)點對的三階鄰居也會對于結構權重有一定的影響，RA指標只能展示結構權重的部分信息，因此只將之作為局部結構權重。而DeepWalk算法生成的節(jié)點向量包含了上下文的節(jié)點信息，即包含了網(wǎng)絡的高階結構信息，將節(jié)點向量間的余弦相似性作為節(jié)點鏈接的高階結構權重，可以有效彌補RA指標不能表示高階結構信息的缺陷。因此本文將資源分配指標與DeepWalk相似性相結合表示網(wǎng)絡的拓撲結構權重。

圖1 網(wǎng)絡結構圖

由DeepWalk算法生成的節(jié)點向量計算節(jié)點x與節(jié)點y之間的余弦相似性：

(9)

將計算得到的余弦相似性映射到(0,1)區(qū)間，然后與RA指標相結合，那么網(wǎng)絡2連邊節(jié)點x與y之間的結構權重定義為：

(10)

在上式結構權重中，將前一項稱為DeepWalk權重，后一項稱為RA權重。其中參數(shù)α是調節(jié)DeepWalk權重與RA權重結合的比例，當α=0時，結構權重退化為RA權重，當α=1時，結構權重由DeepWalk加權。

在進行鏈路預測時，先將網(wǎng)絡利用本文的算法對網(wǎng)絡進行結構加權，之后再利用計算出的權重信息將無權網(wǎng)絡轉化為加權網(wǎng)絡進行加權網(wǎng)絡鏈路預測，通過對權重比例參數(shù)α的調整，確定在不同網(wǎng)絡上的最優(yōu)參數(shù)，以此有效提高鏈路預測效果。

基于資源分配與圖嵌入加權的算法流程如下：

輸入：網(wǎng)絡G(V,E)

輸出：節(jié)點相似度矩陣S

1)利用RA指標得到局部權重。

2)利用DeepWalk算法得到高階權重。

3)根據(jù)式(10)計算網(wǎng)絡的結構權重。

4)將權重信息應用到加權算法得到相似度矩陣S。

3 實驗結果及分析

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

本實驗采用了4個真實網(wǎng)絡數(shù)據(jù)集進行鏈路預測實驗,分別是美國政治博客網(wǎng)絡PB、線蟲神經(jīng)網(wǎng)絡Celegans、佛羅里達生態(tài)系統(tǒng)食物鏈網(wǎng)絡FWFW、線蟲新陳代謝網(wǎng)絡Metabolic。4個網(wǎng)絡數(shù)據(jù)集的拓撲結構性質如表1所示。其中，V表示節(jié)點數(shù)，E表示邊數(shù)，D表示平均度，C表示平均聚集系數(shù)，R為同配系數(shù)。

表1 網(wǎng)絡的拓撲性質

3.2 評價指標

本文利用AUC指標評估提出的結構加權算法的預測效果，采用隨機抽樣的方法從網(wǎng)絡數(shù)據(jù)集中提取10%的節(jié)點對連邊作為測試集EP，剩下連邊作為訓練集ET的同時保證原始網(wǎng)絡結構不發(fā)生較大變化，即訓練集連邊網(wǎng)絡具有連通性。設U(|U|=|V|(|V|-1)/2)為所有節(jié)點對組成的全集，計算時，首先計算出節(jié)點對全集U的相似性得分，然后從測試集EP中與不存在邊U-E中各隨機選取一條邊，比較2條邊的相似性得分，如果測試集連邊相似性得分大于不存在邊得分，則加1分，分數(shù)相等，則加0.5分。獨立重復地比較n次，若測試集得分高的次數(shù)為n′次，得分相等的次數(shù)有n″次，則AUC指標定義為：

顯然，若隨機打分，則AUC值約為0.5，AUC值越高，算法精度越高。

3.3 實驗結果

參數(shù)設置：DeepWalk模型參數(shù)窗口w=5，維數(shù)d=128，采樣次數(shù)γ=10，步長t=10；LP指標的三階貢獻參數(shù)設置為ε=0.01；RWR指標重啟概率設置為c=0.85。

實驗結果分為3個部分，第1部分是利用AUC指標分析權重調節(jié)參數(shù)α的變化對預測精度的影響；第2部分是將在最優(yōu)α下的W-CN、W-LP、W-RWR指標與無權的CN、LP、RWR指標以及基于WCD加權指標在4個真實網(wǎng)絡數(shù)據(jù)集上的預測精度進行對比，觀察融入RA與DeepWalk結構權重信息后的指標的預測效果。第3部分是觀察在不同訓練集比例下，預測結果的變化情況。

3.3.1 參數(shù)α對預測精度的影響

將本文的結構加權算法應用在4個真實網(wǎng)絡數(shù)據(jù)集上，忽略原網(wǎng)絡的連邊方向，以CN、LP、RWR為基準指標，將加入結構權重信息之后進行加權鏈路預測的指標命名為W-CN、W-LP、W-RWR。對于4個真實網(wǎng)絡，圖2展示了不同網(wǎng)絡中結構權重調節(jié)參數(shù)α變化對3個指標預測結果的影響，參數(shù)α的變化步長設置為0.1。

(a) PB

(b) Celegans

(c) FWFW

(d) Metabolic

在Celegans、Metabolic網(wǎng)絡上，當α值由0到0.1的過程中，AUC值都有小幅提升，在α值由0.2增大到1的過程中，基本在α=0.5左右AUC趨近最大值，后續(xù)AUC值變化趨于平緩，說明在結構權重中加入DeepWalk權重對預測精度提升是有效的。在PB網(wǎng)絡上，W-CN與W-LP都在α=0.1左右取得最優(yōu)AUC值，α繼續(xù)增大AUC值有所降低，W-RWR在α=0.5之后變化趨于平緩，同樣說明RA權重與DeepWalk權重相結合能有效提高預測精度。在FWFW網(wǎng)絡上，當α=0時，即僅由RA加權時，W-LP與W-CN指標都取得了最大AUC值，加入DeepWalk權重后預測精度反而降低，這是由FWFW網(wǎng)絡的結構特性決定的，表明FWFW食物鏈網(wǎng)絡更注重局部鄰居信息，在FWFW網(wǎng)絡上RA權重更能代表結構權重。

3.3.2 算法精度對比分析

將利用本文方法對網(wǎng)絡結構加權后進行預測的W-CN、W-LP、W-RWR指標與無權的CN、LP、RWR指標以及基于邊特性WCD加權的WCD-CN、WCD-LP、WCD-RWR指標在4個真實網(wǎng)絡數(shù)據(jù)集上的預測精度進行對比，結果如表2所示，其中W-CN、W-LP、W-RWR指標的AUC值為隨參數(shù)α變化取得的最優(yōu)值。

表2 加權算法與基準算法AUC值對比

從表2可以看出，使用RA與DeepWalk加權的W-CN、W-LP、W-RWR指標相較于無權的CN、LP、RWR指標，預測精度都有所提高，而相較于WCD加權的指標也有著較好的效果。其中加權后的W-CN相較CN指標預測精度平均提升3.7%，W-LP相較LP指標預測精度平均提升2.65%，即使與在相似性指標中表現(xiàn)最好的RWR指標相比，W-RWR也有一定程度提升，平均提升0.2%。而且與基于邊特性加權的WCD方法相比，本文的加權方法在大多數(shù)網(wǎng)絡上都表現(xiàn)出更好的預測效果，而WCD方法由于在拓撲權重上融入了邊的擴散特性，在一定程度上削弱了節(jié)點間粒子的游走概率，導致在加權隨機游走指標上表現(xiàn)不佳?？梢钥闯?，本文所提出的資源分配與圖嵌入加權的方法相比于無權算法是有較好效果的，且與已有的加權算法相比也有一定程度的提升。

3.3.3 預測精度隨訓練集大小的變化情況

在本實驗中，將訓練集比例從0.6增長至0.9，步長為0.1，得到本文的W-CN、W-LP、W-RWR以及對應的CN、LP、RWR的AUC值隨訓練集大小的變化情況，如圖3所示。

在4個網(wǎng)絡數(shù)據(jù)集上，AUC值都隨訓練集比例的增加而增大，在訓練集比例為0.9時AUC值達到最大，且在不同訓練集比例下W-CN、W-LP、W-RWR的AUC值都高于相應的CN、LP、RWR指標，表明本文的方法具有較強的穩(wěn)定性和更好的預測精度。

(a) PB

(b) Celegans

(c) FWFW

(d) Metabolic

4 結束語

本文對無權網(wǎng)絡提出了一種從網(wǎng)絡結構中生成隱式結構權重的鏈路預測算法。分別計算RA權重和DeepWalk權重，并按照一定比例結合得到網(wǎng)絡的結構權重，之后應用到加權鏈路預測算法上，通過調整RA權重與DeepWalk權重的融合參數(shù)α找到最優(yōu)預測精度。實驗結果表明，基于資源分配與圖嵌入加權的方法相比于未加權指標以及已有的拓撲加權指標，預測精度得到有效提高且具有良好的穩(wěn)定性。