一種疊加隨機游走重力模型的鏈路預測算法

姜萬昌,路明明

(1.東北電力大學 計算機學院， 吉林 吉林 132012；2.東北電力大學 吉林省智能電網信息技術工程實驗室， 吉林 吉林 132012)

0 引言

鏈路預測用于蛋白質網絡預測[1]、航班風險預測[2]、網絡結構優化[3]等領域，揭示網絡的結構特性。其中廣泛使用的基于網絡結構的鏈路預測算法分為基于局部信息、基于路徑和基于隨機游走三類算法。第一類基于局部信息算法，其使用最廣泛的CN算法(common neighbors)利用節點之間公共鄰居節點的數量進行預測[4]。Adamic等[5]利用共同鄰居節點的度提出AA算法(adamic-adar)。AA是CN的變型，公共鄰居節點的度越大，節點之間存在鏈路的可能性越小。Lyu等[6]受網絡資源分配過程的啟發提出與AA算法相似的RA算法(resource allocation)，兩者預測效果相近。這些算法不能區分不同公共鄰居節點的作用，Liu等[7]提出局部樸素貝葉斯模型LNBCN和LNBRA算法，揭示不同公共鄰居節點的不同作用。第一類算法較簡單，算法的時間復雜度較低，但只考慮節點或節點之間的公共鄰居節點的度，沒有結合更多的網絡結構信息。第二類基于路徑算法中，Katz算法[8]使用2個節點之間的所有路徑，通過對路徑的長度進行懲罰的方式預測，在許多網絡上具有不錯的預測效果。但計算節點之間的所有路徑會導致算法的時間復雜度高，因此又提出在CN算法和Katz算法之間折衷的LP算法[8]，只利用長度為2和3的路徑信息。第二類算法增加節點的路徑信息，較第一類算法考慮更多的網絡結構特征，但沒有利用節點之間的緊密程度度量。第三類基于隨機游走算法中，RWR(random walk with restart)算法[9]從源節點隨機游走一步后有一定概率在下一時刻回到源節點，利用游走穩定達到目的節點時的概率進行預測計算。這樣計算的復雜度較高，邵豪等[9]用節點度量化隨機游走轉移概率，只考慮幾步隨機游走提出LRW算法(local random walk)。為提高目標節點與附近節點之間轉移概率，在LRW上疊加局部游走步數得到SRW(superposed random walk) 算法[9]。第三類算法精度較高，但只關注一種結構特征假設適用于所有網絡，其預測性能在不同網絡上具有不穩定性。這三類算法在真實的網絡數據集上進行對比實驗，呂琳媛[10]的研究結果表明第三類基于隨機游走的算法具有較高的準確性，尤其是基于局部隨機游走的算法具有更高預測精確度。但對于具有局部高聚集程度的網絡，局部隨機游走算法沒有考慮網絡局部節點與鄰居節點的緊密程度。

鏈路預測中節點與鄰居節點的緊密程度可以用聚類系數衡量。研究表明，網絡的聚類系數能有效提高鏈路預測效果[11]。Wu等[12]提出基于節點聚類系數的CCLP算法，但沒有考慮鄰居節點的度。高楊等[13]在此基礎上結合鄰居節點的度，提出一種結合節點度和聚類系數的鏈路預測NDCC算法。陳紫揚等[14]認為NDCC算法只考慮單層度，信息不全面，提出結合二層節點度和聚類系數的鏈路預測TDNCC算法，雖然提高了基于局部信息的算法性能，并且與基于隨機游走的算法相比性能較優，但不適于具有局部高聚集程度的網絡。

綜上考慮，在具有局部高聚集程度的網絡中，針對局部隨機游走算法可能無法區分網絡中存在度和聚類系數均高的節點之間預測效果的問題，在局部隨機游走的基礎上，結合公共鄰居節點的聚類系數，并對游走步數進行疊加計算，在全局網絡上利用重力模型，提出一種疊加隨機游走重力模型鏈路預測算法。

1 鏈路預測算法

結合鄰居節點的度和聚類系數，改進疊加隨機游走的轉移概率，引入重力模型，提出一種疊加隨機游走重力模型的鏈路預測算法。

1.1 改進的隨機游走轉移概率

對于具有局部高聚集程度的網絡，等概率隨機游走不能很好地反映這種網絡結構，預測效果不佳。因此，本節結合聚類系數和RA算法，構建改進的隨機游走轉移概率矩陣。

網絡G=(V,E,A)，V表示G的節點集，N=|V|表示G的節點數，E表示G的邊集，A=(axy)N×N表示G的鄰接矩陣。若G中節點滿足(x,y)∈E，axy值為1，否則axy值為0。當G中存在度和聚類系數均高的節點v′，其構成的節點集V′滿足V′={v′|v′∈V,kv′>0.6·Maxdegree,Cv′>0.6}且|V′|>0.1·N時，G是具有局部高聚集程度的網絡，其中|V′|表示v′的數量，kv′表示v′的度，Maxdegree表示G的最大度數，Cv′表示v′的聚類系數。

構造隨機游走模型并設置初始狀態，將一個walker放置在網絡G的任意節點x處，規定walker以節點之間的相似性作為轉移概率同時進行隨機游走，游走的每一步的選擇相互獨立。受Node2vec算法[15]的啟發，按照節點x與節點y有無公共鄰接節點分2種情況，分別計算walker從節點x到節點y的轉移概率：

1) 當節點x與節點y無公共鄰居節點，滿足x的鄰居節點集Γ(x)與y的鄰居節點集Γ(y)交集為空，即Γ(x)∩Γ(y)=?時，根據y的度可以區分walker游走到x的不同鄰居節點的轉移概率。考慮節點x、節點y的度以及兩者之間的連接情況，利用A，定義轉移概率如式(1)所示。

(1)

式中：axy表示x與y是否連接；kx、ky分別表示x、y的度。

2) 當節點x與節點y有公共鄰居節點時，公共鄰居節點的聚類系數反映x和y周圍節點的聚集程度，但當節點之間的公共鄰居節點具有相同的聚類系數時，不能區分節點之間的相似性，故將公共鄰居節點的度與聚類系數結合；RA算法能有效地反映x與y的公共鄰居節點影響x到y的資源分配情況，則定義轉移概率如式(2)所示。

(2)

綜合上述2種情況，定義網絡G改進的隨機游走轉移概率如式(3)所示。

(3)

(4)

1.2 疊加局部隨機游走

局部的隨機游走與全局的隨機游走相比，在時間復雜度較小時能獲得較高的精度，故在網絡G中按照改進的隨機游走轉移概率進行有限步數的局部隨機游走。為了充分結合G的結構特征，進行疊加局部隨機游走。

在網絡G中，walker從任意節點開始隨機游走t步到達G上其余節點的轉移概率向量為:

πx(t)=PT·πx(t-1)

(5)

式中：πx(0)=ex表示walker的初始狀態，ex是一個1×N的行向量，該向量第x列處元素為1，其余全為0；P表示改進的隨機游走轉移概率矩陣；T表示矩陣轉置。

假定任意節點x的初始資源分布為x的度kx，則節點x與任意節點y基于t步局部隨機游走的轉移概率為：

(6)

將前t步的結果相加，得到節點x與任意節點y基于t步疊加局部隨機游走的轉移概率為:

(7)

1.3 疊加隨機游走重力模型

重力模型已用于定義節點的吸引力識別復雜網絡中的關鍵節點[17]，可以從全局網絡的角度分析節點之間的關系影響，故引入重力模型，設計疊加隨機游走重力模型，計算節點之間的相似性。

(8)

根據計算G的節點之間的相似性，最后得到疊加隨機游走重力模型節點相似性矩陣為S=(Sxy)N×N。

1.4 疊加隨機游走重力模型的鏈路預測算法

使用疊加隨機游走重力模型，得到疊加隨機游走重力模型鏈路預測算法(link prediction algorithm based on superimposed random walk gravity model，SRWG)，其中步驟1)—6)初始化改進的隨機游走轉移概率矩陣S′、疊加局部隨機游走的轉移概率矩陣πSRW、疊加隨機游走重力模型節點相似性矩陣S等；步驟7)—10)用式(3)和式(4)計算S′并標準化處理得到改進數的隨機游走轉移概率矩陣P；步驟11)—17)用式(5)—(7)計算得到基于步疊加局部隨機游走的轉移概率矩陣πSRW；步驟18)—21)用式(8)計算疊加隨機游走重力模型節點相似性矩陣S。

SRWG算法如下:

輸入:網絡G的鄰接矩陣A=(axy)N×N、隨機步長t輸出:疊加隨機游走重力模型節點相似性矩陣S=(Sxy)N×N

1) 初始化改進的隨機游走轉移概率矩陣S′←0N×N；

2) 初始化G節點間的最短路徑矩陣D←(dxy)N×N；

3) 初始化G節點間的連通度矩陣H←(hxy)N×N；

4) 初始化基于步疊加局部隨機游走的轉移概率矩陣πSRW←IN×N；

5) 初始化疊加隨機游走重力模型節點相似性矩陣S←0N×N；

6) 初始化G節點間的公共鄰居節點度總數矩陣B←A*AT；

目前我國沒有正式的養老地產項目用地的供應政策。養老地產的建設用地優惠力度表現得并不明顯。從各地實踐看，截至2012年底，北京市、四川省、吉林省、山東省、廣東省陸續采取“養老綜合用地招拍掛”政策，養老用地被政府納入土地利用總體規劃。在用地上，優先安排符合規劃的養老服務設施的建設用地。

7) Forx←1 toΝdo 7)—10)

8) Fory←1 toΝdo

10) 用式(4)標準化處理S′得到P；

11) Forx←1 toΝdo 11)—17)

12) 迭代t步

13)P代入式(5)中；

14) 用式(5)計算G中walker從任意x開始隨機游走t步到達G上其余節點的轉移概率向量πx(t)；

15) Fory←1 toΝdo

18) Forx←1 toΝdo 18)—21)

19) Fory←1 toΝdo

21) 用式(8)計算G中x與y的相似性Sxy。

1.5 實例計算

斑馬網絡如圖1所示，其平均度為8.222，聚類系數為0.876。網絡26個節點中,度大于11且聚類系數大于0.8的節點有14個，故該網絡是具有局部高聚集程度的網絡。使用斑馬網絡作為網絡實例，用于SRWG算法求解過程的說明。

圖1 斑馬網絡

表1的橫欄和豎欄分別表示斑馬網絡的不同的節點，表內的數據表示計算得到的不同節點之間疊加隨機游走重力模型節點相似性，對角線的數據表示同一個節點與節點之間的相似性，由于本文算法只計算不同節點之間的相似性，故將同一個節點與節點之間的相似性設為0。

表1 疊加隨機游走重力模型節點相似性矩陣S

SRWG算法充分考慮節點的度、聚類系數、節點之間的吸引力等結構特性計算節點之間的相似性。圖1中，節點1與節點15之間比節點16與節點23之間的公共鄰居多且鄰居節點之間的聚集程度大，本文算法得到的疊加隨機游走重力模型節點相似性矩陣S中，節點1與節點15之間相似性S1,15=0.435 7，節點16與節點23之間相似性S16,23=0.096，說明本文方法對具有度和聚類系數均高的節點之間可以進行有效的鏈路預測。

2 實驗

2.1 實驗設計

選取生物網絡、航空網絡、社交網絡等領域中11個具有不同的平均度和聚類系數的真實網絡進行實驗，網絡數據的統計量信息如表2所示。其中，|V|表示網絡的節點數量，|E|表示網絡的邊數量，〈k〉表示網絡的平均度，〈d〉表示網絡的平均最短路徑，C表示網絡的聚類系數，M表示網絡的密度，D表示網絡的直徑。

將SRWG算法與基于局部信息的考慮公共鄰居節點的CN和RA算法、基于局部信息的結合樸素貝葉斯模型的LNBCN和LNBRA算法、基于路徑的LP和Katz算法、基于隨機游走的RWR和SRW算法與基于節點聚類系數的NDCC和TDNCC算法進行預測性能對比，用AUC[18]和Precision[19]指標衡量鏈路預測結果的精確度。使用Matlab作為實驗工具，進行100次獨立實驗，取平均值，將原網絡劃分為訓練集train和測試集test，其中訓練集比例為90%，測試集比例為10%。

表2 11個真實網絡的統計量信息

2.2 AUC和Precision指標分析

將表2中網絡按照節點數量是否大于1 000分成2組，前5個為1組，后6個為1組。圖2表示前5個網絡上各種算法的AUC指標度量情況，圖3表示后6個網絡上各種算法的AUC指標度量情況。圖2和圖3中的對比算法分為2個部分，第1部分是CN、RA、LNBCN、LNBRA、LP和Katz算法與本文算法進行比較，第2部分是RWR、SRW、NDCC和TDNCC算法與本文算法進行比較。圖4表示2組網絡上每種算法的Precision指標度量情況。

圖2 5個網絡上各種算法的AUC

圖3 6個網絡上各種算法的AUC

圖4 11個網絡上各種算法的Precision

圖2、圖3和圖4的坐標下軸表示不同的網絡，上軸表示網絡的聚類系數，左軸表示AUC或Precision指標數值。與其他算法的AUC指標相比，SRWG算法在其中8個網絡上表現最佳，在Metabolic、CE網絡上排名第2、在Wikipediagag網絡上排名第3；基于Precision指標，SRWG算法在其中4個網絡上Precision值最大，表現最佳，在Blogs、USAir網絡上排名第3，在Usairport、Openflights網絡上排名第5，其余網絡上表現較差。

圖2和圖3中，隨著聚類系數的減小，各算法的AUC指標的變化趨勢并不會呈現明顯下降。當聚類系數大幅下降時，預測效果會明顯下降，當聚類系數下降幅度在有限的小范圍內，預測效果會發生波動。當2組網絡中的聚類系數相差不大時，網絡的密度越小，AUC值越大，SRWG算法和基于隨機游走的算法與其他算法相比，AUC值提高較多。

圖2和圖3中，SRWG算法左側圖的折線都在CN、RA、LNBCN、LNBRA、LP和Katz算法的折線上面，右側圖的折線都在NDCC和TDNCC算法的折線上面，但右側圖的SRWG算法與RWR和SRW算法的折線有相交部分。在11個網絡中，SRWG算法較CN、RA、LNBCN、LNBRA、LP、Katz、NDCC、TDNCC算法的AUC指標分別平均提高2.6%、1.4%、2.3%、1.6%、2.1%、1.8%、1.4%和1.2%。相對RWR和SRW算法，SRWG算法對于不同聚集程度的網絡的AUC指標表現各有差異，具體分析如下：

Zebra、Wikipediaxal、Wikipedialo網絡的平均度較高且聚類系數較高，網絡局部具有高聚集程度，SRWG算法與RWR和SRW算法相比分別平均提高了0.9%和0.7%。

雖然USAir、Jazz、Usairport、Openflights、Blogs網絡的平均度較高且聚類系數較高，但網絡整體聚集程度較為均勻，SRWG算法略優于RWR和SRW算法，分別平均提高了0.5%和0.2%。

Metabolic、Wikipediagag網絡的平均度低且聚類系數較高，CE網絡的平均度低且聚類系數低，都不存在局部高聚集程度，網絡整體聚集程度較低，RWR和SRW算法表現最好，相對于SRWG算法分別平均高出0.2%和0.6%。

2.3 度和聚類系數對SRWG算法的AUC指標影響的分析

SRWG算法使用度和聚類系數結合的方式提供節點之間轉移概率的貢獻，將其作為節點的影響力。圖5描述網絡中節點的不同程度的度和聚類系數的分布情況，以及度和聚類系數結合下節點的影響力的分布情況，用于分析網絡節點的不同程度的度和聚類系數對SRWG算法和其他算法的預測效果的影響。按照SRWG算法與RWR和SRW算法之間的AUC指標差異，分3種情況進行分析。

圖5 節點的度數與聚類系數和影響力的關系

圖5(a)中Zebra、Wikipediaxal、Wikipedialo網絡的節點的度和聚類系數主要集中分布在右上部和左下部區域，度高且聚類系數高的節點和度低且聚類系數低的節點較多。這3個網絡節點影響力出現不連續的突然增長的上升趨勢，度高且聚類系數高的節點的影響力極大，且與度低且聚類系數低的節點相比，節點的影響力差異極大，說明網絡中存在很多高聚集程度的節點，所以SRWG算法效果最好。

圖5(b)中USAir、Jazz、Usairport、Openflights、Blogs網絡的節點的度和聚類系數主要集中分布在中部區域，低度且高聚類的節點數和高度且低聚類的節點數相差不多。這5個網絡節點的影響力分布較為分散，呈現均勻的上升趨勢，說明網絡大部分節點的聚集程度較為均勻，所以SRWG算法略優于RWR和SRW算法。

圖5(c)中Metabolic、CE、Wikipediagag網絡的節點的度和聚類系數主要集中分布在左上角區域，度低且聚類系數低的節點和度低且聚類系數高的節點較多，沒有度和聚類系數均高的節點。這3個網絡的節點影響力主要集中分布在左下角區域，節點影響力低，說明網絡沒有高聚集程度的節點且節點的聚集程度均低，所以RWR和SRW算法優于SRWG算法。

另外，對于上述所有情況中的網絡，SRWG算法都優于基于聚類系數的NDCC和TDNCC算法，這說明鄰居節點的聚集程度在計算節點相似性起到很大作用。

綜上所述，SRWG算法與除RWR和SRW算法的其他算法相比，都可以達到最高的預測精度，且對于具有局部高聚集程度的網絡，SRWG算法比RWR和SRW算法表現更好，結果證明SRWG算法是有效的。

3 結論

針對等概率轉移的局部隨機游走的鏈路預測算法忽略網絡結構，不適用于具有局部高聚集程度的網絡的問題，提出一種疊加隨機游走重力模型的鏈路預測算法。該算法充分利用網絡結構信息，體現局部范圍節點之間相互影響對鏈路生成的貢獻。在隨機游走的過程中融合各節點相似性，有效地度量各鄰居節點的轉移概率。最后針對幾組不同聚類系數和平均度的真實網絡進行實驗，結果表明提出的算法能取得更好的預測效果。

本文中研究的鏈路預測方法只考慮了無向無權網絡，接下來的研究主要是能否將該方法擴用到有向有權網絡，從而提高鏈路預測的精確度。