鏈路預測的方法與發展綜述

(北京信息科技大學 信息與通信工程學院,北京 100101)

復雜網絡能夠很好地描述社會科學、自然科學、管理科學以及工程技術等領域的相互關聯的復雜模型，應用范圍廣泛。其以復雜系統為研究目標，利用數學、統計學、計算機等科學工具，分析和研究事物的本質結構和規律。復雜網絡具有規模龐大、連接結構復雜、節點種類多樣以及網絡演化過程復雜的特點，使得其研究充滿了挑戰。但是，掌握了復雜網絡的演化規律可以幫助人們更好地掌控網絡結構的變化趨勢，因此，吸引了越來越多的人去探索復雜網絡已存在的結構特征及其發展趨勢。

鏈路預測是研究復雜網絡的核心內容之一。在復雜網絡中，個體被稱為節點，節點與節點間的關系稱為鏈接。鏈接的內在機制、形式和結構在不同系統中的演變過程揭示了人類在社會活動中的行為和趨勢[1]。研究鏈接的產生有助于塑造和提高對人類行為和社會網絡的理解，也有助于推進對其他眾多領域的研究，比如社交軟件的好友推薦系統、網絡超鏈接的預測以及股市走向等。準確的鏈路預測為復雜網絡的進化研究工作提供了有力幫助。因此，對復雜網絡中的結構和鏈路進行研究和建模是十分必要的。

本文對節點屬性、網絡拓撲結構、機器學習、最大似然等4類鏈路預測方法進行總結與概括，介紹了各類方法中學者們提出的一些經典算法，對這4種方法的優缺點進行了闡述。對幾種較為常見的評價鏈路預測算法精確度的方法進行了介紹，最后對鏈路預測的未來研究方向和發展前景進行了總結和展望。

1 網絡模型介紹

表1 網絡符號及定義

鏈路預測的定義為：對選定的真實網絡數據集進行處理，將連邊集合E分成訓練集ET和測試集EP兩部分，且訓練集和測試集并無交集。一般隨機選擇邊作為測試集的邊，時序鏈路預測中，會將最近時間內產生的邊作為測試集。利用鏈路預測方法，計算出訓練集中的給定節點對(x,y)的評分數值Sxy，并將評分數值Sxy按大小進行排序，如果節點對的評分數值越大，那么節點間產生鏈接的可能性越大，將得到的預測結果與測試集進行對比得出評價結果，從而得出真實網絡的演化模型并對其進行預測和分析。其具體過程如圖1所示。

圖1 鏈路預測過程描述

鏈路預測的方法基本分為4類：以節點屬性為基礎、以網絡拓撲結構為基礎、以機器學習為基礎以及以最大似然為基礎。基于節點屬性的鏈路預測方法有助于提高預測準確度，但是節點屬性，如姓名、愛好、地理位置等信息難以獲取，而且已獲取信息的時效性和真實性不能確定。與該方法相比較，基于網絡拓撲結構的方法容易獲取網絡結構信息，通過網絡結構，更容易發現哪些節點更傾向于連接或斷開連接。部分學者利用基于機器學習或最大似然等技術更新的鏈路預測方法，與節點屬性、網絡結構等信息相結合，綜合性地對連接關系進行預測，大大提高了鏈路預測的準確程度。

2 鏈路預測方法分類

2.1 基于節點屬性的方法

在早期對鏈路預測的研究中，多數學者采用的是基于節點屬性的鏈路預測方法。兩個節點的屬性，如興趣愛好等越相似，就越容易產生連接。在社交網絡中，最簡單的獲得節點屬性的方法就是使用標簽。卜心怡等人[2]利用微博做出了實證分析，用粉絲數量、微博數量、關注人數、轉發微博數量等作為節點屬性標簽，與基于共同鄰居的算法相結合進行節點連接的預測。Jure等人[3]利用包含超過300億次對話、1.8億節點與13億鏈接的數據集進行了仿真，證明人們更傾向于和相同地區、共同興趣、愛好相似的人建立新連接。利用節點屬性等信息可以提高的預測準確性，但網絡用戶更傾向于保護自己的隱私，信息的獲取變得難度很大，即使成功獲取信息也無法保證其準確性。此外，在獲取信息后，如何提取有用信息也是較為煩瑣的工程。因此，基于節點屬性的鏈路預測方法在實現上具有一定的難度，更多學者傾向于使用以網絡拓撲結構為基礎的方法進行鏈路預測。

2.2 基于網絡拓撲結構的方法

基于網絡拓撲結構的鏈路預測方法的原理為：以網絡結構的相似性為基礎，判別節點的相似性，兩個節點的結構越相似，那么它們之間越可能產生連接。以網絡拓撲結構為研究基礎的鏈路預測方法，可以分為3種研究方向：以局部信息、路徑和隨機游走為基礎。

解決鏈接預測問題最有效的方法是建立相似性指標。不同的鏈路預測方法主要區別之一即是相似性指標的不同。相似性指標是定義網絡節點之間相似性的評分函數，根據該函數對網絡中所有的節點，兩兩計算相應的評分數值。

2.2.1 基于局部信息的方法

在基于局部信息的鏈路預測方法中，最基本的是共同鄰居(Common Neighbor，CN)指標。CN評價指標代表了兩個節點間共同鄰居的多少。如果其數目越多，這兩個節點越可能進行連接。除此之外，CN評價指標還有很多基于鄰居其他屬性的評價方式：Salton指標[4]、Jaccard指標、Sorensen指標、LHN-I指標等，如表2所示，分別利用了共同鄰居、鄰居的并集以及節點的度屬性等。另外，Adamic和Adar還提出了AA指標，其主要考慮節點對共同鄰居的重要程度不同，從而通過共同鄰居的度來突出這一特點。Zhou等人[5]對9種基于局部性的指標進行了準確性對比，并提出了準確度更高的資源分配(Resource Allocation，RA)指標。大量的實驗結果顯示，RA指標與AA指標的表現相近，但在準確性上略微高于AA指標。

表2 相似性指標及其定義公式

2.2.2 基于路徑的方法

基于路徑的相似性指標有3種不同的研究方向，局部路徑(Local Paths，LP)指標、LHZ-II指標以及Katz指標。

CN指標可以看作是考慮兩個節點間的二階路徑數目，LP指標在CN指標的基礎上進行了改進，在二階路徑的基礎上再考慮三階路徑數目。當考慮的階數越來越多，趨近于無窮時，這一指標的計算公式就相當于Katz指標了，與LP指標相比，Katz指標的計算復雜度也成倍增高。Leicht等人提出了基于自相似度矩陣的LHZ-II指標，表示如果兩個節點是相似的，它們在網絡中的鄰居也相似，那么它們建立連接的可能性較大。LHZ-II指標可以使用網絡的鄰接矩陣關系，進行多次迭代遍歷網絡中所有節點的相互關系，進行鏈路預測。

2.2.3 基于隨機游走的方法

基于隨機游走的指標，比如Cos+指標、重新開始的隨機游走指標(Random Walk with Restart,RWR)以及Sim Rank指標等。

Fouss等人基于馬爾科夫隨機游走模型，通過計算平均通勤時間等信息，為節點對之間的鏈接定義Cos+相似性指標。實驗結果表明，該算法在Mivieles數據集上表現良好，但不能很好地應用于大型數據集。張學佩[6]定義了局部隨機游走的節點相似度指標，并與其他相似性指標進行比較。結果表明，其提出的算法具有更低的計算復雜度。Jeh等人認為，如果兩個節點的鄰居節點相似，則它們是相似的，并據此提出了Sim Rank指標。

2.3 基于機器學習的方法

現有的鏈路預測方法除了以相似性為研究基礎，還有基于機器學習的方法，主要分為三大類：特征分類、概率模型以及矩陣分解。基于機器學習的算法有助于解決數據挖掘中的常見問題，例如類別不平衡，過度擬合等。

在基于特征分類的鏈路預測算法方面，很多學者使用監督學習中一些較為常用的算法，比如支持向量機、決策樹、徑向基網絡、神經網絡[7]等，對未知鏈接進行預測，其中預測精度最高的是支持向量機方法。Li等人[8]將快速分類法應用于支持向量機，對分類器進行訓練，把大部分預測過程中測試階段傳遞到訓練階段，大大減少了預測階段的時間復雜度。Yuan等人[9]提取推特中用戶的情感信息，通過分析情感特征來判斷兩個用戶是否可能成為好友。實驗結果表明，提出的模型優于Logistic分類器和隨機森林。

基于概率模型的鏈路預測算法的主要思想為，首先建立一個可以調整參數的可預測模型，然后在調整參數的過程中找到使模型達到最優的參數值，可令模型的預測準確度達到最高。構建概率模型的方法主要有馬爾科夫網絡關系模型以及貝葉斯網絡模型等。Liben等人[10]首先利用機器學習的方法進行了鏈路預測，且預測準確度較高。Asil等人[11]使用監督學習的方法進行鏈路預測，并證明多數情況下，加權網絡比未加權網絡在監督和非監督方法中都有更好的預測結果。Gupta等人[12]將鏈路預測問題視為二元分類問題，應用貝葉斯分類來預測網絡中缺失的鏈接。基于概率模型的鏈路預測研究可以擴展到包括社交網絡分析在內的各個領域，可以用來發現生物學中蛋白質的相互作用[19]，幫助建立電子社交網絡中的推薦系統[13]，還可以識別出社交網絡中隱藏的連接。

在基于矩陣分解的鏈路預測算法，Menon等人[15]提出了一個擴展矩陣分解的模型來解決有向網絡中的鏈路預測問題，并在實驗中證明，顯式特征通常能夠提供比隱式特征更好地鏈路預測結果，但兩者結合可以更好地提高預測性能。郭麗媛[16]提出用集體矩陣分解方法將可用的鏈接信息從相對密集的交互網絡轉移到稀疏的目標網絡，通過網絡相似性來建立源網絡和目標網絡之間的對應關系。Ahmed等人[17]針對動態圖中的鏈路預測問題，提出了一種基于非負矩陣分解的方法，該方法從動態網絡的時間和拓撲結構中學習潛在特征，可以獲得更高的預測結果。該方法應用新的迭代規則構造具有重要網絡特征的矩陣因子，并證明了算法的收斂性和正確性。

2.4 基于最大似然的方法

基于最大似然的鏈路預測方法的基本思路是：根據目前已經觀測到的網絡中的鏈路計算網絡的似然值，并假設真實網絡的似然值最大，最后根據網絡似然最大化，計算所有未連接節點間的連邊概率。以網絡結構為研究基礎的最大似然估計方法較為適用于具有組合結構的網絡類型。

2008年，Clauset等人提出一種通過網絡數據推斷網絡層級結構的方法，證明層次結構可以用來預測網絡中丟失的鏈接，并具有較高的精確度。劉繼嘉[18]提出了一個擴展的經典隨機塊模型，預測了網絡中的丟失鏈接和錯誤鏈接。田甜等人[19]提出了一種基于最大似然估計的層次隨機圖模型，利用腦網絡數據建立層級隨機圖，通過改進的馬爾科夫蒙特卡洛算法對樹狀圖空間進行采樣，最后計算腦網絡邊的平均連接概率，實驗驗證，該算法比傳統的算法計算復雜度低。

3 衡量算法精確度

衡量鏈路預測算法準確度的指標最常用的有3種：AUC(Area Under ROC Curve，ROC曲線下面積)、Precision和Ranking Score。

3.1 AUC

AUC的評價方式為：每次從測試集EP中隨機選取一條邊，再隨機從不存在的邊的集合中選取一條邊，對兩者的評分數值Sij進行比較，若測試集中的邊分數高，則記1分，若兩者相等，記0.5分。假定一共比較n次，其中有n′次測試集分數高，有n″次兩者分數相同，則AUC計算值為

(1)

3.2 Precision

在鏈路預測完成后，需要對所有的邊計算的評分數值由高到低排序，而Precision計算的是排在前L位的邊中，預測正確的邊所占比例，即如果在預測后的排序結果中，排在前L位的邊有m個與測試集中的邊相同，那么Precision的計算值為

(2)

當兩個鏈路預測方法的AUC值相同時，用Precision比較其準確性，Precision值越大，越傾向于把連邊準確的節點對排在前面。

3.3 Ranking Score

(3)

4 結束語

綜上所述，無論是通過節點屬性、網絡拓撲，還是基于概率模型，都是通過已知的數據，盡可能貼近實際情況刻畫鏈路的連接走向，但它們各自有優缺點。基于節點屬性的預測方法通過獲取用戶信息來確定連接關系，但無法確定用戶信息的真實性和準確性，深入挖掘又涉及用戶的隱私問題，單從這一方面進行預測，準確率難以保證。通過網絡拓撲來進行預測，計算復雜度比較低，只通過網絡結構預測鏈路需要獲取的數據較為簡單。機器學習是最近較為熱門的方向，與鏈路預測相結合會得到更高的預測準確率。概率模型是數據挖掘的傳統模型，它同時考慮了節點屬性和網絡結構，能夠得到較好的準確度，可是計算復雜度和用戶屬性的獲取都是它無法大規模進行采用實施的原因。

目前，鏈路預測廣泛應用于生物系統、社交關系、推薦好友方式、股市走向等方面，已經成為一門熱門的交叉學科。如何在不侵犯用戶隱私、計算復雜度低的條件下設計出快速、準確的鏈路預測模型，從而應用于大規模復雜網絡上，是接下來要繼續攻克的難題。