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

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

1 引言

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

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

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

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

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

本文針對此問題設計了一種將網(wǎng)絡結(jié)構(gòu)信息和節(jié)點屬性信息統(tǒng)一在一個層次的框架內(nèi)的方法，并給出了針對大規(guī)模網(wǎng)絡的近似計算算法，通過在網(wǎng)絡公開數(shù)據(jù)集上進行的實驗表明該方法相對于其他鏈接預測方法有較為明顯的效果提升。

2 方法

2.1 方法概述

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

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

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

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

Q是全連通網(wǎng)絡H的轉(zhuǎn)移概率矩陣，其元素Qij應體現(xiàn)節(jié)點i和j的屬性相似程度，因此定義如下：

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

2.2 模型簡化與計算

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

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

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

證明如下。對于每一個節(jié)點i：

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

使用矩陣的Neumann級數(shù)展開，得到：

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

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

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

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

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

算法1ARWR計算算法

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

輸出：每一個節(jié)點i游走到網(wǎng)絡中其他節(jié)點的概率π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算法計算出網(wǎng)絡中所有節(jié)點對相似性的時間取決于網(wǎng)絡規(guī)模（N）和針對每一個節(jié)點進行計算的迭代次數(shù)，這與傳統(tǒng)的RWR方法的時間復雜度是一致的[15]，這表明了ARWR算法與原始的RWR算法相比并不會降低運算速度。

3 實驗

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

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

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

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

數(shù)據(jù)集1是具有社會網(wǎng)絡性質(zhì)的合作網(wǎng)絡，僅包含網(wǎng)絡結(jié)構(gòu)數(shù)據(jù)且網(wǎng)絡邊是無方向的。數(shù)據(jù)集2是標準的在線社會網(wǎng)絡，連邊是有方向的，并且其除了好友關(guān)系之外還包括節(jié)點的多種屬性數(shù)據(jù)。這兩個數(shù)據(jù)集涵蓋了各種不同的情況，具有廣泛的代表性。表1總結(jié)了兩個數(shù)據(jù)集的典型網(wǎng)絡特征。

Table1 Network characteristics of datasets表1 實驗數(shù)據(jù)集的網(wǎng)絡特征

3.2 數(shù)據(jù)整理

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

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

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

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

3.3 比較和評價方法

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

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

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

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

（3）RWR，如前所述，該指標僅基于網(wǎng)絡拓撲結(jié)構(gòu)進行隨機游走。

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

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

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

3.4 實驗結(jié)果與分析

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

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

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

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

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

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

4 結(jié)束語

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

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