基于網(wǎng)絡(luò)表示學(xué)習(xí)與隨機(jī)游走的鏈路預(yù)測算法

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

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

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

基于網(wǎng)絡(luò)表示學(xué)習(xí)與隨機(jī)游走的鏈路預(yù)測算法

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

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

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

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

鏈路預(yù)測；相似性；重啟隨機(jī)游走；局部隨機(jī)游走；網(wǎng)絡(luò)表示學(xué)習(xí)

0 引言

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 重啟隨機(jī)游走指標(biāo)

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

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

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

(1)

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

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

(2)

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

(3)

1.2 局部隨機(jī)游走指標(biāo)

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

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

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

(4)

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

(5)

1.3 Word2vec模型

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

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

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

2 基于網(wǎng)絡(luò)表示學(xué)習(xí)與隨機(jī)游走的鏈路預(yù)測

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

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

2.1 DeepWalk模型

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

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

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

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

2)將網(wǎng)絡(luò)節(jié)點(diǎn)構(gòu)造成一棵二叉樹T。

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

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

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

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

2.2 融合DeepWalk模型與隨機(jī)游走的鏈路預(yù)測

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

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

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

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

(6)

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

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

(7)

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

4)NetScience網(wǎng)絡(luò)(networkrepository.com/network.php)，由1 589個科學(xué)家的合作關(guān)系構(gòu)成的網(wǎng)絡(luò)，包含268個連通集。本實(shí)驗(yàn)選取最大的連通集，包含379個節(jié)點(diǎn)。

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

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

表1 各數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)特征Tab. 1 Topological structure features of each dataset

3.2 評價指標(biāo)

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

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

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

(8)

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

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

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

實(shí)驗(yàn)參數(shù)設(shè)置如下：

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

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

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

4)DWLRW和LRW隨機(jī)步長t。隨機(jī)步長對實(shí)驗(yàn)的預(yù)測效果起重要作用，實(shí)驗(yàn)通過在區(qū)間[2,20]上不同的取值，觀察DWLRW和LRW在不同數(shù)據(jù)集上AUC值的變化，如圖2所示，t的不同取值對AUC值產(chǎn)生一定影響，在本文實(shí)驗(yàn)中取最優(yōu)步長的AUC值進(jìn)行對比，在表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 基準(zhǔn)方法

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

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

2)HDI指標(biāo)：

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

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

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

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

3.5 實(shí)驗(yàn)結(jié)果

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

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

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

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

表3 算法的AUC指標(biāo)改進(jìn)比例 %Tab. 3 Improvement proportion of algorithm’s AUC %

4 結(jié)語

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

References)

[1] 呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J].電子科技大學(xué)學(xué)報,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] 胡文斌,彭超,梁歡樂,等.基于鏈路預(yù)測的社會網(wǎng)絡(luò)事件檢測方法[J].軟件學(xué)報,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)絡(luò)表示學(xué)習(xí)[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] 孫志遠(yuǎn),魯成祥,史忠植,等.深度學(xué)習(xí)研究與進(jìn)展[J].計算機(jī)科學(xué),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。

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

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

1001- 9081(2017)08- 2234- 06

10.11772/j.issn.1001- 9081.2017.08.2234