基于網(wǎng)絡表示學習與隨機游走的鏈路預測算法

劉 思，劉 海，2，陳啟買，賀超波

(1.華南師范大學 計算機學院，廣州 510631； 2.廣東省高性能計算重點實驗室，廣州 510033；3.仲愷農(nóng)業(yè)工程學院 信息科學與技術學院，廣州 510225)

(*通信作者電子郵箱liuhai@m.scnu.edu.cn)

基于網(wǎng)絡表示學習與隨機游走的鏈路預測算法

劉 思1，劉 海1，2*，陳啟買1，賀超波3

(1.華南師范大學 計算機學院，廣州 510631； 2.廣東省高性能計算重點實驗室，廣州 510033；3.仲愷農(nóng)業(yè)工程學院 信息科學與技術學院，廣州 510225)

(*通信作者電子郵箱liuhai@m.scnu.edu.cn)

現(xiàn)有的基于隨機游走鏈路預測指標在無權網(wǎng)絡上的轉移過程存在較強隨機性，沒有考慮在網(wǎng)絡結構上不同鄰居節(jié)點間的相似性對轉移概率的作用。針對此問題，提出一種基于網(wǎng)絡表示學習與隨機游走的鏈路預測算法。首先，通過基于深度學習的網(wǎng)絡表示學習算法——DeepWalk學習網(wǎng)絡節(jié)點的潛在結構特征，將網(wǎng)絡中的各節(jié)點表征到低維向量空間；然后，在重啟隨機游走(RWR)和局部隨機游走(LRW)算法的隨機游走過程中融合各鄰居節(jié)點在向量空間上的相似性，重新定義出鄰居節(jié)點間的轉移概率；最后，在5個真實數(shù)據(jù)集上進行大量實驗驗證。實驗結果表明：相比8種具有代表性的基于網(wǎng)絡結構的鏈路預測基準算法，所提算法鏈路預測結果的AUC值均有提升，最高達3.34%。

鏈路預測；相似性；重啟隨機游走；局部隨機游走；網(wǎng)絡表示學習

0 引言

現(xiàn)實世界中存在大量的復雜系統(tǒng)都可以通過網(wǎng)絡形式來體現(xiàn)，其節(jié)點代表真實系統(tǒng)中不同的實體，連邊代表實體間的聯(lián)系。鏈路預測是指通過已知的網(wǎng)絡結構和屬性等信息,預測網(wǎng)絡中尚未產(chǎn)生連接的兩個節(jié)點間產(chǎn)生連接的可能性[1]。鏈路預測在復雜網(wǎng)絡和信息科學之間起著重要的橋梁作用，對于鏈路預測研究具有重要的理論價值與實際應用。理論上，它可以幫助人們很好地理解復雜網(wǎng)絡的演化機制[2]；在實際應用方面，它可以在生物網(wǎng)絡中揭示隱含的相互作用關系以指導實驗，在社交網(wǎng)絡中推薦用戶最可能認識的好友，還可以在電子商務中推薦顧客個性化的商品等。近年來，關于復雜網(wǎng)絡中鏈路預測的研究越來越受到國內(nèi)外學者的廣泛關注[3]。

鏈路預測最直觀的假設是，如果兩個節(jié)點之間越相似，它們之間最有可能產(chǎn)生連邊。基于這種假設，鏈路預測的基本問題是如何刻畫和計算節(jié)點之間的相似性。目前，主要存在如下刻畫節(jié)點相似性的方法。

1)基于節(jié)點屬性的鏈路預測方法，其主要是利用節(jié)點的外部屬性和標簽信息來刻畫節(jié)點之間的相似性。例如，如果兩人之間具有相同的學校、工作和興趣，則可以認為他們之間存在較高的相似性。雖然應用節(jié)點屬性等信息可以取得不錯的預測效果，但在很多情況下，節(jié)點的屬性信息不易獲取且伴有較多噪聲，導致無法保證信息的可靠性，同時對于如何甄別哪些屬性對于特定的鏈路預測場景是有效的以及多大程度有效也是一個重要問題。

2)基于網(wǎng)絡結構的鏈路預測方法。近年來，該方法得到了越來越多的關注[3]。相對于節(jié)點屬性而言，網(wǎng)絡結構信息的獲取較容易且更可靠，同時對于結構相似的網(wǎng)絡具有較高的適用性。預測精確度的高低很大程度上取決于能否很好地選取網(wǎng)絡結構特征。當前存在很多基于網(wǎng)絡結構相似性的鏈路預測指標，其中，基于局部信息的相似性指標主要包括共同鄰居指標(Common Neighbors, CN)、Salton指標、Jaccard指標[4]、Sorenson指標、大度節(jié)點有利指標(Hub Promoted Index, HPI)、大度節(jié)點不利指標(Hub Depressed Index, HDI)、LHN-Ⅰ指標、Adamic-Adar指標[5]、資源分配(Resource Allocation, RA)指標和優(yōu)先偏好(Preferential Attachment, PA)[6]指標等。基于路徑的相似性指標主要包括局部路徑(Local Path, LP)指標[7-8]、Katz指標[9]和LHN-Ⅱ(Leicht-Holme-Newman-Ⅱ)指標[10]。基于隨機游走的相似性指標包括平均通勤時間(Average Commute Time, ACT)[11]、基于隨機游走的余弦相似性(Cos+)指標、有重啟的隨機游走(Random Walk with Restart, RWR)指標[12]、SimRank(SimR)指標、局部隨機游走(Local Random Walk, LRW)指標[13]和有疊加效應的局部隨機游走(Superposed Random Walk, SRW)指標[13]。呂琳媛[1]在一些真實的網(wǎng)絡數(shù)據(jù)集上進行實驗并總結對比了上述各種基于網(wǎng)絡結構相似性指標的預測結果，發(fā)現(xiàn)基于隨機游走的相似性指標具有更高的準確性，尤其是基于局部隨機游走的相似性指標具有更低的計算復雜度和更高的預測精確度。

3)基于網(wǎng)絡結構和節(jié)點屬性融合的鏈路預測方法，其綜合考慮了節(jié)點的屬性和網(wǎng)絡結構信息來刻畫節(jié)點之間的相似性。Cherry等[14]在社交網(wǎng)絡Twitter中抽取出用戶不同類型的屬性信息和多種網(wǎng)絡結構特征，對用戶間的聯(lián)系強度和社交關系建模，最后用于刻畫用戶之間的相似度來提高鏈路預測的效果。

網(wǎng)絡表示學習是指對網(wǎng)絡特征進行學習，用低維向量表示網(wǎng)絡節(jié)點[15]。近幾年，深度學習在特征表示學習上取得了巨大的進展[16]。在自然語言處理領域中，以基于深度學習的Word2vec模型[17]為代表的模型在詞向量表示方面取得了很好的效果，從而啟發(fā)了大家應用深度學習在網(wǎng)絡表示學習方面的研究。目前這方面的研究也取得了一些較大的進展，其中一個最具有代表性的基于深度學習的模型是DeepWalk[18]，它正是基于當前最流行的詞向量表示模型Word2vec。DeepWalk能夠很好地學習網(wǎng)絡結構特征，將網(wǎng)絡中的每個節(jié)點用一定維度的連續(xù)向量表征出來，同時能夠很好地捕捉網(wǎng)絡鄰居節(jié)點的相似性以及社區(qū)關系。

現(xiàn)有的基于隨機游走的鏈路預測方法，在未知網(wǎng)絡節(jié)點屬性與權重信息的情形下，鄰居節(jié)點間的轉移過程僅考慮了節(jié)點度之類的局部信息，具有一定的盲目性。例如，基于重啟隨機游走和基于局部隨機游走的鏈路預測指標僅考慮了節(jié)點度進行隨機轉移。為此，本文在基于隨機游走的相似性指標基礎上，利用網(wǎng)絡表示學習方法DeepWalk學習網(wǎng)絡各節(jié)點的潛在網(wǎng)絡結構特征，將其表征到低維向量空間中，并通過各節(jié)點在向量空間上的相似性來度量各節(jié)點在潛在網(wǎng)絡結構特征上的相似性，旨在隨機游走的轉移過程中融合各節(jié)點間的潛在網(wǎng)絡結構相似性，有效地度量各鄰居節(jié)點間的轉移概率。最后通過與眾鏈路預測基準算法進行實驗對比，結果顯示本文提出的鏈路預測算法能取得很好的預測效果。

1 相關工作

1.1 重啟隨機游走指標

重啟隨機游走(RWR)指標可以看作是PageRank算法[19]在鏈路預測問題上的拓展應用，其基本思想是假設隨機游走粒子在網(wǎng)絡上某個節(jié)點位置開始運動，每游走到一個節(jié)點時，都能以一定的概率返回初始節(jié)點。

假設隨機游走粒子轉移到任意鄰居節(jié)點的概率為α，返回初始節(jié)點的概率為1-α。P為概率轉移矩陣，其元素Pxy=axy/kx表示粒子從節(jié)點x游走到節(jié)點y的概率。其中：如果x和y之間相連，則αxy=1，否則αxy=0；kx表示節(jié)點x的度。若粒子在初始時刻位于節(jié)點x處，則在t+1時刻粒子轉移到網(wǎng)絡上各節(jié)點的概率向量為：

Dx(t+1)=α·PTDx(t)+(1-α)ex

(1)

其中ex是表示初始狀態(tài)。式(2)的穩(wěn)態(tài)解為：

Dx=(1-α)(1-αPT)-1ex

(2)

其中元素dxy表示從節(jié)點x到達節(jié)點y時處于穩(wěn)態(tài)的概率，由此，節(jié)點x和節(jié)點y的相似性定義為：

(3)

1.2 局部隨機游走指標

局部隨機游走指標(LRW)是由Liu等[13]提出的一種基于網(wǎng)絡局部結構信息的隨機游走相似性指標，用于解決基于全局的隨機游走相似性指標存在計算復雜度過高以致難以在大規(guī)模網(wǎng)絡上應用等問題，同時也具有較高的預測準確度。它的主要特點是在隨機游走過程中只考慮有限步數(shù)。

假設一個隨機游走粒子從節(jié)點x出發(fā)，πx(t)表示此粒子從節(jié)點x經(jīng)游走t步到達網(wǎng)絡上其余各節(jié)點概率的N×1維向量，有：

πx(t)=pTπx(t-1)

(4)

其中πx(0)=ex。通常根據(jù)網(wǎng)絡各節(jié)點的重要性來分配其初始資源分布，此處假定各個節(jié)點的初始資源分布為qx，那么，節(jié)點x與任意節(jié)點y基于t步隨機游走的相似性定義為：

(5)

1.3 Word2vec模型

Word2vec是由Mikolov等[17]在2013年提出的一種快速學習詞向量表示的模型，其基本思想是利用神經(jīng)網(wǎng)絡通過訓練，將文本中的單詞轉換到低維、稠密的實數(shù)向量空間中，通過向量空間中的向量運算來簡化文本內(nèi)容上的處理。例如文本的語義相似度可以通過向量空間上的相似度來衡量，可以用于自然語言處理中的很多工作中，包括同義詞尋找、詞性分析等。

Word2vec主要使用了兩種語言模型：連續(xù)詞袋模型(Continuous Bag-Of-Words model, CBOW)和Skip-Gram(continuous Skip-Gram model)，它們在借鑒自然語言處理模型(Neural Network Language Model， NNLM)[20]的基礎上進行了簡化以便于計算，是包含了輸入層、投影層和輸出層的三層神經(jīng)網(wǎng)絡，如圖1所示。

訓練過程可以簡述為：若給定某一語料庫，使用一個固定長度為c的滑動窗口遍歷整個預料庫，每次從整個語料庫中抽取出一段語料進行訓練，假設c=2，則每次的訓練語料為Wt-2Wt-1WtWt+1Wt+2。CBOW模型的基本思想是使用某一詞Wt的上下文Wt-2Wt-1Wt+1Wt+2來預測詞Wt，訓練過程如圖1所示，輸入層為Wt的上下文Wt-2Wt-1Wt+1Wt+2各個詞向量，投影層是對輸入層所有詞向量進行累加求和，輸出層通常采用Hierarchical Softmax[21]或者Negative Sampling算法來表征已知上下文Wt-2Wt-1Wt+1Wt+2的條件下Wt出現(xiàn)的概率。Skip-Gram模型的基本思想與CBOW模型相反，是使用某一詞Wt來預測其上下文Wt-2Wt-1Wt+1Wt+2，訓練過程與CBOW模型類型類似。

2 基于網(wǎng)絡表示學習與隨機游走的鏈路預測

通過1.1節(jié)和1.2節(jié)對RWR與LRW等兩種基于隨機游走的鏈路預測指標的轉移過程進行分析，發(fā)現(xiàn)轉移矩陣P在隨機游走過程中是一個關鍵因素，對最后預測的結果產(chǎn)生重要影響。

考慮在無權網(wǎng)絡G(V,E)中，其中：V代表節(jié)點集合，E代表連邊集合，不存在自連接。LRW指標和RWR指標在隨機游走過程中，當游走到任意節(jié)點x時，選擇任意鄰居節(jié)點y的作為下一步游走的概率均是1/kx。其中：kx表示節(jié)點的度，具有較強的隨機性，沒有考慮到不同節(jié)點間的潛在網(wǎng)絡結構相似性對轉移過程的影響。本文認為，在隨機游走過程中，在網(wǎng)絡結構上相似度更高的兩節(jié)點之間應該有更高的轉移概率。

2.1 DeepWalk模型

DeepWalk是由Perozzi等[18]提出的一種基于深度學習的網(wǎng)絡表示學習模型。通過觀察發(fā)現(xiàn)，如果在一個服從冪律分布的網(wǎng)絡(即無標度網(wǎng)絡)上進行隨機游走，其網(wǎng)絡節(jié)點被訪問的頻率也服從冪律分布，而這與自然語言中的詞頻同樣服從冪律分布是類似的。受此啟發(fā)，將網(wǎng)絡中的節(jié)點類比成自然語言中的一個詞，而將網(wǎng)絡上一次隨機游走過程中產(chǎn)生的節(jié)點訪問序列類比成自然語言中的句子，再在此基礎上結合Word2vec模型將網(wǎng)絡上進行隨機游走產(chǎn)生的節(jié)點訪問序列當作Skip-Gram模型的輸入，采用隨機梯度下降和反向傳播算法對節(jié)點表示向量進行優(yōu)化，最后訓練生成每個節(jié)點最優(yōu)的向量表示。DeepWalk算法的描述框架如下所示：

輸入 網(wǎng)絡G(V,E)，滑動窗口大小ω，向量空間維數(shù)d，重新隨機游走遍歷次數(shù)γ，每次隨機游走遍歷步長t。

輸出 節(jié)點表示向量矩陣Φ∈R|V|×d。

1)初始化Φ，使其服從均勻分布。

2)將網(wǎng)絡節(jié)點構造成一棵二叉樹T。

3)將網(wǎng)絡節(jié)點隨機排序放入到集合?。

4)從屬于集合?的每個節(jié)點vi開始，在網(wǎng)絡G上進行步長為t的隨機游走，產(chǎn)生節(jié)點Wvi的訪問序列Wvi。

5)SkipGram(Φ,Wvi,ω)，即對Wvi用Skip-Gram算法更新節(jié)點向量表示。

6)一直重復步驟3)～6)γ次。

2.2 融合DeepWalk模型與隨機游走的鏈路預測

通過觀察DeepWalk模型的網(wǎng)絡節(jié)點向量的表示學習過程，發(fā)現(xiàn)它綜合考慮到了節(jié)點的“上下文信息”，即節(jié)點周圍的網(wǎng)絡結構，并通過深度學習方法不斷訓練節(jié)點的網(wǎng)絡結構特征的最優(yōu)向量表示，訓練出的節(jié)點在向量空間上的相似性可以很好地表征節(jié)點在網(wǎng)絡結構上的潛在相似性。受DeepWalk模型啟發(fā)，本文在基于隨機游走的轉移矩陣P中融合DeepWalk所生成的各節(jié)點向量表示的相似性，然后進行轉移更新，最終計算出不同節(jié)點間的相似度，這樣可以很好地體現(xiàn)出節(jié)點在潛在網(wǎng)絡結構上的相似度對隨機游走轉移過程的影響。

首先使用DeepWalk算法生成網(wǎng)絡中每個節(jié)點的向量表示，假定Φ(x)=[x1,x2,…,xd]表示任意節(jié)點x的向量，Φ(y)=[y1,y2,…,yd]表示任意節(jié)點y的向量。由于歐氏距離被廣泛采用來衡量多維空間中兩點間的距離，所以本文也利用各節(jié)點在多維空間上的歐氏距離來表征各節(jié)點在潛在網(wǎng)絡結構上的相似度，并給出定義1。

定義1 網(wǎng)絡中任意節(jié)點x和任意節(jié)點y之間的潛在網(wǎng)絡結構相似性為：

DWSim(x,y)=Euclidean(Φ(x),Φ(y))=

(6)

為了在隨機游走的轉移過程中保持一定的隨機性，在隨機游走的每一步轉移過程中按一定比例融合各節(jié)點間的潛在網(wǎng)絡結構相似性，并給出定義2。

定義2 任意節(jié)點x與其任意鄰居節(jié)點y之間的轉移概率為：

(7)

3 實驗結果及分析

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

本文實驗采用了分別在5個不同領域具有代表性的真實網(wǎng)絡數(shù)據(jù)集，忽略網(wǎng)絡連邊的權重與方向，分別如下:

1)USAir網(wǎng)絡(http://vlado.fmf.uni-lj.si/pub/networks/data)，由332個機場的之間航線構成的網(wǎng)絡，包含2 126條航線。

2)Jazz網(wǎng)絡(http://www.linkprediction.org/index.php/link/resource/data)，由198個音樂家構成的合作網(wǎng)絡，包含2 742個音樂家的合作關系。

3)Metabolic網(wǎng)絡(http://www.linkprediction.org/index.php/link/resource/data)，其中的節(jié)點代表線蟲的代謝物，連邊代表代謝物之間能直接參與的酶催化生化反應，包含453種線蟲代謝物。

4)NetScience網(wǎng)絡(networkrepository.com/network.php)，由1 589個科學家的合作關系構成的網(wǎng)絡，包含268個連通集。本實驗選取最大的連通集，包含379個節(jié)點。

5)Facebook社交網(wǎng)絡(snap.stanford.edu/data/index.html)，是從Facebook中抽取出的部分社交網(wǎng)絡，包括4 039個用戶，其中的節(jié)點代表用戶，連邊代表用戶之間的好友關系。

表1進一步列出了這5個數(shù)據(jù)集的網(wǎng)絡拓撲結構特征，其中：N表示節(jié)點數(shù)，M表示連邊數(shù)，〈K〉表示平均度，〈C〉表示平均聚集系數(shù)，D表示網(wǎng)絡直徑。

表1 各數(shù)據(jù)集的拓撲結構特征Tab. 1 Topological structure features of each dataset

3.2 評價指標

為了評估算法的準確性，實驗將數(shù)據(jù)集隨機且獨立地劃分為訓練集和測試集，90%用作訓練集，10%用作測試集，同時保證訓練集和測試集中的網(wǎng)絡具有連通性。本文實驗采用AUC(Area Under the receiver operating characteristic Curve)指標[22]來評價算法的準確性。

在鏈路預測算法計算出所有節(jié)點間存在連邊的分數(shù)值之后，AUC指標可以描述為在測試集中隨機選擇一條存在連邊的分數(shù)值比隨機選擇一條不存在連邊的分數(shù)值高的概率。這樣獨立重復比較n次，在n次中，如果有n′次在測試集中存在連邊的分數(shù)比不存在連邊的分數(shù)值高，有n″次在測試集中存在連邊的分數(shù)值與不存在連邊的分數(shù)值相等，則AUC值可以定義為：

AUC=(n′+0.5n″)/n

(8)

通常，評分算法計算出的AUC值最少應大于0.5。AUC值越高，算法的精確度就越高，最高不超過1。

3.3 實驗環(huán)境與實驗參數(shù)

實驗環(huán)境：Windows 7操作系統(tǒng)，DeepWalk模型算法采用Python 2.7實現(xiàn)，所提算法和各對比鏈路預測算法均在Matlab R2015a上實現(xiàn)。

實驗參數(shù)設置如下：

1)DeepWalk模型算法參數(shù)：ω=5,γ=10,t=40,d=64。

2)式(7)的調(diào)節(jié)參數(shù)β。實驗通過β在區(qū)間[0,1]上的不同取值，觀察β取值對預測結果的影響，整體上，β取值為0.75在所有數(shù)據(jù)集上都能取得較好的實驗效果。

3)重啟因子α。通常α取值為0.9有著較優(yōu)的效果，因此，本文設置α=0.9。

4)DWLRW和LRW隨機步長t。隨機步長對實驗的預測效果起重要作用，實驗通過在區(qū)間[2,20]上不同的取值，觀察DWLRW和LRW在不同數(shù)據(jù)集上AUC值的變化，如圖2所示，t的不同取值對AUC值產(chǎn)生一定影響，在本文實驗中取最優(yōu)步長的AUC值進行對比，在表2中DWLRW和LRW算法的AUC值后括號內(nèi)的數(shù)值表示在各數(shù)據(jù)集上的最優(yōu)步長取值。

圖2 AUC值隨參數(shù)t的影響Fig. 2 Influence of parameter t on AUC

3.4 基準方法

本文所提算法是一種基于網(wǎng)絡結構的鏈路預測方法。除了基于重啟隨機游走方法與基于局部隨機游走方法外，本文還將最常用的6種基于網(wǎng)絡結構的方法作為基準進行性能對比，其中包含基于網(wǎng)絡局部結構信息的相似性方法(CN、HDI、PA)、基于路徑的相似性方法(LP、Katz)和基于全局隨機游走的相似性方法(ACT)。下面分別對其作簡要介紹。

1)CN指標。若Γ(x)與Γ(y)分別表示節(jié)點x與節(jié)點y的直接鄰居集合，那么基于CN指標的相似性可以表示為Sxy=|Γ(x)∩Γ(y)|。

2)HDI指標：

Sxy=|Γ(x)∩Γ(y)|/ max {kx,ky}

其中kx與ky分別表示節(jié)點x與節(jié)點y的度。在這一指標中分母由度較高的節(jié)點決定，其意在減弱度值高的節(jié)點對相似性的影響。

3)PA指標。它是一個只考慮節(jié)點度相似性的指標。在無標度網(wǎng)絡中，一條新邊連接到節(jié)點x的概率正比于節(jié)點的度kx。其定義為Sxy=kxky。

4)LP指標。它是在CN的基礎上考慮了三階路徑的影響，定義為S=A2+αA3。其中α為可調(diào)節(jié)參數(shù)，用來控制三階路徑的影響；A表示網(wǎng)絡的鄰接矩陣。

3.5 實驗結果

將本文提出的算法DWRWR和DWLRW在3.1節(jié)中的5個數(shù)據(jù)集上進行實驗，為了更加準確呈現(xiàn)預測結果，在所有數(shù)據(jù)集上重復獨立實驗100次，并計算這100次實驗的AUC平均值作為最后的預測結果。表2列出了各算法在5個數(shù)據(jù)集上預測結果的AUC值比較；表3列出了所提算法DWRWR和DWLRW的AUC指標相對于RWR和LRW算法在5個數(shù)據(jù)集上的改進程度。

從表2中可以看出，在5個數(shù)據(jù)集上，本文算法DWRWR和DWLRW分別比RWR和LRW算法在AUC指標上均有所提高，同時相較于各鏈路預測基準算法，其AUC值是最高的。從表3中可以看出，在5個數(shù)據(jù)集上，DWRWR算法相較RWR算法，其預測精確度平均提升了1.34%，DWLRW算法相較LRW算法，其預測精確度平均提升了0.34%。

因此，上述結果分析表明，通過DeepWalk學習各節(jié)點在潛在網(wǎng)絡結構上的相似性，將其應用于RWR和LRW的轉移過程中，在提升鏈路預測的精確度方面起到了積極作用。

表2 各算法在5個數(shù)據(jù)集上的預測AUC值比較Tab. 2 Comparison of AUC of each algorithm on five datasets

表3 算法的AUC指標改進比例 %Tab. 3 Improvement proportion of algorithm’s AUC %

4 結語

本文針對現(xiàn)有的基于隨機游走的鏈路預測指標在無權網(wǎng)絡中的轉移過程存在較強隨機性的問題，提出了一種基于網(wǎng)絡表示學習與隨機游走的鏈路預測算法。首先通過網(wǎng)絡表示學習模型DeepWalk學習網(wǎng)絡結構潛在特征，得到節(jié)點的低維向量表示；然后，將節(jié)點間的向量的相似性融合到LRW和RWR的隨機游走轉移過程中，重新定義出不同鄰居節(jié)點間的轉移概率，使其在轉移過程中考慮了鄰居節(jié)點在網(wǎng)絡結構上的相似性。實驗結果表明，本文所提算法DWRWR和DWLRW對比現(xiàn)有眾多鏈路預測算法有著更加準確的預測結果。在下一步的研究中，可以嘗試考慮一種同時結合網(wǎng)絡結構和節(jié)點屬性信息的網(wǎng)絡表示學習方法在鏈路預測問題上的應用。

References)

[1] 呂琳媛.復雜網(wǎng)絡鏈路預測[J].電子科技大學學報,2010,39(5):651-661.(LYU L Y. Link prediction on complex networks [J]. Journal of University of Electronic Science and Technology, 2010, 39(5): 651- 661.)

[2] 胡文斌,彭超,梁歡樂,等.基于鏈路預測的社會網(wǎng)絡事件檢測方法[J].軟件學報,2015,26(9):2239-2355.(HU W B, PENG C, LIANG H L, et al. Event detection method based on link prediction for social network evolution [J]. Journal of Software, 2015, 26(9): 2339-2355.)

[3] LU L Y, ZHOU T. Link prediction in complex networks: a survey [J]. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170.

[4] JACCARD P. étude comparative de la distribution florale dans uneportion des Alpes et des Jura [J]. Bulletin del la Société Vaudoise des Sciences Naturelles, 1901, 37: 547-579.

[5] ADAMIC L A, ADAR E. Friends and neighbors on the Web [J]. Social Networks, 2003, 25(3): 211-230.

[6] BARABASI A L, ALBERT R. Emergence of scaling in random networks [J]. Science, 1999, 286(5439): 509-512.

[7] ZHOU T, LU L Y, ZHANG Y C. Predicting missing links via local information [J]. The European Physical Journal Condensed Matter and Complex System, 2009, 71(4): 623-630.

[8] LU L Y, JIN C H, ZHOU T, Similarity index based on local paths for link prediction of complex networks [J]. Physical Review E, 2009, 80(4): 046122.

[9] KATZ L. A new status index derived from sociometric analysis [J]. Psychometrika, 1953, 18(1): 39-43.

[10] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks [J]. Physical Review E, 2006, 73(2): 026120.

[11] KLEIN D J, RANDIC M. Resistance distance [J]. Journal of Mathematical Chemistry, 1993, 12(1): 81-95.

[12] TONG H, FALOUTSOS C, PAN J Y. Fast random walk with restart and its applications [C]// Proceedings of the 6th International Conference on Data Mining. Piscataway, NJ: IEEE, 2006: 613-622.

[13] LIU W P, LU L Y. Link prediction based on local random walk [J]. Europhysics Letters, 2010, 89(5): 58007.

[14] CHERRY A, ABBER E. Enhancing link prediction in twitter using semantic user attribute [C]// Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York: ACM, 2015: 1155-1161.

[15] 陳維政,張巖,李曉明.網(wǎng)絡表示學習[J].大數(shù)據(jù),2015,1(3): 8-22.(CHEN W Z, ZHANG Y, LI X M. Network representation learning [J]. Big Data Research, 2015, 1(3): 8-22.)

[16] 孫志遠,魯成祥,史忠植,等.深度學習研究與進展[J].計算機科學,2016,43(2):1-8.(SUN Z Y, LU C X, SHI Z Z, et al. Research and advances on deep learning [J]. Computer Science, 2016, 43(2): 1-8.)

[17] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality [C]// NIPS’13: Proceedings of the 26th International Conference on Neural Information Processing Systems. Red Hook, NY: Curran Associates Inc., 2013: 3111-3119.

[18] PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk: online learning of social representations [C]// Proceedings of the 20th ACM SIGKDD International Conference On Knowledge Discovery and Data Mining. New York: ACM, 2014: 701-710.

[19] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine [J]. Computer Networks and ISDN Systems, 1998, 30(1): 107-117.

[20] YOSHUA B, REJEAN D, PASCAL V, et al. A neural probabilistic language model [J]. Journal of Machine Learning Research, 2003, 3(6): 1137-1155.

[21] MORIN F, BENGIO Y. Hierarchical probabilistic neural network language model [C]// Proceedings of the 10th International Workshop Conference on Artificial Intelligence and Statistics. Cambridge, CA: MIT Press, 2005: 246-252.

[22] HANLEY J A, MCNEIL B J. The meaning and use of the area under a Receiver Operating Characteristic (ROC) curve [J]. Radiology, 1982, 143(1): 29-36.

This work is partially supported by the Natural Science Foundation of Guangdong Province (2016A030313441), the Science and Technology Planning Project of Guangdong Province (2015B010129009, 2016A030303058, 2016A090922008, 2015A020209178), the Open Project Program of Guangdong Provincial Key Laboratory of High Performance Computing (T191527), the Science and Technology Program of Guangzhou (201604016035).

LIUSi, born in 1992, M. S. candidate. His research interests include data mining, big data processing.

LIUHai, born in 1974, Ph. D., associate professor. His research interests include text mining, deep learning.

CHENQimai, born in 1965, M. S., professor. His research interests include data mining, machine learning.

HEChaobo, born in 1981, Ph. D., associate professor. His research interests include data mining, social computing.

Linkpredictionalgorithmbasedonnetworkrepresentationlearningandrandomwalk

LIU Si1, LIU Hai1,2*, CHEN Qimai1, HE Chaobo3

(1.SchoolofComputer,SouthChinaNormalUniversity,GuangzhouGuangdong510631,China；2.GuangdongProvincialKeyLaboratoryofHighPerformanceComputing,GuangzhouGuangdong510033,China；3.SchoolofInformationScienceandTechnology,ZhongkaiUniversityofAgricultureandEngineering,GuangzhouGuangdong510225,China)

The transition process of existing link prediction indexes based on random walk exists strong randomness in the unweighted network and does not consider the effect of the similarity of the network structure between different neighbor nodes on transition probability. In order to solve the problems, a new link prediction algorithm based on network representation learning and random walk was proposed. Firstly, the latent structure features of network node were learnt by DeepWalk which is a network representation learning algorithm based on deep learning, and the network nodes were encoded into low-dimensional vector space. Secondly, the similarity between neighbor nodes in vector space was incorporated into the transition process of Random Walk with Restart (RWR) and Local Random Walk (LRW) respectively and the transition probability of each random walk was redefined. Finally, a large number of experiments on five real datasets were carried out. The experimental results show that the AUC (Area Under the receiver operating characteristic Curve) values of the proposed algorithms are improved up to 3.34% compared with eight representative link prediction benchmarks based on network structure.

link prediction; similarity; Random Walk with Restart (RWR); Local Random Walk (LRW); network representation learning

TP391; TP18

A

2016- 12- 29;

2017- 02- 09。

廣東省自然科學基金自由申請項目(2016A030313441)；廣東省科技計劃項目(2015B010129009, 2016A030303058, 2016A090922008, 2015A020209178)；廣東省高性能計算重點實驗室開放課題項目(T191527)；廣州市科技計劃項目(201604016035)。

劉思(1992—)，男，江西豐城人，碩士研究生，CCF會員，主要研究方向：數(shù)據(jù)挖掘、大數(shù)據(jù)處理； 劉海(1974—)，男，湖南張家界人，副教授，博士，CCF會員，主要研究方向：文本挖掘、深度學習； 陳啟買(1965—)，男，湖南衡陽人，教授，碩士，主要研究方向：數(shù)據(jù)挖掘、機器學習； 賀超波(1981—)，男，廣東河源人，副教授，博士，CCF高級會員，主要研究方向：數(shù)據(jù)挖掘、社會計算。

1001- 9081(2017)08- 2234- 06

10.11772/j.issn.1001- 9081.2017.08.2234