基于網(wǎng)絡(luò)嵌入和關(guān)聯(lián)相似性的鏈路預(yù)測算法

馮仁君 陳海雁 王芳

摘? ?要：鏈路預(yù)測作為復(fù)雜網(wǎng)絡(luò)分析的一個重要分支，在不同領(lǐng)域中有著廣泛的應(yīng)用，而且通過進一步提取網(wǎng)絡(luò)結(jié)構(gòu)信息可以提高鏈路預(yù)測的精度。提出了一種基于結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入和關(guān)聯(lián)相似性的鏈路預(yù)測算法（Structural Deep Correlation Similarity Network Embedding，SDCSNE）。SDCSNE算法結(jié)合了網(wǎng)絡(luò)嵌入捕捉高維非線性網(wǎng)絡(luò)結(jié)構(gòu)的特征，將網(wǎng)絡(luò)映射到向量空間中，這些映射向量的內(nèi)積即為對應(yīng)節(jié)點的相似性，并保持了全局和局部的網(wǎng)絡(luò)結(jié)構(gòu)，獲得了更加穩(wěn)定的網(wǎng)絡(luò)結(jié)構(gòu)信息;SDCSNE算法還融入了節(jié)點的關(guān)聯(lián)性，以提高預(yù)測的準確性。實際結(jié)果表明，在鏈路預(yù)測任務(wù)中，SDCSNE算法具有良好的性能。

關(guān)鍵詞：鏈路預(yù)測;復(fù)雜網(wǎng)絡(luò);相似性;網(wǎng)絡(luò)嵌入;關(guān)聯(lián)

中圖分類號：TP309? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A

文章編號：1003—6199（2020）02—0114—05

Abstract：Link prediction，as an important branch of complex network analysis，has been widely used in different fields.A link prediction algorithm （SDCSNE） based on structural depth network embedding and association similarity is proposed.The algorithm combines the characteristics of network embedding to capture the high-dimensional nonlinear network structure，and maps the network to the vector space. The inner product of these mapping vectors is the similarity of the corresponding nodes，and maintains the global and local network structure，so as to obtain more stable network structure information.The SDCSNE algorithm also incorporates the relevance of nodes to improve the accuracy of prediction.The practical results show that SDCSNE algorithm has good performance in link prediction.

Key words：link prediction;complex networks;similarity;network embedding;correlation

近年來，復(fù)雜網(wǎng)絡(luò)理論體系不斷發(fā)展完善，如何利用已有的網(wǎng)絡(luò)預(yù)測缺失或者未來可能出現(xiàn)的關(guān)系，分析和探索這些數(shù)據(jù)的潛在價值已經(jīng)成為研究熱點。該問題也被稱為鏈路預(yù)測，對認識和了解復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)具有重要意義。

復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測問題的研究則是對真實世界網(wǎng)絡(luò)的進一步剖析。其中，網(wǎng)絡(luò)由節(jié)點和連接節(jié)點之間的連邊組成，通常情況下，節(jié)點可以表示社交網(wǎng)絡(luò)中的個人、蛋白質(zhì)相互作用網(wǎng)絡(luò)中的蛋白質(zhì)、購買商品的客戶等等，連邊則表示兩個節(jié)點之間是否存在聯(lián)系或者是否發(fā)生作用。如果兩個節(jié)點具有某種特定的作用或者聯(lián)系則存在一條連邊，反之則不存在連邊。針對鏈路預(yù)測問題，利用已形成的蛋白質(zhì)相互作用網(wǎng)絡(luò)，來預(yù)測蛋白質(zhì)之間未知相互作用[1];在社會關(guān)系網(wǎng)絡(luò)中，朋友之間的關(guān)系影響人們社交關(guān)系演化以及網(wǎng)絡(luò)中的用戶關(guān)系[2-3];根據(jù)人們的購物信息形成的電商網(wǎng)絡(luò)，結(jié)合不同的購物風格，從而進行商品推薦以及預(yù)測挖掘潛在的客戶[4];不僅如此，鏈路預(yù)測方法還在檢測和控制網(wǎng)絡(luò)攻擊、交通網(wǎng)絡(luò)等應(yīng)用中發(fā)揮著重要作用[5]。

鏈路預(yù)測算法使用最為廣泛的是基于相似性的方法，因為方法簡單、計算復(fù)雜度相對較低為人關(guān)注，其基本思想是如果兩個節(jié)點越相似，那么它們之間存在鏈路的可能性就越大。從網(wǎng)絡(luò)資源分配的角度來說，有RA（Resource Allocation，RA）指標[6]與AA（Adamix-Adar，AA）指標[7]，均考慮了網(wǎng)絡(luò)節(jié)點度信息，將兩個節(jié)點之間的資源傳遞信息量作為相似性指標?；诠餐従拥腃N（Common Neighbors，CN）指標[8]，將共同鄰居個數(shù)作為衡量相似性的標準。在此基礎(chǔ)上，考慮到節(jié)點度的影響，衍生了Jaccard指標、HDI（Hub Depressed Iindex，HDI）指標等一系列基于局部信息的相似性指標。這類算法因具有高魯棒性、容易操作的特點，被廣大研究者所關(guān)注;但此類算法缺乏對未來鏈路時序性的研究[9]。除了提取結(jié)構(gòu)信息，基于路徑信息的相似性指標也是鏈路預(yù)測領(lǐng)域的一大熱點?；诼窂叫畔⒌南嗨菩灾笜擞蠯atz指標、LP（Local Path，LP）指標[10]。

然而以上方法，均很難選取合適的特征來表示節(jié)點的相似性。網(wǎng)絡(luò)嵌入是學習網(wǎng)絡(luò)中頂點表示的重要方法之一，目的是捕獲和維護網(wǎng)絡(luò)結(jié)構(gòu)，并且由于其在處理網(wǎng)絡(luò)數(shù)據(jù)時表現(xiàn)出優(yōu)越性，被運用于預(yù)測連接中。相似性就可以簡單地定義為嵌入向量之間的內(nèi)積，從而使得基于網(wǎng)絡(luò)嵌入的鏈路預(yù)測方法無需手動選擇網(wǎng)絡(luò)特征而實現(xiàn)鏈路預(yù)測。有人提出一種結(jié)構(gòu)化的深度網(wǎng)絡(luò)嵌入方法（Structural Deep Network Embedding，SDNE），利用一階近似和二階近似來共同保持網(wǎng)絡(luò)結(jié)構(gòu)[11]，從而來學習網(wǎng)絡(luò)的潛在表示。因此，通過適當?shù)木W(wǎng)絡(luò)嵌入，可以很容易地處獲取網(wǎng)絡(luò)的潛在信息，解決鏈路預(yù)測問題。

針對SDNE方法進行改進，在捕捉高度非線性網(wǎng)絡(luò)結(jié)構(gòu)的過程中，提取嵌入向量并定義為相似度指標，提出了基于結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入和關(guān)聯(lián)相似性的鏈路預(yù)測算法。

1? ?相關(guān)工作

基于網(wǎng)絡(luò)嵌入的鏈路預(yù)測方法，首先是利用網(wǎng)絡(luò)嵌入的方法對方法進行特征相似性的提取，然后是對網(wǎng)絡(luò)進行重構(gòu)進而預(yù)測新鏈路。隨著數(shù)據(jù)的不斷更新，傳統(tǒng)的鏈路預(yù)測方法不再適用，因此，針對選擇合適的特征方法不斷被提出來。

1.1? ?深度神經(jīng)網(wǎng)絡(luò)

表示學習的表示長期以來一直是機器學習的一個重要問題，許多工作都是針對樣本的表示學習[12]。近年來，深度神經(jīng)網(wǎng)絡(luò)進行表示學習的研究表明，它們具有強大的表示能力，能夠為多種類型的數(shù)據(jù)提取可靠的特征并且生成強有力的表示。例如，Simonyan等人研究了卷積網(wǎng)絡(luò)深度對大規(guī)模圖像識別設(shè)置精度的影響[13]。Wang等人提出了一種多模態(tài)深度模型來學習圖像-文本的統(tǒng)一表示[14]，從而實現(xiàn)跨模態(tài)檢索任務(wù)。

1.2? ?網(wǎng)絡(luò)嵌入

較早期有一些關(guān)于網(wǎng)絡(luò)嵌入的相關(guān)工作，如局部線性嵌入（Locally Linear Embedding，LocallyLLE）[15]方法，IsoMAP等人[16]首先基于特征向量構(gòu)造親和圖，然后求解主導(dǎo)特征向量作為網(wǎng)絡(luò)表示。最近，有人設(shè)計了兩個損失函數(shù)，分別嘗試捕獲本地和全局網(wǎng)絡(luò)結(jié)構(gòu)[17]。盡管這些網(wǎng)絡(luò)嵌入方法取得了成功，但它們都采用了淺層模型，這很難有效地捕捉底層網(wǎng)絡(luò)中高度非線性的結(jié)構(gòu)。此外，有研究人員利用網(wǎng)絡(luò)結(jié)構(gòu)的高階信息[11，18]，嘗試使用一階和高階鄰近性來保存本地和全局網(wǎng)絡(luò)結(jié)構(gòu)，但是它們分別學習表示，并簡單地將表示連接起來。顯然，與同時在統(tǒng)一的體系結(jié)構(gòu)中對它們建模相比，同時捕獲本地和全局網(wǎng)絡(luò)結(jié)構(gòu)是次優(yōu)的。

1.3? ?鏈路預(yù)測的相似性指標

SDNE[11]結(jié)合了深度神經(jīng)網(wǎng)絡(luò)和網(wǎng)絡(luò)嵌入來學習網(wǎng)絡(luò)表示，模型結(jié)構(gòu)如圖1。

SDNE算法通過多個非線性函數(shù)組成的深度結(jié)構(gòu)，將輸入數(shù)據(jù)映射到一個高度非線性的潛在空間來捕捉網(wǎng)絡(luò)結(jié)構(gòu)。在解決鏈路預(yù)測問題時，向模型輸入鄰接矩陣經(jīng)過映射輸出重構(gòu)后的鄰接矩陣A，所對應(yīng)的嵌入向量為Uk = [u1，u1，…，un]。在這里，用嵌入向量的內(nèi)積來表示兩個對應(yīng)節(jié)點的相似性。兩個節(jié)點越相似，它們對應(yīng)嵌入向量的內(nèi)積就越大。因此，節(jié)點vi和節(jié)點vj之間的相似性可以表示為

相似矩陣表示為Sim。

SDNE算法提出了一個具有多層非線性函數(shù)的半監(jiān)督深度模型，從而能夠捕捉到高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)。在此基礎(chǔ)上，提出了利用一階近似和二階近似來共同保持網(wǎng)絡(luò)結(jié)構(gòu)。其中，二階近似來捕獲全局網(wǎng)絡(luò)結(jié)構(gòu)，而一階近似度作為監(jiān)督分量中的監(jiān)督信息，以保持局部網(wǎng)絡(luò)結(jié)構(gòu)。該方法在半監(jiān)督深度模型中通過一個顯式的目標函數(shù)聯(lián)合優(yōu)化，從而達到既能保持局部網(wǎng)絡(luò)結(jié)構(gòu)，又能保持全局網(wǎng)絡(luò)結(jié)構(gòu)的特性。

2? ?算法設(shè)計

2.1? ?基于網(wǎng)絡(luò)嵌入的關(guān)聯(lián)相似性改進算法

關(guān)聯(lián)相似性是基于相似的傳遞性，如果網(wǎng)絡(luò)中的三個節(jié)點x、y、z，其中x與z相似，y與z相似，那么x和y很有可能是相似的，這種相似是間接的，它對網(wǎng)絡(luò)的影響常常被忽視。x和y的相似性可表示為：

在等式（8）中，S（x，y）表示上一小節(jié)中的直接相似性的值;δ是可調(diào)參數(shù)，用來調(diào)節(jié)直接相似性和間接相似性的比值。最后，相似矩陣表示為：

2.2? ?算法建模

為解決復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測問題提出了基于網(wǎng)絡(luò)嵌入和關(guān)聯(lián)相似性的鏈路預(yù)測（Structural Deep Correlation Similarity Network Embedding，SDCSNE）。下面從網(wǎng)絡(luò)嵌入、關(guān)聯(lián)相似性算法的構(gòu)建對算法建模進行闡述。

對于網(wǎng)絡(luò)嵌入方法是基于SDNE算法進行修改。SDNE具有能夠捕捉到高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)，并利用一階近似和二階近似來共同保持網(wǎng)絡(luò)結(jié)構(gòu)，在此基礎(chǔ)上提取嵌入向量作為評價相似度的標準。與此同時，考慮到這種表示相似度的方法只關(guān)注了節(jié)點之間的直接相似程度而忽視了間接間接相似度，為了解決這個問題，提出了SDCSNE方法進行鏈路預(yù)測。

修改SDNE方法后的SDCSNE方法預(yù)測鏈路，如算法1所示。

3? ?實驗及分析

3.1? ?數(shù)據(jù)

數(shù)據(jù)采用Leskovec[19]在一項工作中使用的網(wǎng)絡(luò)數(shù)據(jù)ARXIV GR-QC，這是一個論文協(xié)作網(wǎng)絡(luò)。在這個網(wǎng)絡(luò)中，頂點表示作者，邊緣表示作者合作撰寫過一篇科學論文。此外，文中還使用了蛋白質(zhì)相互作用PPI和政治博客網(wǎng)絡(luò)PB。這三個真實網(wǎng)絡(luò)數(shù)據(jù)集用于鏈接預(yù)測任務(wù)。

3.2? ?實驗結(jié)果

提出的鏈路預(yù)測算法以結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入方法為基礎(chǔ)，該方法首先結(jié)合深度神經(jīng)網(wǎng)絡(luò)通過自編碼器對鄰接矩陣進行重構(gòu)，提取網(wǎng)絡(luò)嵌入過程中的嵌入向量，定義嵌入向量的內(nèi)積來表示兩個對應(yīng)節(jié)點的相似性。在一階近似和二階近似的作用下，嵌入向量包含了全局和局部的網(wǎng)絡(luò)結(jié)構(gòu)，對應(yīng)的節(jié)點也相應(yīng)的保留了全局和局部的網(wǎng)絡(luò)特征，因此用此方法來表示對應(yīng)的兩個節(jié)點的相似性。但是此方法忽略了間接相似性的重要性，采取了SDCSNE方法，保證了相似的關(guān)聯(lián)性。

在實驗中，引入了@p作為判斷算法優(yōu)劣程度的評估指標，其中@p定義如下：

其中，V是節(jié)點集合，index（j）是第j個頂點的排序索引，Δ（i，j）=1表示節(jié)點vi和節(jié)點vj之間有鏈接。

首先，對網(wǎng)絡(luò)GR-QC隨機隱藏了15%的鏈路，并使用@p作為評價指標。圖2顯示了k值逐步從2增加到1000，對預(yù)測精度的影響。當k小于等于500時，精度隨著迭代次數(shù)的增加始終保持在90%以上，反之，精度低于80%。k值的變化對預(yù)測精度的影響如圖2所示。

接著，使用三個網(wǎng)絡(luò)GR-QC、PPI、PB網(wǎng)絡(luò)進行測試，這三個網(wǎng)絡(luò)按稀疏程度排序。訓(xùn)練結(jié)果如表1。發(fā)現(xiàn)網(wǎng)絡(luò)越稀疏，該算法的預(yù)測精度越低，但當k為小于等于100時，預(yù)測精度依舊在70%以上。對于此算法，對于一般的網(wǎng)絡(luò)都可以得到較好的效果，但對稀疏網(wǎng)絡(luò)在一定條件下才會有不錯的效果。鏈路預(yù)測的精度與@P有不可或缺的影響。

實驗表明，本文提出的基于網(wǎng)絡(luò)嵌入和關(guān)聯(lián)相似性的算法可以在真實世界的網(wǎng)絡(luò)中進行預(yù)測缺失或者未來可能出現(xiàn)的鏈接，并且在稀疏度不同的網(wǎng)絡(luò)中均可以達到極佳的預(yù)測精度。

4? ?結(jié)? ?論

復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測具有廣泛的應(yīng)用價值。運用結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入的方法捕捉高度非線性網(wǎng)絡(luò)結(jié)構(gòu)，并結(jié)合了節(jié)點的關(guān)聯(lián)相似性提出了基于網(wǎng)絡(luò)嵌入和關(guān)聯(lián)相似性的鏈路預(yù)測算法。該方法通過提取提取嵌入向量的內(nèi)積作為衡量其相似性指標，然后基于相似的關(guān)聯(lián)性，將節(jié)點的間接相似性融入網(wǎng)絡(luò)嵌入方法中。最后，將該算法應(yīng)用于以上幾個真實世界網(wǎng)絡(luò)中，進行預(yù)測網(wǎng)絡(luò)中已經(jīng)缺失或未來可能出現(xiàn)的鏈接。實驗表明，該方法具有良好的性能。

參考文獻

[1]? ? YAN Ling-ling，CHEN Zeng-qiang，ZHANG Qing. Analysis of key nodes in China's aviation network based on the degree centrality indicator and clustering coefficient[J].? CAAI Transactions on Intelligent Systems，2016，11（5）：586-593.

[2]? ? WANG P，XU B，WU Y，et al. Link prediction in social networks：the state-of-the-art[J].? Science in China Series F：Information Sciences，2015，58（1）：1-38.

[3]? ?HU W，WANG H，PENG C，et al. An event detection method for social networks based on link prediction[J].? Information Systems，2017：16-26.

[4]? ?MADAN K，YADAV R. Understanding and predicting antecedents of mobile shopping adoption：a developing country perspective[J].? Asia Pacific Journal of Marketing and Logistics，2018，30（1）：139-162.

[5]? ?CHEN B，CHEN L. A link prediction algorithm based on ant colony optimization[J].? Applied Intelligence，2014，41（3）：694-708.

[6]? ? ZHOU T，LU L，ZHANG Y，et al. Predicting missing links via local information[J].? European Physical Journal B，2009，71（4）：623-630.

[7]? ? ADAMIC L A，ADAR E. Friends and neighbors on the Web[J].? Social Networks，2003，25（3）：211-230.

[8]? ? LIBENNOWELL D，KLEINBERG J M. The link-prediction problem for social networks[J].? Journal of the Association for Information Science and Technology，2007，58（7）：1019-1031.

[9]? ? 張巖慶，陸余良，楊國正. 基于頻繁閉圖關(guān)聯(lián)規(guī)則的AS級Internet鏈路預(yù)測方法[J].? 計算機科學，2016，43（Z6）：314-318.

[10]? LU L，JIN C，ZHOU T，et al. Similarity index based on local paths for link prediction of complex networks[J].? Physical Review E，2009，80（4）：1-9.

[11]? WANG D，CUI P，ZHU W，et al. Structural deep network embedding[C]//Knowledge Discovery and Data Mining，2016：1225-1234.

[12]? XU C，TAO D，XU C，et al. Multi-view intact space learning[J].? IEEE Transactions on Pattern Analysis and Machine Intelligence，2015，37（12）：2531-2544.

[13]? SIMONYAN K，ZISSERMAN A. Very deep convolutional networks for large-scale image recognition[C]//International Conference on Learning Representations，2015，1-14.

[14]? WANG D，CUI P，OU M，et al. Deep multimodal hashing with orthogonal regularization[C]//International Conference on Artificial Intelligence，2015：2291-2297.

[15]? ROWEIS S T，SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science，2000，290（5500）：2323-2326.

[16]? TENENBAUM J B，DE SILVA V，LANGFORD J，et al. A global geometric framework for nonlinear dimensionality reduction[J].? Science，2000，290（5500）：2319-2323.

[17]? TANG J，QU M，WANG M，et al. LINE：large-scale information network embedding[C]//The Web Conference，2015：1067-1077.

[18] RIBEIRO L F，SAVERESE P H，F(xiàn)IGUEIREDO D R，et al. Struc2vec ：learning node representations from structural identity[C]//Knowledge discovery and Data Mining，2017：385-394.

[19]? LESKOVEC J，KLEINBERG J M，F(xiàn)ALOUTSOS C，et al. Graph evolution：densification and shrinking diameters[J].? ACM Transactions on Knowledge Discovery From Data，2007，1（1）：1-42.