基于SkipGram模型的鏈路預(yù)測方法

趙 超 朱福喜,2 劉世超

1(武漢大學(xué)計算機學(xué)院 湖北 武漢 430072)

2(漢口學(xué)院計算機科學(xué)與技術(shù)學(xué)院 湖北 武漢 430212)

基于SkipGram模型的鏈路預(yù)測方法

趙 超1朱福喜1,2劉世超1

1(武漢大學(xué)計算機學(xué)院 湖北 武漢 430072)

2(漢口學(xué)院計算機科學(xué)與技術(shù)學(xué)院 湖北 武漢 430212)

現(xiàn)有的基于節(jié)點相似性的鏈路預(yù)測算法，在提升預(yù)測準(zhǔn)確度時往往無法兼顧計算復(fù)雜度。受自然語言概率圖模型在詞向量表征上的運用啟發(fā)，提出一種基于SkipGram模型的鏈路預(yù)測方法。首先提出基于概率的隨機游走方法，通過這種方法得到網(wǎng)絡(luò)節(jié)點的采樣序列；然后結(jié)合SkipGram模型將網(wǎng)絡(luò)節(jié)點映射到一個低維向量空間來降低復(fù)雜度；最終以向量間的距離作為衡量網(wǎng)絡(luò)節(jié)點間相似性的指標(biāo)，進而完成鏈路預(yù)測。通過在6個具有代表性的真實網(wǎng)絡(luò)中進行實驗和比較發(fā)現(xiàn)，提出的模型在預(yù)測準(zhǔn)確度上得到大幅提高。

鏈路預(yù)測 向量表征 SkipGram模型 節(jié)點相似性

0 引 言

現(xiàn)實生活中許多復(fù)雜的系統(tǒng)都能夠使用網(wǎng)絡(luò)來描述，網(wǎng)絡(luò)中的節(jié)點即代表系統(tǒng)中的個體，節(jié)點間的連邊代表個體間的相互關(guān)系。因而，復(fù)雜網(wǎng)絡(luò)逐漸成為分析一個復(fù)雜系統(tǒng)的重要工具。鏈路預(yù)測作為社會網(wǎng)絡(luò)(復(fù)雜網(wǎng)絡(luò)之一)研究中的一個重要分支，受到了來自各個領(lǐng)域的學(xué)者的關(guān)注。例如，蛋白質(zhì)相互作用網(wǎng)絡(luò)[1]、科學(xué)合作網(wǎng)絡(luò)[2]、社交網(wǎng)絡(luò)[3]等都是研究的熱點方向。

鏈路預(yù)測即利用網(wǎng)絡(luò)中已知的節(jié)點信息來預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的節(jié)點之間產(chǎn)生連邊的可能性。如圖1所示，鏈路預(yù)測即利用圖1(a)中的已知節(jié)點信息，來預(yù)測圖1(b)中虛線連邊產(chǎn)生的概率。鏈路預(yù)測有兩個方面的含義，一是預(yù)測網(wǎng)絡(luò)中已經(jīng)產(chǎn)生但還未被發(fā)現(xiàn)的連邊，二是預(yù)測網(wǎng)絡(luò)中目前還未產(chǎn)生但將來可能產(chǎn)生的連邊。

圖1 鏈路預(yù)測問題描述圖

鏈路預(yù)測的傳統(tǒng)做法一般是基于機器學(xué)習(xí)和馬爾科夫鏈的，如文獻[4]使用馬爾科夫鏈來進行自適應(yīng)網(wǎng)絡(luò)中的鏈路預(yù)測；文獻[5]使用馬爾科夫鏈來進行鏈路預(yù)測和網(wǎng)絡(luò)中的路徑分析。此類基于傳統(tǒng)機器學(xué)習(xí)的鏈路預(yù)測方法多半利用了網(wǎng)絡(luò)中節(jié)點的屬性信息，然而節(jié)點的屬性信息既難以獲取且無法保證其可靠性。例如，在目前十分流行的社交網(wǎng)站中，用戶填寫的個人信息一定程度上是虛假的，因而以此構(gòu)建社交網(wǎng)絡(luò)并進行鏈路預(yù)測，其結(jié)果必然是不可靠的。

由于利用網(wǎng)絡(luò)中節(jié)點屬性進行鏈路預(yù)測存在諸多弊端，基于網(wǎng)絡(luò)節(jié)點相似性的算法得以發(fā)展。文獻[6]基于“度小的共同鄰居貢獻大于度大的共同鄰居”的認知提出了AA算法；文獻[7]從網(wǎng)絡(luò)中資源分配的角度出發(fā)提出了RA算法。基于網(wǎng)絡(luò)全局相似性的算法往往計算復(fù)雜度過高，根本無法在較大規(guī)模的網(wǎng)絡(luò)中使用；基于網(wǎng)絡(luò)局部相似性的算法雖然降低了計算復(fù)雜度，然而代價卻是預(yù)測效果的相對下降。

近年來，深度學(xué)習(xí)逐漸成為一個熱門研究方向，它在音頻處理、圖像處理以及自然語言處理等領(lǐng)域的成功運用為解決鏈路預(yù)測問題帶來了啟示。文獻[8]提出了一種神經(jīng)概率語言模型，運用人工神經(jīng)網(wǎng)絡(luò)來學(xué)習(xí)一種分布式表征的詞向量，解決了統(tǒng)計語言模型中常見的維數(shù)災(zāi)難問題，同時使得向量間的相互運算變得有意義。文獻[9]提出了CBOW模型和SkipGram模型，用以大規(guī)模文本連續(xù)性表達的學(xué)習(xí)。

本文受自然語言概率圖模型在詞向量表征上的應(yīng)用啟發(fā)，提出一種基于SkipGram模型的鏈路預(yù)測方法。通過基于概率的隨機游走得到網(wǎng)絡(luò)中的節(jié)點序列，結(jié)合SkipGram模型訓(xùn)練得到節(jié)點對應(yīng)的向量，利用節(jié)點向量間的距離來衡量對應(yīng)節(jié)點間的相似度，以此相似性指標(biāo)來進行鏈路預(yù)測。經(jīng)過在6個真實的網(wǎng)絡(luò)中進行實驗和比較發(fā)現(xiàn)，本文提出的模型相比基準(zhǔn)算法而言，在預(yù)測準(zhǔn)確度上有較大的提升。

1 相關(guān)工作

迄今為止，絕大多數(shù)的鏈路預(yù)測算法都是基于節(jié)點相似性定義設(shè)計的。一類是基于節(jié)點屬性的相似性指標(biāo)，如果兩個節(jié)點擁有的共同特征越多[10]，則這兩個節(jié)點越相似；另一類節(jié)點相似性指標(biāo)完全是基于網(wǎng)絡(luò)結(jié)構(gòu)的，稱為結(jié)構(gòu)相似性指標(biāo)。結(jié)構(gòu)相似性指標(biāo)可以劃分為基于節(jié)點、基于路徑和混合方法三種類型。文獻[5]對上述3種類型的指標(biāo)進行了比較，共同鄰居(CN)[11]、Jaccard系數(shù)[12]、AA指標(biāo)[6]和PA指標(biāo)[13]都被歸為基于節(jié)點的標(biāo)準(zhǔn)；而Katz指標(biāo)[14]、命中次數(shù)[15]、往返次數(shù)[16]、PageRank[17]、SimRank[18]和Blondel指數(shù)[19]都被歸為基于路徑的標(biāo)準(zhǔn)。此外，Leicht等[20]基于假設(shè)——如果網(wǎng)絡(luò)中兩個節(jié)點的鄰居相似，則這兩個節(jié)點相似，提出了一種量化節(jié)點相似性的方法，這種相似性指標(biāo)可以作為一種候選的精確鏈路預(yù)測方法。

除了基于相似性的鏈路預(yù)測算法之外，近年來一些更為復(fù)雜的算法也逐步被提出。Clauset等[21-22]基于層次網(wǎng)絡(luò)結(jié)構(gòu)提出一種鏈接預(yù)測算法，首先使用一個層級隨機圖來近似真實的網(wǎng)絡(luò)數(shù)據(jù)；隨后根據(jù)橫向鏈接概率的深度推斷出節(jié)點的層次結(jié)構(gòu)；最后通過降序排列橫向鏈接概率預(yù)測網(wǎng)絡(luò)中的缺失鏈接。此外，研究人員也做了大量的工作來設(shè)計推薦系統(tǒng)[23]。事實上，向用戶推薦產(chǎn)品的過程可以看作是預(yù)測用戶-商品二分圖中缺失鏈接的過程[24]。值得一提的是，基于能量傳播[25]和熱傳導(dǎo)[26]理論，物理學(xué)家近來提出了一些信息推薦算法。盡管相關(guān)問題還沒有被全面探索過，然而運用經(jīng)典的物理理論仍有可能增加鏈路預(yù)測算法準(zhǔn)確度。

鏈路預(yù)測的研究仍然面臨著許多難題，其一就是目標(biāo)網(wǎng)絡(luò)的稀疏性問題[27]。稀疏網(wǎng)絡(luò)中存在大量的孤立節(jié)點，導(dǎo)致建立合適的統(tǒng)計模型變得非常困難。另一個問題就是真實網(wǎng)絡(luò)往往過于龐大，對算法的效率要求非常高。一般而言，鏈路預(yù)測算法的準(zhǔn)確度與其計算復(fù)雜度是呈正相關(guān)的，準(zhǔn)確度越高通常意味著更高的計算復(fù)雜度。

2 模型和算法

本文提出的模型(如圖2所示)主要包含兩個過程：(1) 使用基于概率的隨機游走獲取網(wǎng)絡(luò)中的節(jié)點序列；(2) 利用SkipGram模型訓(xùn)練節(jié)點對應(yīng)的向量。在獲取網(wǎng)絡(luò)中節(jié)點對應(yīng)的向量之后，采用余弦相似性來度量向量間的距離，進而間接衡量對應(yīng)節(jié)點間的相似度，進行鏈路預(yù)測。

圖2 模型流程圖

2.1 基于概率的隨機游走

文獻[28]所提出的模型第一步就是使用隨機游走來對網(wǎng)絡(luò)節(jié)點進行序列化，隨機游走實際上也是一種概率游走，只不過它在當(dāng)前位置選擇下一步都是等概率的。序列化的節(jié)點就相當(dāng)于語言模型中的句子，大量的句子就構(gòu)成了語料庫。很顯然，不論是一般的隨機游走還是基于概率的隨機游走，其要求都是所得到的節(jié)點序列要能正確反映出網(wǎng)絡(luò)的結(jié)構(gòu)特征。

網(wǎng)絡(luò)中的隨機游走在當(dāng)前節(jié)點選擇下一個節(jié)點時都是等概率的，這也就意味著對于目標(biāo)節(jié)點的鄰居節(jié)點，隨機游走時認為它們都是一樣的。然而事實并非如此，目標(biāo)節(jié)點的多個鄰居節(jié)點之間必然是存在差異的。例如在一個無標(biāo)度圖中，度大的節(jié)點之間和度小的節(jié)點之間未來產(chǎn)生連邊的概率前者要明顯大于后者，倘若使用隨機游走對網(wǎng)絡(luò)進行采樣，則不免最終結(jié)果弱化了度大節(jié)點的作用，節(jié)點序列也就無法準(zhǔn)確地反映網(wǎng)絡(luò)的特征。

基于隨機游走對網(wǎng)絡(luò)節(jié)點進行采樣的不足，本文提出基于概率的隨機游走(簡稱PBWalk)來對無向無權(quán)網(wǎng)絡(luò)中的節(jié)點進行序列化。基于概率的隨機游走根據(jù)當(dāng)前節(jié)點與鄰居節(jié)點的共同鄰居數(shù)目來為鄰居節(jié)點賦予權(quán)值：各鄰居節(jié)點權(quán)值均初始化為1，和當(dāng)前節(jié)點間每增加一個共同鄰居，權(quán)值加1。基于概率的隨機游走計算從當(dāng)前節(jié)點轉(zhuǎn)移到各鄰居節(jié)點的概率為：

(1)

其中x表示游走的當(dāng)前節(jié)點，Γ(x)表示節(jié)點x的鄰居集合，Sx表示節(jié)點x的各鄰居節(jié)點的權(quán)值總和，即：

(2)

如圖3所示，假設(shè)在網(wǎng)絡(luò)中進行游走的當(dāng)前節(jié)點為A，則需要從節(jié)點A的鄰居節(jié)點B、C、D和F中選擇一個作為游走的下一步，圖3中(a)和(b)分別顯示了隨機游走和基于概率的隨機游走從節(jié)點A到鄰居節(jié)點的轉(zhuǎn)移概率。隨機游走選擇鄰居的概率都相同，因而圖3(a)從A轉(zhuǎn)移到B、C、D和F中任何一個節(jié)點的概率都是1/4；基于概率的隨機游走選擇鄰居是依據(jù)共同鄰居數(shù)目來加權(quán)選擇，根據(jù)式(1)計算可知，A轉(zhuǎn)移到節(jié)點C、D和F的概率要大于轉(zhuǎn)移到節(jié)點B的概率。

圖3 隨機游走與基于概率的隨機游走對比

利用基于概率的隨機游走獲取了網(wǎng)絡(luò)的節(jié)點序列之后，將這些節(jié)點序列作為SkipGram模型的輸入，利用SkipGram模型訓(xùn)練得到節(jié)點對應(yīng)的詞向量。

2.2 SkipGram

SkipGram是一個神經(jīng)概率語言模型，它使用一個單詞來預(yù)測句子而不是使用句子上下文來預(yù)測缺失的單詞。句子的上下文由給定單詞左邊和右邊出現(xiàn)的單詞組成。SkipGram語言模型要求極大化單詞出現(xiàn)在上下文中的概率，優(yōu)化的目標(biāo)函數(shù)形式如下：

(3)

其中w表示當(dāng)前詞，Context(w)表示詞w的上下文，C表示語料庫。SkipGram將條件概率函數(shù)p(Context(w)|w)記為如下形式：

(4)

2.3 目標(biāo)函數(shù)求解

SkipGram模型的輸出對應(yīng)一棵Huffman樹，該樹是根據(jù)網(wǎng)絡(luò)節(jié)點在概率游走節(jié)點序列集中出現(xiàn)的頻次構(gòu)造的，樹的葉子節(jié)點對應(yīng)網(wǎng)絡(luò)中的節(jié)點。對于網(wǎng)絡(luò)中的任意節(jié)點，Huffman樹中必存在一條從根節(jié)點到該節(jié)點對應(yīng)葉子的路徑，可以將路徑上的每一個分支看作一次二分類，每一次分類就產(chǎn)生一個概率，將這些概率相乘就得到所求的p(Context(w)|w)。

運用邏輯回歸進行二分類，式(4)中的p(u|w)可以表示成如下形式：

(5)

(6)

綜合式(3)-式(6)即可得到目標(biāo)函數(shù)Ψ：

(7)

其中：

φ(w,u,j) =φ(w,u,j)1+φ(w,u,j)2

使用隨機梯度上升對目標(biāo)函數(shù)進行優(yōu)化，v(w)的更新公式可以表示為：

(8)

其中η表示學(xué)習(xí)率。

本文模型對應(yīng)的算法如下：

輸入： 圖G(V,E)

節(jié)點上下文窗口w

節(jié)點向量維數(shù)d

概率游走總次數(shù)r

概率游走長度t

輸出：節(jié)點向量矩陣Φ

1 for i = 0 to r do

2 O = shuffle(V)

3 for each vi∈O do

4Wvi= PBWalk(G,vi,t)

5 SkipGram(Φ,Wvi,w)

6 end for

7 end for

2.4 使用節(jié)點向量進行鏈路預(yù)測

利用基于概率的隨機游走算法對網(wǎng)絡(luò)中的節(jié)點進行序列化，然后使用SkipGram語言模型結(jié)合神經(jīng)網(wǎng)絡(luò)訓(xùn)練得到網(wǎng)絡(luò)中節(jié)點對應(yīng)的詞向量vj，就可以將計算網(wǎng)絡(luò)中節(jié)點間相似性的問題轉(zhuǎn)化為計算節(jié)點對應(yīng)的詞向量間的距離問題。為了盡量降低算法的時間復(fù)雜度，選擇較為通用的余弦相似性算法來計算網(wǎng)絡(luò)中節(jié)點間的相似度：

(9)

在得到網(wǎng)絡(luò)中所有節(jié)點對應(yīng)的詞向量后，使用式(9)可以計算出測試集中所有節(jié)點間的相似性分?jǐn)?shù)，將相似性分?jǐn)?shù)降序排列成一個列表，取前若干個分?jǐn)?shù)值對應(yīng)的連邊和測試集進行比較，得到這些邊出現(xiàn)的概率。

3 實驗和結(jié)果分析

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

本文選取了不同領(lǐng)域具有代表性的6個網(wǎng)絡(luò)：(1) 蛋白質(zhì)相互作用網(wǎng)絡(luò)(PPI)[29]——該網(wǎng)絡(luò)包含2 617個蛋白質(zhì)、11 855個相互作用關(guān)系。(2) 科學(xué)家合作網(wǎng)絡(luò)(NS)[30]——該網(wǎng)絡(luò)包含1 589位科學(xué)家，其中128位孤立的科學(xué)家并未納入考慮范圍。科學(xué)家合作網(wǎng)絡(luò)的連接情況并不好，它共包含268個聯(lián)通子集，其中最大的聯(lián)通子集卻只有379個節(jié)點。(3) 美國電力網(wǎng)絡(luò)(Grid)[31]——網(wǎng)絡(luò)節(jié)點代表發(fā)電機或基站，網(wǎng)絡(luò)連邊則表示連接節(jié)點間的高壓線路。(4) 政治博客網(wǎng)絡(luò)(PB)[32]——雖然原始網(wǎng)絡(luò)是有向的，但是本文實驗將其視為無向網(wǎng)絡(luò)。(5) 路由器網(wǎng)絡(luò)(INT)[33]。(6) 美國航空網(wǎng)絡(luò)(USAir)[34]——該網(wǎng)絡(luò)表示美國航空運輸系統(tǒng)，包含有332個機場、2 126條航線。

表1總結(jié)了上述6個網(wǎng)絡(luò)的拓撲性質(zhì)，其中N和M分別代表網(wǎng)絡(luò)中的節(jié)點數(shù)和邊數(shù)；Nc表示網(wǎng)絡(luò)中最大聯(lián)通子集的規(guī)模，例如PPI網(wǎng)絡(luò)包含92個聯(lián)通子集，最大聯(lián)通子集包含2 375個節(jié)點；C和d分別表示網(wǎng)絡(luò)的聚集系數(shù)和平均度。

表1 實驗網(wǎng)絡(luò)的拓撲性質(zhì)

3.2 評價方法

為了測試算法的準(zhǔn)確性，將網(wǎng)絡(luò)中已知的邊集隨機分為訓(xùn)練集ET(90%)和測試集EP(10%)兩部分，且ET∪EP=U和ET∩EP=?。在計算相似性分?jǐn)?shù)的時候只能使用訓(xùn)練集ET中的數(shù)據(jù)。

本文采用AUC指標(biāo)[35]和Precision指標(biāo)[36]來對鏈路預(yù)測結(jié)果進行評價，AUC可以看作是隨機選擇的一個不存在的邊比測試集中的邊相似性分?jǐn)?shù)小的概率。AUC計算公式可以表示為：

(10)

其中n表示測試集中的邊的分?jǐn)?shù)值和不存在的邊的分?jǐn)?shù)值獨立比較的次數(shù)，n′表示n次比較中測試集中邊的分?jǐn)?shù)值比不存在的邊分?jǐn)?shù)值大的次數(shù)，n″表示n次比較中測試集中的邊和不存在的邊分?jǐn)?shù)值相等的次數(shù)。

Precision指標(biāo)將實驗結(jié)果的相似性分?jǐn)?shù)按降序排列成一個列表，取前L條記錄，如果其中有n條記錄對應(yīng)的邊出現(xiàn)在測試集中，則Precision的計算公式可以表示為：

(11)

3.3 實驗結(jié)果

本文的實驗結(jié)果都是在對原始數(shù)據(jù)集進行100次隨機劃分形成訓(xùn)練集和測試集，然后取實驗所得數(shù)據(jù)的均值得到的。采用AUC指標(biāo)和Precision指標(biāo)來對實驗結(jié)果進行評價，在AUC評估方法中進行了100 000次隨機抽取比較，Precision取相似性分?jǐn)?shù)列表的前100條記錄與測試集進行比較。

已有的實驗研究[3,7]證明，在基于節(jié)點結(jié)構(gòu)相似性的鏈路預(yù)測算法中，CN、AA和RA算法通常比其他算法具有更好的預(yù)測效果。因此本文將CN、AA和RA算法作為基準(zhǔn)對比方法，同時將文獻[29]中的LsNet2Vec算法(簡記LNV)也納入對比。將本文提出的模型對應(yīng)的算法簡記為PW，實驗結(jié)果如表2和表3所示。

表2 實驗結(jié)果AUC值

表3 實驗結(jié)果Precision值

通過對表2和表3中的實驗數(shù)據(jù)進行分析發(fā)現(xiàn)，PW算法相比傳統(tǒng)的基于節(jié)點相似性的算法，在預(yù)測效果上都有較大的提升。尤其是對于類似INT這種網(wǎng)絡(luò)聚集系數(shù)非常小的網(wǎng)絡(luò)，在傳統(tǒng)的基于節(jié)點相似性的算法都無法準(zhǔn)確預(yù)測的情況下，使用PW算法仍能夠獲得較理想的鏈路預(yù)測結(jié)果。

PW算法相比LNV算法，實驗結(jié)果AUC值和Precision值均有提升。PW算法使用基于概率的隨機游走來對網(wǎng)絡(luò)節(jié)點進行序列化，使游走得到的網(wǎng)絡(luò)節(jié)點序列更加真實地反映了網(wǎng)絡(luò)的拓撲結(jié)構(gòu)性質(zhì)，有助于在使用神經(jīng)網(wǎng)絡(luò)訓(xùn)練語言模型時得到更高質(zhì)量的節(jié)點向量，取得更加良好的預(yù)測效果。

3.4 參數(shù)討論

本節(jié)對模型中的兩個參數(shù)游走長度和節(jié)點向量維度進行討論。基于概率的隨機游走長度默認值為20，節(jié)點向量維度默認值為50，在討論其中一個參數(shù)時，另一個參數(shù)固定為默認值。

3.4.1 基于概率的隨機游走長度

本文選擇游走的長度范圍為[20,120]，同時每次增加10個步長，通過實驗來探討預(yù)測結(jié)果AUC值和基于概率的隨機游走長度間的關(guān)系。觀察圖4中曲線發(fā)現(xiàn)，隨著游走長度的增加，各網(wǎng)絡(luò)中預(yù)測結(jié)果的AUC值整體都是上升的，最終趨近于平穩(wěn)。NS、Grid和INT網(wǎng)絡(luò)較為稀疏，隨著游走長度的增加，網(wǎng)絡(luò)節(jié)點的采樣更加充分，因而AUC值上升的速度更快；相反在較為稠密的網(wǎng)絡(luò)如PB網(wǎng)絡(luò)中，AUC值上升較為緩慢，因為在游走長度不是很大的情況下已經(jīng)足以對網(wǎng)絡(luò)進行充分采樣了。在游走長度增大到一定程度時，網(wǎng)絡(luò)信息已經(jīng)被充分獲取，繼續(xù)增大游走長度不能繼續(xù)提升AUC值。

圖4 游走長度與AUC關(guān)系

3.4.2 節(jié)點向量維度

本文選擇節(jié)點向量維度的變化范圍為[50,200]，每次增加25個維度數(shù)，通過實驗來探討預(yù)測結(jié)果AUC值受節(jié)點向量維度影響的規(guī)律。通過觀察圖5中的曲線發(fā)現(xiàn)，較為稀疏的網(wǎng)絡(luò)如NS、Grid和INT網(wǎng)絡(luò)，隨著節(jié)點向量維度的增加，預(yù)測結(jié)果AUC整體呈上升趨勢。相反在密度較大的網(wǎng)絡(luò)中，隨著節(jié)點向量維度的增加，AUC值逐步下降。在較為稀疏的網(wǎng)絡(luò)中，節(jié)點間分布較為松散，需要用更長的節(jié)點向量去描述網(wǎng)絡(luò)的特征；相反在密度大的網(wǎng)絡(luò)中，較小維度的節(jié)點向量就能夠很好地描述網(wǎng)絡(luò)特征信息，增大節(jié)點向量的維度相反弱化了重要特征信息的表征。

圖5 節(jié)點向量維度與AUC

4 結(jié) 語

本文提出基于概率的隨機游走來進行網(wǎng)絡(luò)節(jié)點序列化，并將游走得到的節(jié)點序列集作為語言模型的語料庫，將網(wǎng)絡(luò)中的節(jié)點作為詞典，使用SkipGram模型訓(xùn)練得到節(jié)點對應(yīng)的節(jié)點向量。最后使用節(jié)點向量來間接計算網(wǎng)絡(luò)中節(jié)點間的相似度，進而進行鏈路預(yù)測，并取得了良好的實驗效果。

當(dāng)然，本文提出的模型也存在一定的不足之處，雖然使用了改進的隨機游走來獲取更加真實反映網(wǎng)絡(luò)特征的節(jié)點序列集，然而在利用節(jié)點序列結(jié)合SkipGram訓(xùn)練節(jié)點向量時并未考慮不同階鄰居的不同作用，因而一定程度上削弱了節(jié)點近鄰的作用。

后續(xù)的研究著眼于思考將模型推廣到有向圖或者帶權(quán)圖中，研究跨不同網(wǎng)絡(luò)的統(tǒng)一適用的模型。

[1] Lei C,Ruan J.A novel link prediction algorithm for reconstructing protein-protein interaction networks by topological similarity[J].Bioinformatics,2013,29(3):355-364.

[2] Yu Q,Long C,Lv Y,et al.Predicting co-author relationship in medical co-authorship networks[J].Plos One,2014,9(7):101-214.

[3] Liben-Nowell D,Kleinberg J.The link prediction problem for social networks[J].Journal of the Association for Information Science and Technology,2007,58(7):1019-1031.

[4] Zhu J,Hong J,Hughes J G.Using Markov Chains for Link Prediction in Adaptive Web Sites[C]//International Conference on Computing in An Imperfect World.Springer-Verlag,2002:60-73.

[5] Saruukkai B R.Link prediction and path analysis using markov chains[J].Computer Networks,2010,33(1-6):377-386.

[6] Adamic L A,Adar E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-230.

[7] Zhou T,Lü L,Zhang Y C.Predicting missing links via local information[J].The European Physical Journal B,2009,71(4):623-630.

[8] Bengio Y,Vincent P,Janvin C.A neural probabilistic language model[J].Journal of Machine Learning Research,2003,3(6):1137-1155.

[9] Mikolov T,Chen K,Corrado G,et al.Efficient Estimation of Word Representations in Vector Space[J].Computer Science,2013,4:124-132.

[10] Shavlik J W.Proceedings of the Fifteenth International Conference on Machine Learning[C]//Fifteenth International Conference on Machine Learning.Morgan Kaufmann Publishers Inc,1998:498-517.

[12] Jaccard P.Lois de distribution florale dans la zone alpine[J].Bulletin De La Societe Vaudoise Des Sciences Naturelles,1902,38(144):69-130.

[13] Barabási A-L,Albert R.Emergence of Scaling in Random Networks[J].Science,1999,286( 5439):509-512.

[14] Cano L,Diaz R.Indirect Influences on Directed Manifolds[J].Mathematics,2015,32(5):10-26.

[15] Wang Jing,Rong Lili.Similarity index based on the information of neighbor nodes for link prediction of complex network[J].Modern Physics Letters B,2013,27(27):793-799.

[16] Bartusiak R,Kajdanowicz T,Wierzbicki A,et al.Cooperation Prediction in GitHub Developers Network with Restricted Boltzmann Machine[M].Intelligent Information and Database Systems,2016.

[17] Paparo G D,Müller M,Comellas F,et al.Quantum Google Algorithm:Construction and Application to Complex Networks[J].Eur.phys.j.plus,2014,129(7):1137-1143.

[18] Jeh G,Widom J.Mining the space of graph properties[C]//Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2004:187-196.

[19] Blondel V,Gajardo A,Heymans M,et al.A measure of similarity between graph vertices[J].Siam Review,2004,46(4):647-666.

[20] Leicht E A,Holme P,Newman M E.Vertex similarity in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,73(2):65-93.

[21] Clauset A,Moore C,Newman M E.Hierarchical structure and the prediction of missing links in networks[J].Nature,2008,453(7191):98-101.

[22] K?lzsch A,Blasius B.Indications of marine bioinvasion from network theory[J].The European Physical Journal B,2011,84(4):601-612.

[23] Cimini G,Medo M,Zhou T,et al.Heterogeneity,quality,and reputation in an adaptive recommendation model[J].The European Physical Journal B,2011,80(2):201-208.

[24] Zhang D,Wu C,Xiong W,et al.Study on topology design for large scale service overlay networks[C]//International Conference on Wireless Communications,NETWORKING and Mobile Computing.IEEE Press,2009:3821-3824.

[25] Pan X,Deng G,Liu J G.Weighted bipartite network and personalized recommendation[J].Physics Procedia,2010,3(5):1867-1876.

[26] Lee S G,Lee J Y,Chmielewski J.Information filtering via weighted heat conduction algorithm[J].Physica A Statistical Mechanics & Its Applications,2011,390(12):2414-2420.

[27] Getoor L.Link mining:a new data mining challenge[J].Acm SIGKDD Explorations Newsletter,2003,5(1):84-89.

[28] 李志宇,梁循,周小平.一種大規(guī)模網(wǎng)絡(luò)中基于節(jié)點結(jié)構(gòu)特征映射的鏈接預(yù)測方法[J].計算機學(xué)報,2016,24(5):149-157.

[29] Liang Z,Xu M,Teng M,et al.Coevolution is a short-distance force at the protein interaction level and correlates with the modular organization of protein networks[J].Febs Letters,2010,584(19):4237-4240.

[30] Newman M E.Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,74(3):92-100.

[31] Watts D J,Strogatz S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):440-442.

[32] Ackland R,Ackland R.Mapping the U.S. Political Blogosphere:Are Conservative Bloggers More Prominent[C]//BlogTalk Downunder 2005 Conference.Berlin:Springer,2005:1-12.

[33] Mahajan R,Spring N,Wetherall D,et al.User-level Internet Path Diagnosis[J].Acm Sigops Operating Systems Review,2003,37(5):106-119.

[34] Surhone L M,Tennoe M T,Henssonow S F,et al.USAir Flight 427[M].Betascript Publishing,2010:165-178.

[35] 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.

[36] Herlocker J L,Konstann J A,Terveen K,et al.Evaluating collaborative filtering recommender systems[J].ACM Transactions on Information Systems,2004,22(1):5-53.

ALINKPREDICTIONMETHODBASEDONSKIPGRAMMODEL

Zhao Chao1Zhu Fuxi1,2Liu Shichao1

1(SchoolofComputerScience,WuhanUniversity,Wuhan430072,Hubei,China)2(SchoolofComputerScienceandTechnology,HankouUniversity,Wuhan430212,Hubei,China)

The existing link prediction algorithm based on node similarity can hardly keep low complexity of the computation when aiming to promote prediction accuracy. Inspired by the application of probabilistic graphical model of natural language, this paper proposes a link prediction method based on SkipGram model. First, the random walk based on probability method was proposed, and the sampling sequence of the network nodes was obtained by this method. Then, the network nodes were mapped to a low dimensional vector space to reduce the complexity by combining the SkipGram model. In the end, the distance between vectors was used as the index to measure the similarity between the nodes of the network to accomplish link prediction. Through experiments and comparison in six representative real networks, the model proposed in this paper can improve the accuracy of prediction a lot.

Link prediction Vector representation SkipGram model Node similarity

TP391

A

10.3969/j.issn.1000-386x.2017.10.043

2016-11-30。國家自然科學(xué)基金項目(61272277)。趙超，碩士，主研領(lǐng)域：社會網(wǎng)絡(luò)。朱福喜，教授。劉世超，博士。