融合網絡結構和節點屬性的鏈接預測方法*

張 昱，高克寧，陳 默，于 戈

東北大學 計算機科學與工程學院，沈陽 110819

1 引言

近年來，鏈接預測作為社會網絡研究的一個基本問題一直都是網絡研究的重點。早期的鏈接預測研究方法集中于利用網絡結構信息計算出網絡中兩個節點間的相似性[1-3]，以相似性的度量值來確定節點間能否產生鏈接的概率，從而達到預測的目的。共同鄰居數（common neighbors，CN）即是其中一種典型方法，即通過兩個節點所擁有的共同鄰居數量來預測兩者建立鏈接的可能性，共同鄰居越多，兩者建立聯系的可能性就越大。共同鄰居數具有計算簡單且效果好的優點，一直是鏈接預測方法的基準指標。此外，還有很多類似的根據網絡結構計算節點相似性的方法，如Adamic-Adar（AA）[4]、Katz[5]等。

社會學的研究表明，網絡中的兩個節點既可能因為在網絡結構上相近而產生聯系，也可能因為兩者屬性相似而產生聯系。隨著信息社會網絡的發展，越來越多的網絡數據包含了大量的節點屬性信息，這給社會網絡鏈接預測的研究帶來了很大的機遇和挑戰。傳統的基于網絡結構的方法大都忽略或弱化了節點的屬性信息，而近年來不少研究都表明這些屬性信息對于網絡的鏈接預測效果有明顯提升[6-10]。但如何將網絡結構信息和節點屬性信息有效地結合起來用于鏈接預測一直是一個研究的難題。

傳統的計算節點相似性方法中，RWR（random walk with restart）方法[11]具有較好的預測效果。RWR方法本質上是PageRank算法的變形，其假設在一個具有N個節點的網絡中，一個隨機游走粒子從節點i出發，并在每走一步時都以一定的概率返回初始位置，其更新規則如下：

其中，向量πi是一個N×1的向量，每一個元素πi,j都表示節點i到j的可能性度量值；P是概率轉移矩陣，P的元素Pij表示節點i到j的轉移概率，這里實際上就是經過歸一化的網絡權值矩陣；ei也是N×1的向量，表示初始態，只有第i個元素為1，其他元素為0；d是一個常數，它的取值實際上是收斂性和有效性的一個折中，d越小收斂速度越快，但收斂值的意義也越小。最終πi的收斂值即是節點i到其他節點的相似性度量值，也就是它們是否形成鏈接的概率值。

RWR方法相對于其他相似性度量方法有一個天然的優勢，即轉移概率矩陣P實際上是由網絡的邊權生成的。如果僅僅知道網絡結構，那邊權只能平均分配，即每一個節點游走到它的任意一個鄰居節點的概率是相等的。如果網絡數據中還包含節點的屬性信息，那就可以將兩個相鄰節點的屬性映射成兩個節點連邊的邊權重，這樣就保證了游走粒子更傾向于游走到與當前節點屬性上更相似的鄰居節點上。如此，網絡結構信息和節點屬性信息就在RWR方法的框架下自然地統一在一起用于鏈接預測。文獻[7]采用此方法并通過優化算法學習出網絡邊權重，取得了較好的效果。但是，此類傳統的RWR方法有一個固有的缺陷，就是隨機游走被限制在網絡拓撲結構上。例如，兩個在網絡中不連通的節點，其節點屬性相似度很高，在實際上是有可能組成新的連邊，但應用傳統RWR的方法則無法預測出來。

本文針對此問題設計了一種將網絡結構信息和節點屬性信息統一在一個層次的框架內的方法，并給出了針對大規模網絡的近似計算算法，通過在網絡公開數據集上進行的實驗表明該方法相對于其他鏈接預測方法有較為明顯的效果提升。

2 方法

2.1 方法概述

社會網絡圖可由G=(V,E)表示，其中V和E分別為網絡的節點集合和邊集合。對于每個節點i∈V，都帶有一個屬性向量，表示為xi。本文的目標就是利用這些輸入設計一個新的基于RWR方法的鏈接預測框架。

本文方法結合了兩種鏈接預測的基本假設：（1）兩個節點在網絡拓撲中的聯系越“近”，兩者越有可能產生鏈接；（2）兩個節點的屬性越相似，兩者越有可能產生鏈接。本文提出的方法是基于屬性相似性的隨機游走方法，簡稱為“ARWR（attributed random walk with restart）”。基于假設（2），如果兩個節點的屬性相似，即使它們在網絡上的“距離”遠，也可能產生鏈接。因此，ARWR方法將網絡虛擬成為一個全聯通圖H，這樣對于隨機游走粒子而言，它在每一步游走過程中，都有機會走向任意一個節點，而不是像傳統的RWR方法只能走向網絡上與其相鄰的節點。文獻[12]提出了將節點屬性也當成網絡中的節點，從而將節點屬性融合到網絡中再采用隨機游走的方式進行鏈接預測。文獻[13]則提出了類似的計算含屬性網絡的PageRank值方法，將網絡分解成原始社會網絡無權圖G和帶有屬性權重的全聯通網絡H，并使隨機游走粒子同時在兩個網絡中游走。本文與上述文獻不同之處是在不增加網絡節點數量的條件下融合了節點屬性信息，并且隨機游走粒子按照傳統RWR方法每走一步都可能以一定的概率返回出發點，最終給出了面向鏈接預測問題的實驗結果。

為了簡化問題，可以將ARWR方法理解為隨機游走粒子在每一步行動中，既有機會按照傳統的RWR形式在原始只有網絡拓撲結構信息的網絡G中移動，也有可能在只包括屬性相似度信息的全聯通的網絡H中移動。G的轉移概率矩陣P維持不變，而H的轉移概率矩陣Q則是通過節點間的屬性相似度生成的權值矩陣。因此ARWR的更新規則可調整為：

其中，α和β分別表示粒子在G和H中游走的可能性。P為網絡圖G的轉移概率矩陣，按傳統的定義，每一個粒子都有均等的機會移動到它的鄰居節點。

Q是全連通網絡H的轉移概率矩陣，其元素Qij應體現節點i和j的屬性相似程度，因此定義如下：

其中，sij表示節點i和j的屬性相似度，對其進行標準化處理，使得每個節點上的粒子向其他節點游走的概率總和為1。如果已知兩個節點i和j的屬性向量，則衡量它們的屬性相似度有多種方法，本文采用了皮爾遜相關系數，sij的范圍從-1到+1，數值越大說明i和j的相似性越高，本文采用了一個映射函數f(x)=(x+1)/2將該系數的范圍映射至[0,1]。本文還嘗試了其他若干種標準的相似性度量方法，如歐氏距離、余弦相似度等，結果發現對最終的鏈接預測效果影響非常小。因此，本文僅采用皮爾遜相關系數報告最終的結果。

2.2 模型簡化與計算

首先，α和β的選擇對預測結果至關重要，它們分別表示游走粒子在G和H上游走的概率，同時也表示著網絡結構和節點屬性這兩類不同的信息對鏈接形成的貢獻程度。然而，各種實際的社會網絡千差萬別，并且實際采集到的數據也不同，因此很難確定究竟是網絡結構還是節點屬性對鏈接預測的結果影響更大，也很難度量它們各自的影響程度。因此，也就很難確定出α和β的比例。此外，游走粒子在每一步返回初始節點的概率θ=1-α-β同樣需要 確定。

為簡化模型，首先選擇固定的返回概率θ。在PageRank和RWR的很多經典文獻中都給出θ=0.15[11,14]的取值，它代表著RWR方法在收斂速度和收斂結果有效性上的折中，本文的實驗也采用這個取值計算并給出結果。一旦θ確定，因為α+β=1-θ，所以可表示β=1-θ-α。

為實現快速的計算，本文對式（2）進行進一步的簡化。首先定義一個N維向量r，其元素ri定義為：

證明如下。對于每一個節點i：

如前所述，α和β的比例無法確定，因此將其當成隨機變量來處理并建立它們的概率分布模型。最終ARWR將計算基于α和β的分布的π的期望E(π)作為節點間的鏈接可能性度量結果。對上式整理后得到其穩態解為：

使用矩陣的Neumann級數展開，得到：

于是得到πi的期望，寫成：

由上式可看出，為計算這個E(πi)，需要計算兩個分量各自從0到∞的和。于是可做如下處理：

因為P、r、ei都是非負的量，而α則是(0,1-θ)之間的一個隨機量，這就保證了上式的所有分項都是非負的，所以可通過循環累加的方式計算E(πi)的近似值，即：

接下來就是為α選擇一個合適的概率分布模型，但關于此參數并沒有任何先驗知識，因此本文在實驗中首先假設α為一固定值，然后分別測試不同的α取值并根據測試結果選擇合適的概率分布，概率分布確定后即可計算E(αk)的值代入獲得E(πi)的結果。本文將在實驗環節對α取值做進一步分析。

至此，本文方法敘述完畢，下面用一個完整的偽代碼算法描述將上述方法整合在一起。

算法1ARWR計算算法

輸入：圖G=(V,E)，其中每一個節點i∈V都有一個屬性向量xi，隨機游走粒子的返回概率θ、α具有確定的概率分布，以及收斂容差ε。

輸出：每一個節點i游走到網絡中其他節點的概率πi。

1.標準化所有的屬性向量xi；

2.利用式（5）生成r；

3.利用式（3）生成P；

4.ρA=(1-θ-E(α))r

5.ρB=θei

6.π=ρA+ρB

7.k=1

8.whileρ＞εdo

11.π=π+ρA+ρB

12.k=k+1

13.end while

由算法的偽代碼可知，P和r均為一次性計算，在P和r固定的情況下，算法中的每一次迭代中主要的計算消耗為PρA，其計算的時間復雜度為O(N)。因此，使用ARWR算法計算出網絡中所有節點對相似性的時間取決于網絡規模（N）和針對每一個節點進行計算的迭代次數，這與傳統的RWR方法的時間復雜度是一致的[15]，這表明了ARWR算法與原始的RWR算法相比并不會降低運算速度。

3 實驗

3.1 實驗數據集

為了測試本文方法的適應性和有效性，選取了兩種不同類型的數據集。數據集均從斯坦福大學的網絡數據網站（http://snap.stanford.edu/data/）下載，是在社會網絡研究中使用廣泛的公開數據集。

數據集1（CA-HepPh）此數據集為一個論文合作網絡，涵蓋了1993年1月至2003年4月間高能物理某領域的論文數據。數據集中，每個節點表示一個論文作者，如果作者i和作者j至少有1篇共同署名的論文，則i和j之間產生一條無向邊。

數據集2（soc-Pokec）Pokec是斯洛伐克的一個非常流行的在線社交網絡。此數據集包含該網絡的帶方向的好友關系以及用戶的多種屬性信息，如性別、年齡、愛好等。

數據集1是具有社會網絡性質的合作網絡，僅包含網絡結構數據且網絡邊是無方向的。數據集2是標準的在線社會網絡，連邊是有方向的，并且其除了好友關系之外還包括節點的多種屬性數據。這兩個數據集涵蓋了各種不同的情況，具有廣泛的代表性。表1總結了兩個數據集的典型網絡特征。

Table1 Network characteristics of datasets表1 實驗數據集的網絡特征

3.2 數據整理

數據集1是無向圖，為了使用本文算法，將其看成是有向圖，即將每一條無向邊轉換為兩條方向相對的有向邊。在數據集1中，只有網絡結構信息，即節點間的好友關系，并不包括節點的屬性信息。但在實際應用中，可以從網絡結構信息中提取出節點的屬性信息，這部分基于結構的屬性信息實際上對鏈接預測有很大幫助。因為最終基于RWR方法的隨機游走雖然是基于網絡結構的方法，但是其遵循的是一階馬爾可夫模型，而網絡結構中的更高階的信息被掩蓋了。因此，將更多的這類網絡結構信息轉換成節點的屬性信息即可更好地服務于鏈接預測模型。

使用網絡拓撲結構信息提取屬性相似度不能按照計算兩者屬性向量相似度的方式進行。例如，兩個節點的度數都很大并不能說明兩者可能產生鏈接。因此本文針對數據集1選取了能夠表示出節點間結構相似性的若干個度量指標用于計算sij，包括：（1）共同好友數；（2）2-hop共同好友數；（3）3-hop共同好友數。為避免上述的屬性值過大，計算時均進行了歸一化處理，之后再對各指標進行加和形成節點的相似性取值sij。

數據集2本身包含節點的自然屬性信息，為驗證屬性信息對鏈接形成的影響，本文選取了其中5種有代表性的可用于度量節點相似性的屬性：（1）年齡；（2）所在地區；（3）工作領域；（4）所講語言；（5）愛好。

由于數據集2的數據量過大且屬性信息不全，本文從該數據集中選取了屬性信息完整并度數大于10的節點形成了一個子集用于實驗。上述屬性中只有年齡為數值型數據，做歸一化處理即可；其他屬性為非數值型離散數據，在計算屬性向量相似度時，先對其進行one-hot code方式的編碼，再采用皮爾遜相關系數計算節點間的屬性相似度。

3.3 比較和評價方法

本文使用如下4種鏈接預測指標與本文提出的方法進行比較。

（1）共同鄰居數（CN），此指標為鏈接預測領域的基準指標。

（2）AA，該指標最早提出時用作度量兩個網頁間的相似性[4]，表示為：

此處N表示節點的好友集合，這個指標的基本思想是兩個節點的共同好友對于兩節點建立鏈接的支持程度不同，其中度數較大的好友對建立鏈接的支持度被削弱。

（3）RWR，如前所述，該指標僅基于網絡拓撲結構進行隨機游走。

（4）RWRW（RWR on weighted network），這是將屬性相似性信息與網絡結構信息相結合的最基本的方法，使用節點間屬性相似度作為其邊權值，隨機游走則按照邊權形成的概率進行。

鏈接預測的評價采用的是標準AUC（area under curve）值，簡述如下：將網絡數據集分成訓練集和驗證集，首先隨機取出網絡中10%的鏈接作為有鏈接的驗證集，余下的含有原始網絡90%鏈接的網絡作為訓練集，此外從無鏈接節點對中隨機取出與有鏈接驗證集等量的節點對作為無鏈接驗證集。分別計算兩個驗證集中的各節點對在訓練集網絡上的各個度量指標（5種），得出各類度量值的AUC值以比較預測結果。AUC值的計算方法如下：

從鏈接集合與非鏈接集合中隨機取出鏈接進行測試，比較其在訓練數據集上各度量指標的值，實驗共重復n次，n′表示鏈接集的分值高于非鏈接集分值的次數，n″表示兩者相等的次數，最終得到AUC分值作為此類鏈接預測方法的評估值。

3.4 實驗結果與分析

本文方法將參數α當作隨機變量來處理，在沒有任何先驗知識的情況下，最合理的假設是α服從[0,θ]間的均勻分布。但為了分析不同數據集下采用不同α的實際效果，實驗中除了設α服從[0,0.85]間的均勻分布外，還對α取[0,θ]間的多個固定取值，步長為0.1，針對兩種不同的數據集，得到AUC預測結果，如圖1所示。

Fig.1 Performance of link prediction with different parametersα圖1 參數α在不同取值下的鏈接預測效果

首先，由圖1可知，不同數據集下α的最優取值并不相同，這也說明了在不同的網絡中，鏈接形成的機制十分復雜，不是由網絡結構或是節點屬性獨立決定的；其次，將α看成服從均勻分布并不能保證得到最優的結果，α在不同類型網絡下的分布還有待進一步大量的實驗分析；最后，從本文的兩種實驗數據集的結果觀察可知，α偏大更有可能取得較好的預測效果，說明網絡結構信息對鏈接預測的影響還是非常大。但當α達到最大時（如圖中α=0.8），預測的效果有一定程度的降低，說明節點屬性信息對提高預測效果是有幫助的。

實驗選取了圖1中的最優AUC值作為本文方法的最終預測結果，與其他4種預測指標進行比較，結果如表2所示。

Table 2 AUC comparison of different methods表2 不同方法的AUC比較

這個結果表明本文方法可以有效地利用節點的屬性信息提高鏈接預測的效果。

4 結束語

社會網絡中大量的節點屬性信息可以與網絡結構信息相結合用于網絡的鏈接預測已經成為研究者的共識，本文基于此構建了一種基于隨機游走的方法進行鏈接預測，并將節點的屬性相似度信息融合進網絡中參與隨機游走過程，并給出了一種可適用于大規模網絡計算的近似算法。最后在不同的數據集上進行了方法的驗證，實驗表明此方法可有效地提高鏈接預測的效果。

未來尚有兩個問題需要進一步研究和實驗：一是如何針對不同類型的網絡，快速地找到參數α的最優值，從而提高鏈接預測的精確度；二是借鑒其他的研究成果[16-17]，采用更有效的機器學習模型得到節點間的屬性相似度，從而建立更為精確的轉移概率矩陣。