趙宇紅，張 政

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

1 引 言

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

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

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

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

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

2 相關(guān)工作

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

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

2.1.1 基于節(jié)點相似性的鏈路預(yù)測

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

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

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

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

(1)

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

(2)

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

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

(3)

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

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

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

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

(4)

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

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

(5)

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

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

(6)

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

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

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

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

3 模型與算法

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

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

3.1 CBOW模型

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

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

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

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

(7)

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

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

(8)

公式(8)中：

(9)

(10)

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

(11)

簡記為：

(12)

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

(13)

(14)

(15)

3.3 節(jié)點序列選取

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

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

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

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

3.4 SMTV指標(biāo)

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

(16)

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

(17)

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

(18)

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

4 實驗及結(jié)果分析

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

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

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

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

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

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

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

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

4.2 評價指標(biāo)

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

(19)

4.3 實驗結(jié)果

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

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

通過對表2的實驗數(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

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

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

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

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

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

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

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

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

5 總結(jié)與展望

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

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

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