馮仁君 陳海雁 王芳

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

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

中圖分類(lèi)號(hào)：TP309? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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

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

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

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

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

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

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

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

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

表示學(xué)習(xí)的表示長(zhǎng)期以來(lái)一直是機(jī)器學(xué)習(xí)的一個(gè)重要問(wèn)題，許多工作都是針對(duì)樣本的表示學(xué)習(xí)[12]。近年來(lái)，深度神經(jīng)網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)的研究表明，它們具有強(qiáng)大的表示能力，能夠?yàn)槎喾N類(lèi)型的數(shù)據(jù)提取可靠的特征并且生成強(qiáng)有力的表示。例如，Simonyan等人研究了卷積網(wǎng)絡(luò)深度對(duì)大規(guī)模圖像識(shí)別設(shè)置精度的影響[13]。Wang等人提出了一種多模態(tài)深度模型來(lái)學(xué)習(xí)圖像-文本的統(tǒng)一表示[14]，從而實(shí)現(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è)計(jì)了兩個(gè)損失函數(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]，嘗試使用一階和高階鄰近性來(lái)保存本地和全局網(wǎng)絡(luò)結(jié)構(gòu)，但是它們分別學(xué)習(xí)表示，并簡(jiǎn)單地將表示連接起來(lái)。顯然，與同時(shí)在統(tǒng)一的體系結(jié)構(gòu)中對(duì)它們建模相比，同時(shí)捕獲本地和全局網(wǎng)絡(luò)結(jié)構(gòu)是次優(yōu)的。

1.3? ?鏈路預(yù)測(cè)的相似性指標(biāo)

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

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

相似矩陣表示為Sim。

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

2? ?算法設(shè)計(jì)

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

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

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

2.2? ?算法建模

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

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

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

3? ?實(shí)驗(yàn)及分析

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

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

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

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

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

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

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

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

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

4? ?結(jié)? ?論

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

參考文獻(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ó)正. 基于頻繁閉圖關(guān)聯(lián)規(guī)則的AS級(jí)Internet鏈路預(yù)測(cè)方法[J].? 計(jì)算機(jī)科學(xué)，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.