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

趙 超 朱福喜,2 劉世超

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

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

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

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

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

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

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

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

0 引 言

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

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

圖1 鏈路預(yù)測(cè)問(wèn)題描述圖

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

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

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

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

1 相關(guān)工作

迄今為止，絕大多數(shù)的鏈路預(yù)測(cè)算法都是基于節(jié)點(diǎn)相似性定義設(shè)計(jì)的。一類(lèi)是基于節(jié)點(diǎn)屬性的相似性指標(biāo)，如果兩個(gè)節(jié)點(diǎn)擁有的共同特征越多[10]，則這兩個(gè)節(jié)點(diǎn)越相似；另一類(lèi)節(jié)點(diǎn)相似性指標(biāo)完全是基于網(wǎng)絡(luò)結(jié)構(gòu)的，稱(chēng)為結(jié)構(gòu)相似性指標(biāo)。結(jié)構(gòu)相似性指標(biāo)可以劃分為基于節(jié)點(diǎn)、基于路徑和混合方法三種類(lèi)型。文獻(xiàn)[5]對(duì)上述3種類(lèi)型的指標(biāo)進(jìn)行了比較，共同鄰居(CN)[11]、Jaccard系數(shù)[12]、AA指標(biāo)[6]和PA指標(biāo)[13]都被歸為基于節(jié)點(diǎn)的標(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ò)中兩個(gè)節(jié)點(diǎn)的鄰居相似，則這兩個(gè)節(jié)點(diǎn)相似，提出了一種量化節(jié)點(diǎn)相似性的方法，這種相似性指標(biāo)可以作為一種候選的精確鏈路預(yù)測(cè)方法。

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

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

2 模型和算法

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

圖2 模型流程圖

2.1 基于概率的隨機(jī)游走

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

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

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

(1)

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

(2)

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

圖3 隨機(jī)游走與基于概率的隨機(jī)游走對(duì)比

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

2.2 SkipGram

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

(3)

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

(4)

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

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

運(yùn)用邏輯回歸進(jìn)行二分類(lèi)，式(4)中的p(u|w)可以表示成如下形式：

(5)

(6)

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

(7)

其中：

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

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

(8)

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

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

輸入： 圖G(V,E)

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

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

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

概率游走長(zhǎng)度t

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

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é)點(diǎn)向量進(jìn)行鏈路預(yù)測(cè)

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

(9)

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

3 實(shí)驗(yàn)和結(jié)果分析

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

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

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

表1 實(shí)驗(yàn)網(wǎng)絡(luò)的拓?fù)湫再|(zhì)

3.2 評(píng)價(jià)方法

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

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

(10)

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

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

(11)

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

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

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

表2 實(shí)驗(yàn)結(jié)果AUC值

表3 實(shí)驗(yàn)結(jié)果Precision值

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

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

3.4 參數(shù)討論

本節(jié)對(duì)模型中的兩個(gè)參數(shù)游走長(zhǎng)度和節(jié)點(diǎn)向量維度進(jìn)行討論。基于概率的隨機(jī)游走長(zhǎng)度默認(rèn)值為20，節(jié)點(diǎn)向量維度默認(rèn)值為50，在討論其中一個(gè)參數(shù)時(shí)，另一個(gè)參數(shù)固定為默認(rèn)值。

3.4.1 基于概率的隨機(jī)游走長(zhǎng)度

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

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

3.4.2 節(jié)點(diǎn)向量維度

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

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

4 結(jié) 語(yǔ)

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

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

后續(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é)點(diǎn)結(jié)構(gòu)特征映射的鏈接預(yù)測(cè)方法[J].計(jì)算機(jī)學(xué)報(bào),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。國(guó)家自然科學(xué)基金項(xiàng)目(61272277)。趙超，碩士，主研領(lǐng)域：社會(huì)網(wǎng)絡(luò)。朱福喜，教授。劉世超，博士。