基于圖勾勒的圖鏈路預測方法

尤潔，李勁,2，張賽，李婷

（1. 云南大學 軟件學院，云南 昆明 650091； 2. 云南省軟件工程重點實驗室，云南 昆明 650091）

圖上的鏈路預測是指通過已有的網絡拓撲結構和節點屬性信息等預測網絡中尚未產生連邊的兩個節點之間產生鏈接的可能性，或者是已經產生但是并未發現的鏈接信息，是圖數據挖掘的重要方向之一，受到廣泛的關注。

當前，關于鏈路預測的研究方法主要包括3種：1)基于極大似然估計的方法。該方法將網絡鏈接看作是內在層次的反映，采用極大似然估計進行預測。但該方法的預測準確性與樣本數據量有關，高質量的預測需要大的樣本數據，導致計算復雜度高，不適用于大規模網絡[1-2]；2)基于概率模型方法。通過建立可調參數模型再現網絡的結構和關系特征，將預測問題轉化為預測邊的屬性問題進行預測，此類方法具有較高預測精度，但預測過程中涉及到非普適性的參數和節點屬性信息，使得應用范圍受限，計算復雜度高[3]；3)基于節點相似性預測方法[4-14]。假設節點之間存在鏈接的可能性與節點之間的相似性緊密相關，通過預測節點之間的相似性來進行鏈路預測。其中，基于節點相似性模型的預測方法由于方法簡單，鏈接預測質量較好等成為目前主流的鏈接預測方法。

針對已有研究工作的不足，本文在保證鏈路預測質量的前提下，降低預測算法的計算復雜性角度，提出基于圖勾勒[16]的鏈路預測算法。首先，基于圖勾勒技術對現有的鏈路預測方法進行擴展，定義了基于ADS(all-distances sketches)結構的鏈路預測相似性度量指標，提出了基于圖勾勒的鏈路預測算法，將一般鏈路預測算法的計算復雜度由降低至，其中是ADS勾勒參數，是網絡節點數。其次，基于并行圖計算平臺Spark，提出了ADS的并行計算方法以及基于ADS技術的并行鏈路預測實現方法。從算法運算時間和預測精度兩方面驗證算法的有效性，實驗結果表明：基于ADS技術的鏈路預測算法可以保證一定預測精度，同時降低預測方法的時間復雜度，提升運算效率。

1 背景知識

1.1 鏈路預測

下面分別給出本文中采用的3種節點間相似度度量指標及定義：

定義1Common Neighbor(CN)[5]：如果圖中兩個節點擁有的共同鄰居節點越多，那么這兩個節點就越相似，則它們之間存在或者未來發生鏈接的可能性就越大。相似度定義為

定義2Adamic Adar(AA)[6]：AA在CN的基礎上，賦予鄰居節點權重，它認為共同鄰居節點的節點度對相似度也有影響，共同鄰居節點度越大，它對節點相似度的貢獻越小，反之，共同鄰居節點度越小，它對節點的相似度的貢獻越大。因此在求相似度的公式中，對共同鄰居節點度賦予一個懲罰因子。其相似度定義為

定義 3Resource Allocation(RA)[7]：RA 從資源分配的角度考慮節點相似性。它認為沒有直接相連的兩個節點，資源可以從一個節點傳遞到另一個節點，它們的共同鄰居節點是兩個節點傳遞資源的媒介，每一個媒介都有一個單位的資源，它將自己的資源平均分配給它的鄰居節點，另一個節點接收到的資源數就是這兩個節點的相似度。其相似度定義為

評估指標：鏈路預測結果的衡量指標主要包括Precision(準確率)[17]和AUC(曲線下面積)[18]，Precision針對局部結果進行評估，AUC基于全局進行評估，本文討論的是整體性能，故以AUC作為預測精度的評估標準。AUC的值越高，則鏈路預測整體性能較好。

定義4對于邊集進行數據劃分，有E =，假設是屬于全集，但是不屬于邊集，從中取出一條邊的預測值記為，從中選出一條邊的預測值記為，比較次，若，若，否則不計數，具體如下：

1.2 圖勾勒技術

ADS(all-distances sketches)是定義在圖節點上的數據摘要結構。通過對圖中各節點的可達鄰居節點集進行抽樣，抽樣結果與原節點的集合構成了該節點的Sketch結構。在大圖上，基于ADS可有效進行節點相似關系，中心度等度量計算[16]。v

定義5節點的All-Distances Sketches(ADS)的定義如下[16]：

例1圖的ADS結構如圖1所示，該圖為有向圖帶權圖。節點上的數值為勾勒ADS結構所對應生成的0 ～ 1的隨機數。

圖 1 圖的ADS示例Fig. 1 An illustration of ADS in a graph

圖中每個節點的ADS結構是一個集合。以節點 1 為例，ADS(1)()={(1，0)，(2，8)，(3，9)，(4，18)，(6，18)}表示在圖中隨機值取值情況下，ADS勾勒參數為2時節點1的ADS結構，集合中元素(4，18)表示節點1到節點4的最短距離是18。例如：

2 鏈路預測方法

ADS是對節點的全局鄰居節點進行抽樣，而CN、AA、RA 3種算法的默認情況是基于1跳鄰居進行計算的，故為了排除多跳鄰居對相似度的影響，基于節點的ADS結構的鏈路預測算法中也只考慮一跳鄰居節點?；?跳鄰居的ADS的大小永遠不大于節點的1跳鄰居數，所以在求兩個集合的相似度時，運算量也相應減少。在AA算法和RA算法中還涉及到求共同鄰居節點的度，其他相似性度量指標也涉及到節點中心度的計算等，這個過程中需要耗費大量的計算時間，而ADS抽樣的過程中會過濾掉一部分的鄰居節點，故在一定程度上減少了部分求節點度、中心度的運算量。

對圖勾勒后，得到的ADS結構不再是單一的節點集、邊集所構成的圖數據，而是由節點及其部分鄰居節點構成的集合，這部鄰居節點包括了一跳至多跳另據節點，還帶有相應的可達距離，故ADS需要根據自身結構定義合適的相似性指標，具體定義如下：

定義6基于ADS的CN度量指標(ADS-CN)定義如下：

定義7基于ADS的AA度量指標(ADS-AA)如下：

定義8基于ADS技術擴展的RA度量指標(ADS-RA)定義如下：

公式中符號含義同定義6。

2.1 基于ADS勾勒技術的鏈路預測算法

首先簡要介紹鏈路預測算法的基本思想，鏈路預測算法首先將待預測數據集劃分為訓練集和測試集。找出訓練集中不存在連邊的節點對，得到中不存在連邊的數據集和，并計算節點對的相似度值，隨機從和中各選出一條邊，比較它們的相似度的值，重復多次，根據AUC公式定義，得到預測精度?；贏DS勾勒技術的鏈路預測算法的基本思想：在計算節點對相似度之前，構造出邊集的圖結構，對圖進行ADS勾勒處理，得到中每個節點的ADS結構，根據基于ADS結構定義的相似性度量指標進行鏈路預測。由于節點的ADS是獨立于圖的，這樣帶來的優勢是原圖有些節點發生變化以后，只需要更新變化節點的ADS，帶來的好處是可以獨立動態更新節點的ADS結構，更新代價小；處理后的數據另一個優點是利于并行化處理，每個節點及其ADS結構與其他節點時獨立的，在其他并行框架下，每個節點ADS互不干擾，利于并行。基于ADS勾勒技術的鏈路預測算法的具體描述如算法1。

分析算法1的時間復雜度。首先，由文獻[16]可知，對于圖中的一個節點，的期望大小為其中是從節點出發的可達鄰居節點數，是第i個調和級數，由于()且，所以的期望大小為。于是，基于ADS技術求圖中節點相似度的時間復雜度為。

算法1基于ADS勾勒技術的鏈路預測算法

輸入，預測值比較次數n，勾勒參數K；

輸出AUC值。

1) 切割邊集E為訓練集Er和測試集Ep，；

//找出訓練集中不存在連邊的結點對集合

2.2 基于ADS勾勒技術的并行化鏈路預測算法

為提高鏈路預測算法的執行效率，在算法1基礎上，進一步提出了基于Spark的并行化的鏈路預測算法。該算法具體描述如算法2。算法2的執行過程與算法1一致，但算法2將算法1中的每一步驟采用彈性分布式數據集(RDD)進行了實現?；赗DD表示，采用對RDD的Map-reduce并行化操作有效提升鏈接預測算法的執行效率。RDD轉換和操作細節詳見算法2中的描述。

算法2基于Spark的并行化鏈路預測算法G(V,E)

輸入，預測值比較次數n；

輸出AUC值。

//找出訓練集中不存在連邊的結點對集合

//求出各頂點的鄰居節點

//求出各結點的節點度

//求結點x, y的相似度

3 實驗結果

3.1 實驗環境設置

表 1 實驗數據集拓撲結構信息Table 1 Experimental dataset topology information

本文實驗在USAir97(美國航空網絡數據[17])、Yeast(酵母菌蛋白質相互作用網絡數據[18])、Grid(美國電力網絡數據[19])3個數據集上進行測試，實驗結果主要對鏈路預測算法和基于ADS勾勒技術的鏈路預測算法兩種算法的運行時間和預測精度進行對比分析。實驗環境包括內存：64 GB；處理器：inter(R) Xeon(R) CPU E5-2620 v3 @ 2.40 GHz 2.40 GHz；開發平臺：Intellij IDEA 2016.2.5+Spark GraphX；開發語言：Scala。

本次所有實驗結果均是對數據集進行10次劃分，求平均值，由于程序運行時間存在誤差，故每次劃分結果得到訓練集在運行相關算法的程序時，運行20次求平均值作為劃分一次的數據值。AUC計算公式中的統一取10萬次。

3.2 基于ADS的鏈路預測算法的有效性

ADS勾勒技術是對原數據的一種抽樣方法，通過抽樣達到降低計算復雜度的目的，但是由于它只是對數據的近似勾勒，所以用勾勒的結果進行數據的分析與挖掘，在精度上會有一定的損失，是不可避免的，但是損失一定范圍內的精度，卻提升了較大的計算效率。

3.2.1 兩種算法執行效率

圖 2～4分別給出了 USAir97、Yeast、Grid數據集基于CN、AA、RA3種相似性度量指標的兩種算法的執行效率。從圖中可以看出基于ADS勾勒技術的鏈路預測算法執行時間均低于原鏈路預測算法的執行時間，由于鏈路預測算法不涉及到值得變化，故在值變化過程中結果不改變。而基于圖勾勒技術的鏈路預測算法隨著值的變化算法執行時間有所增加，但是均低于原鏈路預測算法，計算效率提高了約百分之15%～25%，這是由于ADS結構是原數據集的一個抽樣，每個節點的一跳鄰居節點集的數目遠遠小于原圖的一跳鄰居節點集的數目，當值足夠大時，抽樣的結果也只能等于原圖的數據。

圖 2 CN、AA、RA度量指標運行時間對比(USAir97)Fig. 2 CN, AA, RA metrics comparison of run time(USAir97)

3.2.2 兩種算法的預測精度

圖5～7給出了3個數據集在兩種算法下的預測精度，實驗結果顯示，基于ADS的鏈路預測算法的預測精度隨著值的增加而逐漸接近于原鏈路預測算法的精度，數據線最后趨于重合。

圖 3 CN、AA、RA度量指標運行時間對比(Yeast)Fig. 3 CN，AA，RA metrics comparison of run time(Yeast)

圖 4 CN、AA、RA度量指標運行時間對比(Grid)Fig. 4 CN，AA，RA metrics comparison of run time(Grid)

從表1中可以看出USAir97數據集節點遠小于Yeast數據集和Grid數據集，但是圖中結果顯示USAir97數據集較為理想的預測結果對應的值要比其余兩個數據集對應的值要大，這是由于USAir97數據集要比Yeast數據集和Grid數據集稠密，在網絡刻畫中對精度的要求更高，所以相對而言預測結果較為理想的情況下對應的值要大。

圖5和圖6中精度的變化逐漸上升最后趨于穩定，但是圖7中精度的變化有波動，在千分之一上下波動，存在原因可能有兩個：1)計算AUC過程中抽取的次數不夠所造成的誤差；2)ADS節點隨機值變化過程中產生的誤差。

圖 5 CN，AA，RA度量指標AUC對比(USAir97)Fig. 5 Comparison of the CN, AA, RA metrics AUC(USAir97)

圖 6 CN、AA、RA度量指標AUC對比(Yeast)Fig. 6 Comparison of the CN，AA，RA metrics AUC(Yeast)

圖 7 CN、AA、RA度量指標AUC對比(Grid)Fig. 7 comparison of the CN，AA，RA metrics AUC(Grid)

3.3 基于ADS與基于網嵌入的鏈路預測算法對比

DeepWalk[20]是一種基于隨機游動的網絡表示學習方法。通過DeepWalk可獲得圖中節點的向量化表示，進而可基于向量點積進行鏈接預測。在真實圖數據上將本文方法與基于Deep-Walk的鏈接預測方法進行了實驗對比。測試數據為蛋白質交互網絡[21](protein-Protein Interactions)。該數據包括19 706 個節點、390 633條邊。采用CN-ADS與DeepWalk在算法執行時間和AUC值上進行了比較。其中DeepWalk的參數設置為：向量學習模型為Skip-Gram，向量維數設為64。實驗結果如圖8、9所示。從圖8、9結果可知，小值可保證算法執行效率，然而，AUC較DeepWalk差。提高值后，在執行時間仍小于D e e p W a l k的情況下，可顯著改善AUC值。特別地，當＞32后，AUC值優于DeepWalk。對于鏈接預測而言，本文算法在一定條件下優于DeepWalk的結果。

圖 8 PPI數據集上CN-ADS與DeepWalk的時間對比Fig. 8 Time comparison of CN-ADS and DeepWalk on PPI

圖 9 PPI數據集上CN-ADS與DeepWalk的AUC對比Fig. 9 AUC comparison of CN-ADS and DeepWalk on PPI

4 結束語

本文針對大規模網絡數據在鏈路預測中存在時間復雜度高、運算量大等問題，對現有的鏈路預測方法進行擴展，結合現有的圖勾勒技術，提出了基于ADS技術的鏈路預測方法，根據勾勒的結果結合現有的預測方法，定義了基于ADS結構的鏈路預測方法，在算法預測精度和預測時間中取得了較好的折衷，并在真實網絡數據中驗證了算法的有效性。

本文是基于局部信息相似度進行鏈路預測的，更精確的預測方法是基于全局信息進行預測的，如何更好地在圖勾勒技術的基礎上基于全局信息定義預測方法，是將來展開的要點之一。此外，為驗證圖勾勒技術在鏈路預測問題上面的有效性，本文是通過實驗數據進行驗證分析的，缺少嚴謹的理論證明，后續工作將會致力于從理論方面證明圖勾勒技術對鏈路預測的有效性。