趙宇紅，張 政

(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010)

1 引 言

在網(wǎng)絡(luò)理論研究中，復(fù)雜網(wǎng)絡(luò)是由數(shù)量眾多的節(jié)點(diǎn)和節(jié)點(diǎn)之間錯(cuò)綜復(fù)雜的關(guān)系共同構(gòu)成的網(wǎng)絡(luò)[1].復(fù)雜網(wǎng)絡(luò)擁有眾多形式，既不是完全規(guī)則，也不是完全隨機(jī).現(xiàn)實(shí)世界中存在的網(wǎng)絡(luò)一般都是復(fù)雜網(wǎng)絡(luò)，比如常見的電力網(wǎng)絡(luò)、航空網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)以及社交網(wǎng)絡(luò)等.復(fù)雜網(wǎng)絡(luò)的研究是網(wǎng)絡(luò)研究中的一大熱點(diǎn)，而鏈路預(yù)測(cè)能夠?qū)?fù)雜網(wǎng)絡(luò)中的缺失信息或隱含信息進(jìn)行預(yù)測(cè)，從而有效挖掘和呈現(xiàn)內(nèi)在的信息與規(guī)則，因此吸引著越來(lái)越多研究者的關(guān)注.

鏈路預(yù)測(cè)的目標(biāo)體現(xiàn)在對(duì)于網(wǎng)絡(luò)中實(shí)際存在但是還沒有被探測(cè)到的鏈路的預(yù)測(cè)或?qū)W(wǎng)絡(luò)中目前不存在，但應(yīng)該存在或者是未來(lái)有可能存在的鏈路的預(yù)測(cè)[2].復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測(cè)是指通過(guò)已知的網(wǎng)絡(luò)節(jié)點(diǎn)信息以及網(wǎng)絡(luò)結(jié)構(gòu)信息等，預(yù)測(cè)網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生連接的可能性，在實(shí)際應(yīng)用中有著巨大的價(jià)值.例如，在蛋白質(zhì)相互作用網(wǎng)絡(luò)中通過(guò)鏈路預(yù)測(cè)結(jié)果指導(dǎo)試驗(yàn)，提高試驗(yàn)的成功率從而降低試驗(yàn)成本[3]；在社交網(wǎng)絡(luò)中通過(guò)鏈路預(yù)測(cè)方法對(duì)用戶進(jìn)行好友推薦[4]，提高相關(guān)網(wǎng)站在用戶心中的地位和用戶對(duì)網(wǎng)站的忠誠(chéng)度；在電子商務(wù)網(wǎng)絡(luò)中，通過(guò)對(duì)用戶歷史行為和購(gòu)買記錄進(jìn)行分析，為用戶推薦相應(yīng)產(chǎn)品或者電影，在吸引用戶、推廣產(chǎn)品等方面具有重要的作用[5].

隨著計(jì)算機(jī)硬件技術(shù)的進(jìn)步，計(jì)算機(jī)運(yùn)算能力得到巨大提升，人工神經(jīng)網(wǎng)絡(luò)算法得以高效率運(yùn)行，深度學(xué)習(xí)得到前所未有的發(fā)展，使深度學(xué)習(xí)成為熱門的研究方向，其在圖像處理、音頻處理以及自然語(yǔ)言處理等領(lǐng)域的成功運(yùn)用為解決鏈路預(yù)測(cè)問(wèn)題帶來(lái)了啟發(fā).文獻(xiàn)[6]提出兩種模型架構(gòu)—CBOW(Continuous Bag of Words)和skip-gram，用來(lái)計(jì)算大規(guī)模數(shù)據(jù)集中的連續(xù)詞向量表示.對(duì)計(jì)算得出的結(jié)果通過(guò)詞相似性任務(wù)進(jìn)行評(píng)估.兩種模型分別通過(guò)上下文對(duì)中心詞進(jìn)行評(píng)估以及通過(guò)中心詞對(duì)上下文進(jìn)行評(píng)估，在自然語(yǔ)言處理中應(yīng)用十分廣泛，且計(jì)算成本相對(duì)較小.

近年來(lái)，鏈路預(yù)測(cè)方法僅僅考慮節(jié)點(diǎn)自身屬性信息或者僅僅考慮節(jié)點(diǎn)所處的網(wǎng)絡(luò)結(jié)構(gòu)信息，這兩類方法都只考慮復(fù)雜網(wǎng)絡(luò)中的部分信息.

本文從概率語(yǔ)言模型訓(xùn)練產(chǎn)生的詞向量得到啟發(fā)，向量作為原生信息在空間中的呈現(xiàn)，是信息本質(zhì)特征的內(nèi)在表現(xiàn).網(wǎng)絡(luò)中的節(jié)點(diǎn)可以看作是自然語(yǔ)言處理過(guò)程中的詞，在網(wǎng)絡(luò)演化中，節(jié)點(diǎn)本身的特性與結(jié)構(gòu)關(guān)聯(lián)將形成節(jié)點(diǎn)的上下文信息.為了有效、全面地獲取網(wǎng)絡(luò)中的節(jié)點(diǎn)序列信息，將節(jié)點(diǎn)序列看作是具有意義的句子，考慮每一個(gè)節(jié)點(diǎn)出現(xiàn)在節(jié)點(diǎn)序列某一位置的概率，提出基于連續(xù)詞帶模型(Continuous Bag of Words，CBOW)的鏈路預(yù)測(cè)方法.使用深度優(yōu)先搜索(DFS)獲得包含網(wǎng)絡(luò)結(jié)構(gòu)信息的節(jié)點(diǎn)路徑，再結(jié)合使用廣度優(yōu)先搜索(BFS)獲得的節(jié)點(diǎn)n階鄰居信息的節(jié)點(diǎn)序列，可以獲取節(jié)點(diǎn)序列的完整信息.使用CBOW模型通過(guò)中心節(jié)點(diǎn)的上下文節(jié)點(diǎn)序列訓(xùn)練產(chǎn)生節(jié)點(diǎn)對(duì)應(yīng)的向量表示.向量的方向與大小是向量的原生信息，因此提出一種節(jié)點(diǎn)向量相似性指標(biāo)—向量自量趨向性(Self-measurement Tendency of Vector，SMTV)，以此指標(biāo)完成度量并進(jìn)行鏈路預(yù)測(cè).通過(guò)在3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中進(jìn)行的對(duì)比試驗(yàn)，本文提出的方法相比其他經(jīng)典算法在預(yù)測(cè)精確度方面表現(xiàn)更好.

2 相關(guān)工作

2.1 基于相似性的鏈路預(yù)測(cè)方法

基于相似性的鏈路預(yù)測(cè)方法從度量角度不同分為基于節(jié)點(diǎn)相似性的預(yù)測(cè)方法和基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的預(yù)測(cè)方法.

2.1.1 基于節(jié)點(diǎn)相似性的鏈路預(yù)測(cè)

在網(wǎng)絡(luò)中單純考慮節(jié)點(diǎn)之間屬性的相似程度就可以判斷兩個(gè)節(jié)點(diǎn)是否相似，屬性相似的節(jié)點(diǎn)之間更容易連接[7].在網(wǎng)絡(luò)中刻畫節(jié)點(diǎn)屬性的相似性，最簡(jiǎn)單直接的方法就是利用節(jié)點(diǎn)的標(biāo)簽.比如，網(wǎng)絡(luò)虛擬身份中的職業(yè)、地區(qū)、教育程度、興趣愛好、性別等，利用上述屬性在社交網(wǎng)絡(luò)中進(jìn)行好友推薦，就可能找到潛在的好友.但是，由于網(wǎng)絡(luò)自由性和監(jiān)管問(wèn)題，在很多情況下，獲取網(wǎng)絡(luò)節(jié)點(diǎn)的真實(shí)屬性信息是不現(xiàn)實(shí)的，例如，在社交網(wǎng)絡(luò)中，個(gè)人用戶注冊(cè)的信息可能是虛假的，因此將虛假信息作為節(jié)點(diǎn)的屬性進(jìn)行鏈路預(yù)測(cè)就變得不可信.

2.1.2 基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的鏈路預(yù)測(cè)

在網(wǎng)絡(luò)中難以獲得真實(shí)節(jié)點(diǎn)屬性信息的時(shí)候，一種可行的方法是根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)來(lái)計(jì)算節(jié)點(diǎn)的相似性.如果在網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)所處的網(wǎng)絡(luò)結(jié)構(gòu)越相似，那么它們之間存在連邊的可能性越大.

基于網(wǎng)絡(luò)結(jié)構(gòu)信息的相似性預(yù)測(cè)方法最經(jīng)典的就是共同鄰居(CommonNeighbors，CN)[8]，即兩個(gè)節(jié)點(diǎn)如果有更多的共同鄰居，則它們的相似性越高，越有可能產(chǎn)生連邊.其公式如公式(1)所示:

(1)

CN方法認(rèn)為每個(gè)共同鄰居對(duì)于這兩個(gè)節(jié)點(diǎn)的貢獻(xiàn)度是相同的，但是，通常共同的鄰居節(jié)點(diǎn)對(duì)于節(jié)點(diǎn)的貢獻(xiàn)度可能是不同的.一般情況下我們認(rèn)為度大的共同鄰居比度小的共同鄰居貢獻(xiàn)度小.基于兩節(jié)點(diǎn)共同鄰居的度的信息的Adamic-Adar(AA)指標(biāo)[9]，根據(jù)共同鄰居節(jié)點(diǎn)的度為每個(gè)節(jié)點(diǎn)賦予一個(gè)權(quán)重值，該權(quán)重等于節(jié)點(diǎn)的度的對(duì)數(shù)分之一.其公式如公式(2)所示:

(2)

其中kz代表節(jié)點(diǎn)z的度.如果節(jié)點(diǎn)a和節(jié)點(diǎn)b共同鄰居節(jié)點(diǎn)的度越大，那么該指標(biāo)分?jǐn)?shù)值越低.

基于共同鄰居的相似性指標(biāo)的優(yōu)勢(shì)在于計(jì)算復(fù)雜度較低，但是由于使用的信息非常有限，預(yù)測(cè)精度受到限制.例如在Internet路由器網(wǎng)絡(luò)中，由5000多個(gè)節(jié)點(diǎn)構(gòu)成的一千多萬(wàn)節(jié)點(diǎn)對(duì)中有超過(guò)99%的節(jié)點(diǎn)對(duì)之間的CN相似性分?jǐn)?shù)都是0，剩下的節(jié)點(diǎn)對(duì)中也有超過(guò)90%的節(jié)點(diǎn)對(duì)分?jǐn)?shù)是1，只有不到5%的分?jǐn)?shù)是2，導(dǎo)致的結(jié)果是相似性分?jǐn)?shù)過(guò)于集中，節(jié)點(diǎn)對(duì)之間的區(qū)分度太低，鏈路預(yù)測(cè)的精度受限[10].周濤等人[11，12]在共同鄰居的基礎(chǔ)上考慮三階路徑的因素，提出基于局部信息相似性的Local Path(LP)指標(biāo).即在考慮共同鄰居的基礎(chǔ)上，繼續(xù)考慮兩個(gè)節(jié)點(diǎn)之間通過(guò)三條路徑即兩個(gè)節(jié)點(diǎn)進(jìn)行連接的路徑條數(shù)，結(jié)合兩者計(jì)算兩節(jié)點(diǎn)之間的相似性，計(jì)算公式如公式(3)所示:

(3)

其中α為可調(diào)參數(shù)，A表示網(wǎng)絡(luò)的鄰接矩陣，(A3)xy表示節(jié)點(diǎn)vx和vy之間長(zhǎng)度為3的路徑數(shù)目.

2.2 基于機(jī)器學(xué)習(xí)的鏈路預(yù)測(cè)方法

機(jī)器學(xué)習(xí)鏈路預(yù)測(cè)方法使用較多的是隨機(jī)游走算法.文獻(xiàn)[13]提出一種基于隨機(jī)游走的DeepWalk方法，該方法首先在網(wǎng)絡(luò)上等概率隨機(jī)采樣產(chǎn)生大量的隨機(jī)游走序列，之后使用模型對(duì)隨機(jī)游走序列中每個(gè)局部窗口內(nèi)的節(jié)點(diǎn)對(duì)進(jìn)行概率建模.隨機(jī)游走就是從某一特定的節(jié)點(diǎn)出發(fā)，每次游走都從當(dāng)前節(jié)點(diǎn)連接的邊集合中選擇一條，沿著選定的邊移動(dòng)到下一個(gè)節(jié)點(diǎn)的過(guò)程.利用流式的、短的隨機(jī)游走，提出了一個(gè)通用的語(yǔ)言模型用來(lái)探究圖結(jié)構(gòu)，根據(jù)隨機(jī)游走中包含的頂點(diǎn)來(lái)估計(jì)下一個(gè)頂點(diǎn)出現(xiàn)的概率，如公式(4)所示：

Pr(vi|(v1，v2，…，vi-1))

(4)

文獻(xiàn)[14]提出一種與度分布一致的初始資源分布方法，此方法只考慮有限步長(zhǎng)的隨機(jī)游走過(guò)程.從某一節(jié)點(diǎn)x出發(fā)之后開始進(jìn)行隨機(jī)游走，定義πxy(t)為t+1步正好游走到的節(jié)點(diǎn)y的概率，得到基于t步隨機(jī)游走的相似性指標(biāo)，如公式(5)所示：

sxy(t)=qxπxy(t)+qyπyx(t)

(5)

其中q表示節(jié)點(diǎn)的初始化資源分布.通過(guò)大量實(shí)驗(yàn)比較得出由于此方法采用有限步長(zhǎng)的隨機(jī)游走，因此算法復(fù)雜度較低，對(duì)于規(guī)模較大甚至較稀疏的網(wǎng)絡(luò)都很適用.

Node2vec[15]對(duì)隨機(jī)游走方法進(jìn)行了改進(jìn)，在對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行游走遍歷的時(shí)候不使用等概率的隨機(jī)游走，而是使用一種具有回溯并且非均等概率的游走的方式對(duì)網(wǎng)絡(luò)上的節(jié)點(diǎn)進(jìn)行采樣.定義了兩個(gè)參數(shù)p，q指導(dǎo)的二階隨機(jī)游走概率，如公式(6)所示：

(6)

其中αpq(t,x)表示游走的概率，dtx表示節(jié)點(diǎn)x到節(jié)點(diǎn)t的邊數(shù).通過(guò)3個(gè)真實(shí)世界數(shù)據(jù)集中的對(duì)比實(shí)驗(yàn)結(jié)果表明Node2vec-Hadamard方法的結(jié)果要比單純使用DeepWalk-Hadamard的方法效果更好.在隨機(jī)游走過(guò)程中，只能考慮節(jié)點(diǎn)的某一個(gè)鄰居節(jié)點(diǎn)以及獲得一條包含有隨機(jī)連通信息的路徑，對(duì)于鄰居信息的提取不夠完全，對(duì)于連通信息的提取也太過(guò)隨機(jī).

張牧涵等人[16]開發(fā)了一種γ衰減啟發(fā)式理論，將眾多鏈路預(yù)測(cè)相似性指標(biāo)函數(shù)統(tǒng)一在一個(gè)框架中，并證明可以從局部子圖中很好地近似這些相似性指標(biāo)函數(shù)，并基于此理論提出圖神經(jīng)網(wǎng)絡(luò)從局部子圖中學(xué)習(xí)相似性算法的方法.

文獻(xiàn)[17]根據(jù)相似度的性能改進(jìn)，提出一種基于引力的無(wú)監(jiān)督鏈路預(yù)測(cè)方法，通過(guò)集成節(jié)點(diǎn)特征、社區(qū)信息和圖屬性來(lái)減小預(yù)測(cè)空間，從而提高局部和全局預(yù)測(cè)的準(zhǔn)確性.

在現(xiàn)有相關(guān)研究中，對(duì)節(jié)點(diǎn)本身的屬性和網(wǎng)絡(luò)結(jié)構(gòu)信息在鏈路預(yù)測(cè)共同作用考慮不足，且全面與準(zhǔn)確刻畫節(jié)點(diǎn)的自身及空間信息仍有待改善，本文綜合考慮這些問(wèn)題，提出基于CBOW的鏈路預(yù)測(cè)方法—CBOW-SMTV.利用深度優(yōu)先搜索和廣度優(yōu)先搜索分別獲得包含有網(wǎng)絡(luò)連通信息的節(jié)點(diǎn)序列以及節(jié)點(diǎn)鄰居信息的節(jié)點(diǎn)序列，這些節(jié)點(diǎn)序列共同構(gòu)成訓(xùn)練模型的節(jié)點(diǎn)序列庫(kù).CBOW模型通過(guò)考慮節(jié)點(diǎn)序列的順序關(guān)系來(lái)訓(xùn)練節(jié)點(diǎn)序列庫(kù)從而得到節(jié)點(diǎn)的向量表示，以向量的原生特征對(duì)節(jié)點(diǎn)進(jìn)行刻畫，將節(jié)點(diǎn)自身屬性信息映射為節(jié)點(diǎn)向量自身的模長(zhǎng)屬性，將兩節(jié)點(diǎn)的相互關(guān)系映射為節(jié)點(diǎn)向量之間的趨向信息，同時(shí)考慮這兩種信息，提出一種新的相似性指標(biāo)來(lái)度量節(jié)點(diǎn)向量的相似性并進(jìn)行鏈路預(yù)測(cè).

3 模型與算法

本文算法的具體流程圖如圖1所示.首先對(duì)給定的數(shù)據(jù)集進(jìn)行訓(xùn)練集和測(cè)試集的劃分，在訓(xùn)練集構(gòu)造的網(wǎng)絡(luò)中分別使用DFS和BFS搜索策略獲得節(jié)點(diǎn)序列庫(kù)；將節(jié)點(diǎn)序列庫(kù)輸入CBOW模型進(jìn)行訓(xùn)練，得到每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)向量；使用SMTV計(jì)算邊的相似性分?jǐn)?shù)，從而確定鏈路預(yù)測(cè)準(zhǔn)確度AUC的值.

圖1 CBOW-SMTV模型框架Fig.1 CBOW-SMTV model framework

3.1 CBOW模型

CBOW是一種神經(jīng)概率語(yǔ)言模型，廣泛應(yīng)用于自然語(yǔ)言處理領(lǐng)域.該模型使用中心詞的上下文來(lái)預(yù)測(cè)中心詞概率，即在已知當(dāng)前詞wt的上下文：wt-n，wt-n+1，…，wt+n-1，wt+n的前提下預(yù)測(cè)當(dāng)前詞wt的概率，極大地考慮了周圍詞對(duì)于中心詞的影響.模型的結(jié)構(gòu)圖如圖2所示.

圖2 CBOW模型結(jié)構(gòu)圖Fig.2 CBOW model structure

圖2給出了的CBOW模型的網(wǎng)絡(luò)結(jié)構(gòu)，包括3層：輸入層、隱藏層和輸出層.輸入層輸入中心節(jié)點(diǎn)的上下文節(jié)點(diǎn)的初始化向量，這個(gè)向量通常是獨(dú)熱表示(One-hot Representation)，或者是分散表示(Distributed Representation)，這兩種表示都可以對(duì)每個(gè)節(jié)點(diǎn)向量進(jìn)行初始化表示，本文使用分散表示，克服維度災(zāi)難的困擾[18].隱藏層將輸入層輸入的節(jié)點(diǎn)向量做求和累加.輸出層對(duì)應(yīng)一棵哈夫曼樹，這棵哈夫曼樹對(duì)應(yīng)一棵以節(jié)點(diǎn)序列庫(kù)中出現(xiàn)過(guò)的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，以各節(jié)點(diǎn)在節(jié)點(diǎn)序列庫(kù)中出現(xiàn)的次數(shù)為權(quán)值構(gòu)造出來(lái)的二叉樹，采用的編碼策略是將編碼為1的節(jié)點(diǎn)定義為負(fù)類，而將編碼為0的節(jié)點(diǎn)定義為正類.

CBOW作為基于神經(jīng)網(wǎng)絡(luò)的語(yǔ)言模型，對(duì)于中心詞n，其優(yōu)化的目標(biāo)函數(shù)的形式如公式(7)所示：

(7)

3.2 目標(biāo)函數(shù)

對(duì)于節(jié)點(diǎn)序列庫(kù)中出現(xiàn)每一個(gè)節(jié)點(diǎn)都對(duì)應(yīng)輸出的哈夫曼樹的一個(gè)葉子節(jié)點(diǎn)，那么任意一個(gè)葉子節(jié)點(diǎn)一定存在一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑path，且這條路徑唯一存在.假設(shè)這條路徑中包含l個(gè)節(jié)點(diǎn)，則路徑path上存在l-1個(gè)分支，將每個(gè)分支看作一次二分類問(wèn)題，每次分類都會(huì)產(chǎn)生一個(gè)概率，將這些分支產(chǎn)生的概率相乘得到公式(7)需要的p(n|Context(n)).

(8)

公式(8)中：

(9)

(10)

結(jié)合式(7)-式(10)，得到如公式(11)所示對(duì)數(shù)似然函數(shù)表達(dá)式，即為CBOW模型的目標(biāo)函數(shù)：

(11)

簡(jiǎn)記為：

(12)

由于目標(biāo)函數(shù)是對(duì)數(shù)似然函數(shù)，且表示的意義是最大化在上下文出現(xiàn)對(duì)應(yīng)節(jié)點(diǎn)的情況下中心節(jié)點(diǎn)出現(xiàn)的概率，所以優(yōu)化目標(biāo)函數(shù)的目的就是使目標(biāo)函數(shù)最大化，這里使用求最大值的隨機(jī)梯度上升法.使用隨機(jī)梯度上升法得到非葉子節(jié)點(diǎn)對(duì)應(yīng)的更新函數(shù)如下：

(13)

(14)

(15)

3.3 節(jié)點(diǎn)序列選取

使用CBOW訓(xùn)練模型的先導(dǎo)步驟就是構(gòu)造節(jié)點(diǎn)序列庫(kù).傳統(tǒng)構(gòu)造節(jié)點(diǎn)序列的方法是從某一節(jié)點(diǎn)出發(fā)使用隨機(jī)游走產(chǎn)生一條指定長(zhǎng)度的節(jié)點(diǎn)序列，但是使用這一方法產(chǎn)生的序列隨機(jī)性太強(qiáng)，即便是使用有偏向的隨機(jī)游走策略[13].這種節(jié)點(diǎn)序列產(chǎn)生的是具有隨機(jī)性和帶有偏向隨機(jī)性的節(jié)點(diǎn)序列.例如，從網(wǎng)絡(luò)中的某一節(jié)點(diǎn)出發(fā)，為尋找下一節(jié)點(diǎn)而進(jìn)行隨機(jī)游走時(shí)，在此節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)中只隨機(jī)選取一個(gè)，沒有考慮所有鄰居節(jié)點(diǎn)對(duì)于這個(gè)節(jié)點(diǎn)的影響，對(duì)于網(wǎng)絡(luò)節(jié)點(diǎn)的采樣具有一定局限性.本文使用從某一節(jié)點(diǎn)出發(fā)的深度優(yōu)先搜索策略(DFS)結(jié)合廣度優(yōu)先搜索策略(BFS)，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行采樣.

DFS沿著網(wǎng)絡(luò)中的某一節(jié)點(diǎn)v，盡可能深的搜索網(wǎng)絡(luò)分支，當(dāng)節(jié)點(diǎn)v的所在的邊都被搜索過(guò)之后，搜索算法回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那一條邊的起始點(diǎn).這個(gè)過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止.深度優(yōu)先搜索是圖論中的經(jīng)典算法，利用深度優(yōu)先搜索可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮硪簿褪潜疚闹惺褂玫墓?jié)點(diǎn)序列，這個(gè)節(jié)點(diǎn)序列包含整個(gè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的連通路徑信息.BFS是從選定節(jié)點(diǎn)v開始，沿著節(jié)點(diǎn)v向周圍進(jìn)行搜索，如果所有節(jié)點(diǎn)均被訪問(wèn)，則算法終止.在網(wǎng)絡(luò)中對(duì)某一節(jié)點(diǎn)進(jìn)行廣度優(yōu)先搜索，如果搜索深度為1，則得到的是與這個(gè)節(jié)點(diǎn)直接相連的節(jié)點(diǎn)序列，也就是這個(gè)節(jié)點(diǎn)的一階鄰居信息；如果搜索深度為2，則搜索結(jié)果為直接與此節(jié)點(diǎn)相連的節(jié)點(diǎn)序列以及通過(guò)兩條邊間接與此節(jié)點(diǎn)相連的節(jié)點(diǎn)序列，即節(jié)點(diǎn)的一階鄰居信息加上二階鄰居信息.通過(guò)設(shè)定廣度優(yōu)先搜索策略的搜索深度2獲得包含節(jié)點(diǎn)的共2階鄰居信息的節(jié)點(diǎn)序列.通過(guò)BFS和DFS策略，將得到的序列整合在一起，組成包含了網(wǎng)絡(luò)連通性信息和節(jié)點(diǎn)局部信息的節(jié)點(diǎn)序列庫(kù)，使得下一步的訓(xùn)練模型更具有針對(duì)性.

以圖3所示為例，從節(jié)點(diǎn)1出發(fā)，使用深度優(yōu)先搜索得到的節(jié)點(diǎn)序列為：{1,2,4,8,7,6,3}，包含了在此網(wǎng)絡(luò)中從節(jié)點(diǎn)1出發(fā)的連通信息.使用一階廣度優(yōu)先搜索得到的節(jié)點(diǎn)序列為：{1,2,5}，包含節(jié)點(diǎn)的一階鄰居信息.使用二階廣度搜索得到的節(jié)點(diǎn)序列為：{1,2,5,4,6}，包含了節(jié)點(diǎn)的二階鄰居信息.使用這些節(jié)點(diǎn)序列，結(jié)合CBOW模型使用中心節(jié)點(diǎn)的上下文節(jié)點(diǎn)序列信息構(gòu)造節(jié)點(diǎn)向量的特征，能夠更好的提高鏈路預(yù)測(cè)準(zhǔn)確性.

圖3 BFS和DFS的序列搜索策略Fig.3 BFS and DFS sequence search strategy

3.4 SMTV指標(biāo)

在得到包含網(wǎng)絡(luò)連通性信息和節(jié)點(diǎn)局部信息的節(jié)點(diǎn)序列庫(kù)之后，使用CBOW模型訓(xùn)練得到每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的向量表示.網(wǎng)絡(luò)節(jié)點(diǎn)向量化表示之后，使得網(wǎng)絡(luò)節(jié)點(diǎn)具有向量本身的特征，傳統(tǒng)節(jié)點(diǎn)相似性指標(biāo)在進(jìn)行向量度量上不能很好表現(xiàn)向量的本質(zhì)特性.首先，向量化的節(jié)點(diǎn)可以看作是在對(duì)應(yīng)維度的空間中的向量，那么，兩向量的延展特性可以理解為空間趨向，其相似性就可以通過(guò)兩個(gè)向量的余弦相似性進(jìn)行表示，余弦相似性計(jì)算如公式(16)所示：

(16)

其次，向量本身的模長(zhǎng)作為衡量向量大小的原生屬性，也可以度量向量間的相似性.向量模長(zhǎng)的計(jì)算如公式(17)所示：

(17)

結(jié)合向量原生的特征即大小和其演化表現(xiàn)即延展趨向，本文提出了衡量向量化節(jié)點(diǎn)的相似性的指標(biāo)—SMTV，稱為向量自量趨向性(self-measurement tendency of vector，SMTV).該指標(biāo)綜合考慮節(jié)點(diǎn)向量的原生特征及其在空間中的相互關(guān)系，通過(guò)余弦相似性度量?jī)蓚€(gè)節(jié)點(diǎn)向量在向量空間中的趨向情況，兩個(gè)節(jié)點(diǎn)向量之間的余弦相似性越大就認(rèn)為兩向量的趨向性越強(qiáng)，兩節(jié)點(diǎn)的相似性越高.在考慮節(jié)點(diǎn)趨向性的同時(shí)，將節(jié)點(diǎn)自身屬性也加入到相似性度量中，即節(jié)點(diǎn)的“大小”—節(jié)點(diǎn)向量模長(zhǎng).如果兩個(gè)節(jié)點(diǎn)向量不僅在趨向性上相似，并且向量的模長(zhǎng)也非常接近，那么可以肯定這兩個(gè)節(jié)點(diǎn)向量的相似性非常高.SMTV的相似性度量公式如公式(18)所示：

(18)

其中n1，n2表示節(jié)點(diǎn)，v1，v2表示對(duì)應(yīng)的節(jié)點(diǎn)向量，表示可調(diào)參數(shù)，用于調(diào)節(jié)節(jié)點(diǎn)的趨向性和自身大小屬性在相似性度量中的程度.

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

本文選取不同領(lǐng)域的3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，通過(guò)構(gòu)建的CBOW模型對(duì)獲取的節(jié)點(diǎn)序列信息進(jìn)行節(jié)點(diǎn)向量的學(xué)習(xí)與訓(xùn)練，使用SMTV相似性指標(biāo)完成鏈路預(yù)測(cè)，與一些經(jīng)典鏈路預(yù)測(cè)方法如CN、AA、LP和使用帶有回溯和偏向的隨機(jī)游走方法Node2vec-Hadamard進(jìn)行對(duì)比，驗(yàn)證本文模型的可行性和所提出相似性指標(biāo)的有效性.

4.1 數(shù)據(jù)集

本文選用3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)：

·蛋白質(zhì)互作用網(wǎng)絡(luò)Yeast[19]：節(jié)點(diǎn)表示蛋白質(zhì)，邊表示相互作用.該網(wǎng)絡(luò)包含2617個(gè)節(jié)點(diǎn)和11855條邊.屬于稠密網(wǎng)絡(luò)范疇.

·社交網(wǎng)絡(luò)數(shù)據(jù)集Facebook[20]：在Facebook數(shù)據(jù)集中，節(jié)點(diǎn)表示用戶，邊表示兩個(gè)用戶之間的好友關(guān)系，網(wǎng)絡(luò)中包含4039個(gè)節(jié)點(diǎn)和88234條邊.屬于稠密網(wǎng)絡(luò)范疇.

·電力網(wǎng)絡(luò)Power Grid[21]：美國(guó)西部電力網(wǎng)絡(luò).節(jié)點(diǎn)表示變電站或換流站，連邊表示表示它們之間的高壓線.該網(wǎng)絡(luò)包含4941個(gè)節(jié)點(diǎn)和6594條邊.屬于稀疏網(wǎng)絡(luò)范疇.

表1 仿真實(shí)驗(yàn)數(shù)據(jù)集的基本統(tǒng)計(jì)信息Table 1 Basic statistics of the simulated experimental data set

表1總結(jié)上述3個(gè)網(wǎng)絡(luò)的基本統(tǒng)計(jì)特征，其中n表示網(wǎng)絡(luò)中包含的節(jié)點(diǎn)數(shù)，e表示網(wǎng)絡(luò)連邊數(shù)，d表示網(wǎng)絡(luò)直徑，c表示網(wǎng)絡(luò)的聚類系數(shù).

4.2 評(píng)價(jià)指標(biāo)

本文使用衡量鏈路預(yù)測(cè)算法精確度最常用的指標(biāo)—AUC(Area Under the Receiver Operating Characteristic Curve)[22]從整體上衡量算法的精確度.為了對(duì)比實(shí)驗(yàn)的一致性，對(duì)于所有實(shí)驗(yàn)數(shù)據(jù)集均采用抽樣比較的方法得到AUC的值.在抽樣比較的前提下，AUC的含義是在測(cè)試集中隨機(jī)選擇一條邊的分?jǐn)?shù)值比隨機(jī)選擇一條不存在的邊的分?jǐn)?shù)值高的概率.也就是說(shuō)，每次從測(cè)試集中隨機(jī)地抽取一條邊，同時(shí)從不存在的邊中隨機(jī)抽取一條，如果測(cè)試集隨機(jī)邊的分?jǐn)?shù)比不存在隨機(jī)邊的分?jǐn)?shù)大，就加1分；如果相等就加0.5分，如果小于則不加分.獨(dú)立比較m次，有m′次加1分，有m″次加0.5分則AUC定義如公式(19)所示：

(19)

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

本文對(duì)實(shí)驗(yàn)數(shù)據(jù)采用9：1的比例隨機(jī)劃分訓(xùn)練集和測(cè)試集，共進(jìn)行50次獨(dú)立實(shí)驗(yàn)，每次實(shí)驗(yàn)都計(jì)算相應(yīng)的AUC值.將所有得到的AUC值求平均作為最終的實(shí)驗(yàn)結(jié)果.每次獨(dú)立實(shí)驗(yàn)進(jìn)行10000次隨機(jī)抽樣比較預(yù)測(cè)邊與不存在的邊的相似性值計(jì)算AUC.

本文使用CN、AA、LP以及Node2vec-Hadamard 4種方法設(shè)置對(duì)比實(shí)驗(yàn).

通過(guò)對(duì)表2的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析發(fā)現(xiàn)，基于CBOW的SMTV指標(biāo)相比其他4種方法都有提升.

表2 各方法在不同數(shù)據(jù)集下的AUC值Table 2 AUC values for each method indifferent data sets

對(duì)于網(wǎng)絡(luò)規(guī)模相對(duì)較小，包含較少節(jié)點(diǎn)但連邊較多的蛋白質(zhì)相互作用網(wǎng)PPI-Yeast來(lái)說(shuō)，五種方法表現(xiàn)都很好，AUC值均在0.9以上，CN和AA兩個(gè)基于共同鄰居的方法表現(xiàn)相對(duì)一般，都略高于0.9，Node2vec也因?yàn)樾蛄羞x擇的隨機(jī)性，導(dǎo)致AUC值較差.但是采用了二階鄰居信息的LP方法表現(xiàn)突出，達(dá)到了0.96以上，證明在一階鄰居的基礎(chǔ)上考慮二階鄰居，能夠得到更好的效果.因?yàn)樵诠?jié)點(diǎn)序列庫(kù)中包含節(jié)點(diǎn)二階鄰居序列，CBOW-SMTV方法取得了和LP較為接近的結(jié)果，準(zhǔn)確度達(dá)到了0.9637，相比效果最差的Node2vec-Hadamard方法有5.3109%的提高，比效果最好的LP方法提高了0.2497%.

在網(wǎng)絡(luò)規(guī)模較大，節(jié)點(diǎn)數(shù)量和連邊情況都較多的社交網(wǎng)絡(luò)Facebook中，因?yàn)檫B邊數(shù)量眾多，每個(gè)節(jié)點(diǎn)都有很多的鄰居的情況下，就近鄰居的屬性淡化了網(wǎng)絡(luò)連通性的影響，使用CN方法直接對(duì)網(wǎng)絡(luò)鏈路情況進(jìn)行預(yù)測(cè)只能得到0.8513的準(zhǔn)確度，但是在共同鄰居的基礎(chǔ)上考慮節(jié)點(diǎn)度的影響，AA方法的準(zhǔn)確度就可以有較大程度提高.二階鄰居在一定程度上增加了局部的連通性，LP方法相比AA方法也有了一定的提升，Node2vec也因?yàn)椴蓸勇实奶岣撸瑴?zhǔn)確度提高更加明顯.CBOW-SMTV能同時(shí)考慮網(wǎng)絡(luò)的連通性與鄰居信息使得準(zhǔn)確度相比于Node2vec-Hadamard得到一定的提升.

在節(jié)點(diǎn)數(shù)量較多，網(wǎng)絡(luò)連邊較少的PowerGrid網(wǎng)絡(luò)中，傳統(tǒng)的CN，AA，LP方法表現(xiàn)欠佳，AUC都處在0.7以下.本文提出的方法取得較好的鏈路預(yù)測(cè)準(zhǔn)確度，甚至相比于效果最好的Node2vec-Hadamard方法有了9.5714%的提高.對(duì)于同樣使用節(jié)點(diǎn)向量進(jìn)行鏈路預(yù)測(cè)的Node2vec-Hadamard方法，CBOW-SMTV因?yàn)槭褂猛瑫r(shí)結(jié)合網(wǎng)絡(luò)連通信息和節(jié)點(diǎn)鄰居信息的節(jié)點(diǎn)序列，在訓(xùn)練模型的過(guò)程中能得到更具有表現(xiàn)力的節(jié)點(diǎn)向量，利用向量的本質(zhì)特征進(jìn)行相似性度量，所以實(shí)驗(yàn)結(jié)果更好.

綜上，本文提出的CBOW-SMTV方法在不同規(guī)模和類型的網(wǎng)絡(luò)中都能表現(xiàn)出相對(duì)較好的預(yù)測(cè)準(zhǔn)確性.

4.4 參數(shù)敏感性分析

本節(jié)分析CBOW-SMTV模型中的參數(shù)，包括：節(jié)點(diǎn)向量表示的向量維度Dimension、訓(xùn)練節(jié)點(diǎn)序列需要考慮的節(jié)點(diǎn)上下文序列的大小Contextsize和相似性指標(biāo)中的可調(diào)參數(shù).其中Dimension用來(lái)刻畫節(jié)點(diǎn)向量映射空間的復(fù)雜程度，Contextsize用來(lái)衡量周圍節(jié)點(diǎn)對(duì)中心節(jié)點(diǎn)的影響范圍.在PPI-Yeast、Facebook、Power Grid數(shù)據(jù)集下測(cè)試各參數(shù)對(duì)于算法效果的影響，如圖4所示.

在3個(gè)數(shù)據(jù)集中本文采用控制變量法分別測(cè)試了生成節(jié)點(diǎn)向量維度、訓(xùn)練CBOW模型的節(jié)點(diǎn)上下文節(jié)點(diǎn)數(shù)以及相似性指標(biāo)SMTV中的參數(shù)α對(duì)于鏈路預(yù)測(cè)準(zhǔn)確性AUC的影響，默認(rèn)Dimension=100，Contextsize=5，α=0.4；節(jié)點(diǎn)向量維度的調(diào)節(jié)步長(zhǎng)設(shè)置為20，上下文節(jié)點(diǎn)窗口大小步長(zhǎng)設(shè)置為2，比例的步長(zhǎng)設(shè)置為0.1.

圖4 CBOW-SMTV的參數(shù)敏感性分析Fig.4 Parameter sensitivity analysis of CBOW-SMTV

5 總結(jié)與展望

本文中，我們研究使用CBOW模型在網(wǎng)絡(luò)中進(jìn)行鏈路預(yù)測(cè)的方法，提出一種使用神經(jīng)概率語(yǔ)言模型CBOW訓(xùn)練節(jié)點(diǎn)向量，對(duì)準(zhǔn)確衡量節(jié)點(diǎn)向量的相似性，提出了SMTV相似性指標(biāo)，從而進(jìn)行鏈路預(yù)測(cè)的方法.此方法可以有效結(jié)合網(wǎng)絡(luò)的連通信息和節(jié)點(diǎn)的鄰居信息，更加全面地考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位和作用，使向量表達(dá)節(jié)點(diǎn)的信息更加準(zhǔn)確.實(shí)驗(yàn)結(jié)果表明，CBOW-SMTV方法對(duì)PPI-Yeast、Facebook和PowerGrid真實(shí)數(shù)據(jù)集均表現(xiàn)出良好的預(yù)測(cè)效果.

當(dāng)然，本文提出的方法也存在一定的不足之處，雖然使用了多線程對(duì)于模型的訓(xùn)練進(jìn)行了優(yōu)化，但是為了使CBOW-SMTV可以適用于大部分網(wǎng)絡(luò)和各種類型的數(shù)據(jù)集，在對(duì)數(shù)據(jù)集進(jìn)行節(jié)點(diǎn)重新標(biāo)注索引的過(guò)程中仍然耗時(shí)較大，并且在部分計(jì)算過(guò)程中出現(xiàn)大量占用內(nèi)存的問(wèn)題，一定程度上增加了程序執(zhí)行時(shí)間.

后續(xù)的研究將著眼于將方法推廣到包含時(shí)序的網(wǎng)絡(luò)模型中，研究適用于時(shí)序網(wǎng)絡(luò)的基于概率語(yǔ)言模型的鏈路預(yù)測(cè)方法.