曹 蓉 趙海興 冶忠林

1(青海師范大學(xué)計(jì)算機(jī)學(xué)院 青海 西寧 810008)2(陜西師范大學(xué)計(jì)算機(jī)學(xué)院 陜西 西安 710062)3(青海省藏文信息處理與機(jī)器翻譯重點(diǎn)實(shí)驗(yàn)室 青海 西寧 810008)4(藏文信息處理教育部重點(diǎn)實(shí)驗(yàn)室 青海 西寧 810008)

0 引 言

近年來(lái)，網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問(wèn)題已廣泛受到學(xué)者們的關(guān)注，鏈路預(yù)測(cè)問(wèn)題一直是復(fù)雜網(wǎng)絡(luò)領(lǐng)域中的一個(gè)研究重點(diǎn)，也取得了很多的成就。網(wǎng)絡(luò)中的鏈路預(yù)測(cè)一般指的是通過(guò)某種預(yù)測(cè)算法利用已知網(wǎng)絡(luò)的節(jié)點(diǎn)和結(jié)構(gòu)等信息，來(lái)預(yù)測(cè)下一時(shí)刻網(wǎng)絡(luò)中不相鄰的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生連邊的可能性[1-3]。該預(yù)測(cè)包括未知預(yù)測(cè)和未來(lái)預(yù)測(cè)。常見的鏈路預(yù)測(cè)方法有：基于節(jié)點(diǎn)屬性信息、基于網(wǎng)絡(luò)結(jié)構(gòu)和最大似然估計(jì)法。通常情況下，與節(jié)點(diǎn)的屬性信息相比，更容易獲得網(wǎng)絡(luò)的結(jié)構(gòu)信息，而且網(wǎng)絡(luò)的結(jié)構(gòu)信息也相對(duì)比較可靠。此類方法對(duì)于結(jié)構(gòu)相似的一類網(wǎng)絡(luò)都比較適用，并且從一定程度上減輕了對(duì)不同網(wǎng)絡(luò)需要機(jī)器學(xué)習(xí)來(lái)獲得一些特定的參數(shù)組合。文獻(xiàn)[4]提出一種基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相似性的鏈路預(yù)測(cè)方法，基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相似性指標(biāo)可分為兩類，分別為基于節(jié)點(diǎn)的相似性指標(biāo)和基于路徑的相似性指標(biāo)，并在社會(huì)合作網(wǎng)絡(luò)中進(jìn)行了預(yù)測(cè)，分析了預(yù)測(cè)的效果。

基于網(wǎng)絡(luò)結(jié)構(gòu)的最大似然估計(jì)方法是另一類鏈路預(yù)測(cè)方法。2008年，文獻(xiàn)[5]在層次結(jié)構(gòu)的網(wǎng)絡(luò)中提出了一種運(yùn)用網(wǎng)絡(luò)層次結(jié)構(gòu)的鏈路預(yù)測(cè)方法，并在層次網(wǎng)絡(luò)中進(jìn)行了預(yù)測(cè)，結(jié)果顯示預(yù)測(cè)效果確實(shí)比較明顯。此外，還利用隨機(jī)分塊模型[6-9]對(duì)網(wǎng)絡(luò)中的錯(cuò)誤邊和缺失邊進(jìn)行了預(yù)測(cè)。在文獻(xiàn)[6-9]中首次提到網(wǎng)絡(luò)中存在錯(cuò)誤連邊的概念，即在已知的鏈接中很可能存在著一些錯(cuò)誤的鏈接，如人們對(duì)蛋白質(zhì)相互作用關(guān)系的錯(cuò)誤認(rèn)識(shí)。

隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，計(jì)算機(jī)性能的日益提升，僅對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)屬性的預(yù)測(cè)不能夠真實(shí)精確地反映出目標(biāo)網(wǎng)絡(luò)的特性。目前，尤其針對(duì)大規(guī)模網(wǎng)絡(luò)，還沒(méi)有較好的預(yù)測(cè)算法。近幾年，深度學(xué)習(xí)在表示學(xué)習(xí)網(wǎng)絡(luò)的特征提取上取得了非常巨大的進(jìn)展[10]?；诖朔椒ǖ膯l(fā)，我們進(jìn)一步關(guān)注到了網(wǎng)絡(luò)表示學(xué)習(xí)算法。網(wǎng)絡(luò)表示學(xué)習(xí)又叫作網(wǎng)絡(luò)特征學(xué)習(xí)，它是機(jī)器學(xué)習(xí)領(lǐng)域里一個(gè)非常重要的研究領(lǐng)域，該方法的目標(biāo)是通過(guò)對(duì)目標(biāo)網(wǎng)絡(luò)的特征進(jìn)行學(xué)習(xí)，將網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)表示為一個(gè)低維向量[11]。網(wǎng)絡(luò)表示學(xué)習(xí)方法可以更好地幫助我們理解節(jié)點(diǎn)之間的語(yǔ)義關(guān)系，且能更進(jìn)一步緩解由于網(wǎng)絡(luò)稀疏性帶來(lái)的不便?，F(xiàn)存的大部分網(wǎng)絡(luò)表示學(xué)習(xí)算法都是基于網(wǎng)絡(luò)結(jié)構(gòu)的。例如DeepWalk[12]算法，該算法起源于Word2Vec[13-15]算法。DeepWalk算法利用隨機(jī)游走獲得當(dāng)前節(jié)點(diǎn)的上下文，然后將上下文節(jié)點(diǎn)輸入到神經(jīng)網(wǎng)絡(luò)中進(jìn)行訓(xùn)練。

然而，現(xiàn)實(shí)世界中，網(wǎng)絡(luò)的一個(gè)節(jié)點(diǎn)通常包含了非常豐富的信息。例如，在引文網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)中含有該節(jié)點(diǎn)的論文標(biāo)題、類別屬性等。假設(shè)，兩個(gè)節(jié)點(diǎn)的文本內(nèi)容中含有較多的共現(xiàn)詞語(yǔ)，那么，這兩個(gè)節(jié)點(diǎn)屬于同一類別的概率也較大。另外，已有研究證明了，DeepWalk算法其實(shí)質(zhì)為矩陣分解，分解的目標(biāo)矩陣記為M?；诖?，本文提出一種基于網(wǎng)絡(luò)節(jié)點(diǎn)文本增強(qiáng)的鏈路預(yù)測(cè)方法。它將網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)的文本屬性信息結(jié)合起來(lái)，該算法也是基于DeepWalk算法之上。與DeepWalk算法不同的是，在目標(biāo)矩陣M的分解上，考慮了網(wǎng)絡(luò)節(jié)點(diǎn)的文本屬性信息。因此，本文提出的TELP算法旨在通過(guò)對(duì)目標(biāo)矩陣的分解的同時(shí)融入了網(wǎng)絡(luò)節(jié)點(diǎn)的文本內(nèi)容，使得得到的網(wǎng)絡(luò)表示中既含有了網(wǎng)絡(luò)的結(jié)構(gòu)屬性，又有了網(wǎng)絡(luò)節(jié)點(diǎn)的文本屬性。最后，通過(guò)三個(gè)數(shù)據(jù)集實(shí)驗(yàn)仿真，并將仿真結(jié)果與現(xiàn)存的眾多鏈路預(yù)測(cè)算法相比較，實(shí)驗(yàn)證實(shí)本文算法取得了較好的預(yù)測(cè)效果。

1 相關(guān)工作

常見的鏈路預(yù)測(cè)算法主要是基于節(jié)點(diǎn)相似性的預(yù)測(cè)算法，該類算法包括基于局部信息的相似性指標(biāo)、基于路徑的相似性指標(biāo)以及基于隨機(jī)游走的相似性指標(biāo)。

基于局部相似性指標(biāo)的方法通常指的是基于共同鄰居CN(Common Neighbors)的相似性指標(biāo)[16]。CN指標(biāo)可以理解為，若兩個(gè)節(jié)點(diǎn)擁有很多的共同鄰居，則這兩個(gè)節(jié)點(diǎn)相似，它們的共同鄰居數(shù)越多，相似性也就越高。考慮節(jié)點(diǎn)的共同鄰居，以及兩端節(jié)點(diǎn)的度對(duì)網(wǎng)絡(luò)的影響，可將其細(xì)分為6種相似性指標(biāo)，分別為：余弦相似性(Salton)指標(biāo)[17]、Jaccard指標(biāo)[18]、Sorenson指標(biāo)[19]、大度節(jié)點(diǎn)有利指標(biāo)HPI(Hub Promoted Index)[20]、大度節(jié)點(diǎn)不利指標(biāo)HDI(Hub Depressed Index)[21]和(LHN-I)指標(biāo)[22]。若考慮共同鄰居節(jié)點(diǎn)的度的信息，又可分為AA(Adamic-Adar)指標(biāo)[23]和資源分配RA(Resource Allocation)指標(biāo)[21]兩類指標(biāo)。

基于局部相似性的算法是一種比較直觀、簡(jiǎn)單的算法，其計(jì)算復(fù)雜度相對(duì)較低，然而該方法只關(guān)注目標(biāo)節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)的屬性信息，并沒(méi)有完全挖掘出整個(gè)網(wǎng)絡(luò)所攜帶的豐富的信息，導(dǎo)致節(jié)點(diǎn)相似性分?jǐn)?shù)的分布過(guò)于集中，節(jié)點(diǎn)對(duì)與節(jié)點(diǎn)對(duì)之間的區(qū)分度太低，從而導(dǎo)致算法的預(yù)測(cè)精度受到了一定的限制。但是，該類算法的優(yōu)點(diǎn)是可以在大規(guī)模網(wǎng)絡(luò)中進(jìn)行鏈路預(yù)測(cè)。

CN指標(biāo)本質(zhì)上可以看成是二階路徑指標(biāo)，周濤等[24]在基于共同鄰居的相似性指標(biāo)的基礎(chǔ)上，考慮了三階路徑的因素，提出了基于局部路徑的相似性指標(biāo)。該類指標(biāo)有3個(gè)，分別為局部路徑指標(biāo)、Katz指標(biāo)[25]和LHN-II指標(biāo)[22]。Katz指標(biāo)考慮了網(wǎng)絡(luò)的全部路徑，其定義為：

al(Al)xy

基于路徑的鏈路預(yù)測(cè)算法考慮了節(jié)點(diǎn)之間的路徑信息，但是由于在節(jié)點(diǎn)之間存在多條路徑，且路徑搜索算法具有較大的計(jì)算復(fù)雜度，因此，導(dǎo)致了這類算法計(jì)算代價(jià)大。這類算法的優(yōu)點(diǎn)是考慮了所有的路徑信息，因此，在鏈路預(yù)測(cè)任務(wù)重通常具有很好的性能。

基于隨機(jī)游走的相似性指標(biāo)可以分為基于網(wǎng)絡(luò)全局的隨機(jī)游走指標(biāo)和基于局部的隨機(jī)游走指標(biāo)兩大類，基于全局的隨機(jī)游走指標(biāo)主要包括平均通勤時(shí)間ACT(Average Commute Time)[26]、基于隨機(jī)游走的余弦相似性(Cos+)指標(biāo)[27]、有重啟的隨機(jī)游走指標(biāo)RWR(Random Walk With Restart)[28]、SimRank指標(biāo)(SimR)[29]。基于全局的隨機(jī)游走指標(biāo)往往計(jì)算復(fù)雜度都比較高，很難應(yīng)用于大規(guī)模網(wǎng)絡(luò)中。劉偉平[30]等提出了一種基于網(wǎng)絡(luò)局部隨機(jī)游走的相似性LRW指標(biāo)(Local Random Walk)，該指標(biāo)不同于全局隨機(jī)游走的指標(biāo)，它只考慮了有限部署的隨機(jī)游走過(guò)程。它包括基于局部隨機(jī)游走指標(biāo)和有疊加效應(yīng)的局部隨機(jī)游走SRW指標(biāo)(Superposed Random Walk)兩種指標(biāo)。

基于隨機(jī)游走的鏈路預(yù)測(cè)算法可被高效地應(yīng)用于鏈路預(yù)測(cè)任務(wù)中，且具有很高的精度。只是這類算法僅僅是基于節(jié)點(diǎn)之間的隨機(jī)游走，并沒(méi)有考慮節(jié)點(diǎn)之間的結(jié)構(gòu)特征屬性。如果首先挖掘節(jié)點(diǎn)之間的結(jié)構(gòu)特征，之后再基于該結(jié)構(gòu)特征進(jìn)行鏈路預(yù)測(cè)研究，那么該算法的預(yù)測(cè)性能就會(huì)得到較大的提升。

當(dāng)然，還存在一些其他的相似性算法，比如基于矩陣森林理論的矩陣森林指數(shù)MFI算法(Matrix Forest Index)[31]、自洽轉(zhuǎn)移相似性算法[32]等。

雖然目前也有將文本信息融入鏈路預(yù)測(cè)的一些算法，但是這些算法是將文本中的詞語(yǔ)作為一類特殊的節(jié)點(diǎn)考慮，其實(shí)質(zhì)是構(gòu)建異構(gòu)網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測(cè)。本文通過(guò)將文本信息轉(zhuǎn)化為文本特征矩陣，之后通過(guò)分解網(wǎng)絡(luò)特征矩陣步驟，將文本特征的影響因子融入到網(wǎng)絡(luò)節(jié)點(diǎn)的表示向量中。文本算法的實(shí)質(zhì)是基于神經(jīng)矩陣分解模型挖掘網(wǎng)絡(luò)結(jié)構(gòu)特征，之后再基于該特征向量進(jìn)行鏈路預(yù)測(cè)。因此，與傳統(tǒng)的基于異構(gòu)網(wǎng)絡(luò)的鏈路預(yù)測(cè)算法有著本質(zhì)的區(qū)別。本文使用的基于神經(jīng)矩陣分解的鏈路預(yù)測(cè)算法也異于本節(jié)中介紹的3類基于節(jié)點(diǎn)相似性的鏈路預(yù)測(cè)算法，是一種簡(jiǎn)單高效的鏈路預(yù)測(cè)算法。與該3類鏈路預(yù)測(cè)算法最大的區(qū)別是先進(jìn)行了網(wǎng)絡(luò)結(jié)構(gòu)特征挖掘，而非直接利用網(wǎng)絡(luò)節(jié)點(diǎn)的連邊信息直接進(jìn)行鏈路預(yù)測(cè)。

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

已知目標(biāo)網(wǎng)絡(luò)G=(V,E)，其中，點(diǎn)集為V，邊集為E，相關(guān)的節(jié)點(diǎn)文本信息矩陣為T∈Rft×|V|，ft為文本特征的維度。本文提出一種基于文本增強(qiáng)的鏈路預(yù)測(cè)方法(TELP)，該方法不僅結(jié)合了網(wǎng)絡(luò)的結(jié)構(gòu)特征，而且也考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)的文本屬性信息，從而更有效地挖掘到目標(biāo)網(wǎng)絡(luò)的結(jié)構(gòu)特征，以便更好地理解目標(biāo)網(wǎng)絡(luò)。

2.1 基于矩陣分解的DeepWalk算法

DeepWalk算法是由Perozzi等[12]提出的一種基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示模型，該模型是一個(gè)淺層的三層神經(jīng)網(wǎng)絡(luò)，它由輸入層、投影層和輸出層組成。DeepWalk提供了兩種實(shí)現(xiàn)模型，即CBOW(Continuous Bag of Words)模型和Skip-Gram模型。DeepWalk使用了層次化的softmax函數(shù)和負(fù)采樣方法來(lái)優(yōu)化模型的訓(xùn)練過(guò)程，相比于語(yǔ)言模型中的Word2Vec算法，DeepWalk算法將隨機(jī)游走的過(guò)程中生成的節(jié)點(diǎn)序列當(dāng)作句子，其中的節(jié)點(diǎn)看作文本中的詞，來(lái)訓(xùn)練和學(xué)習(xí)目標(biāo)網(wǎng)絡(luò)的節(jié)點(diǎn)向量表示。由于DeepWalk算法其實(shí)質(zhì)為矩陣分解，因此，DeepWalk算法的目標(biāo)函數(shù)為：

(1)

Yang等[33]證明了DeepWalk算法實(shí)質(zhì)上等價(jià)于分解目標(biāo)網(wǎng)絡(luò)的矩陣M，因此，在文獻(xiàn)[33]和文獻(xiàn)[34]中定義了式(1)中的M如下：

Mij=log2(ei(A+A2+A3+…+At)j/t)

(2)

(3)

式中：A表示PageRank的轉(zhuǎn)移矩陣；ei表示從節(jié)點(diǎn)i開始隨機(jī)游走時(shí)的初始狀態(tài)，它是一個(gè)第i行為1，剩余行均為0的eiAt維行向量，ejAt中第j列值為從節(jié)點(diǎn)vi在t步之內(nèi)隨機(jī)游走到節(jié)點(diǎn)vj的概率的大小。j則表示節(jié)點(diǎn)vj在隨機(jī)游走t步內(nèi)出現(xiàn)在節(jié)點(diǎn)vi周圍的次數(shù)。

從式(2)可以看出，當(dāng)滑動(dòng)窗口t不斷增大時(shí)，DeepWalk算法計(jì)算矩陣M的復(fù)雜度達(dá)到了O(|V|3)。

2.2 基于文本信息的DeepWalk算法

DeepWalk算法單純的使用網(wǎng)絡(luò)的結(jié)構(gòu)特征來(lái)訓(xùn)練節(jié)點(diǎn)的向量，文獻(xiàn)[34]在網(wǎng)絡(luò)結(jié)構(gòu)特征的基礎(chǔ)上引入節(jié)點(diǎn)的文本信息，提出了基于文本信息的DeepWalk算法，簡(jiǎn)稱TADW(Text Associated DeepWalk)算法[34]。該算法使用誘導(dǎo)矩陣補(bǔ)全I(xiàn)MC(Inductive Matrix Completion)算法對(duì)M矩陣進(jìn)行分解，同時(shí)將目標(biāo)網(wǎng)絡(luò)節(jié)點(diǎn)的文本屬性信息引入到網(wǎng)絡(luò)表示學(xué)習(xí)中。由于log2M矩陣中含有大量的非零元，且大部分真實(shí)網(wǎng)絡(luò)通常是稀疏的，即O(E)=O(V)，這使得算法的復(fù)雜度上升。因此，在式(2)中分解矩陣M時(shí)，可去掉log進(jìn)行分解。在TADW算法中，考慮了算法的時(shí)間和空間效率等因素，直接對(duì)目標(biāo)矩陣M進(jìn)行分解，最終得到的分解的目標(biāo)矩陣為:M=(A+A2)/2。通過(guò)TADW算法，使得矩陣分解的時(shí)間復(fù)雜度從原來(lái)的O(|V|3)大大地降低到O(|V|2)。因此，在TADW算法很大地降低了矩陣分解的時(shí)間復(fù)雜度。在目標(biāo)矩陣M的分解過(guò)程中，使得下式達(dá)到最?。?/p>

(4)

本文中，也擬采用網(wǎng)絡(luò)表示學(xué)習(xí)中矩陣分解的目標(biāo)矩陣為：M=(A+A2)/2。

2.3 基于文本增強(qiáng)的鏈路預(yù)測(cè)算法

通過(guò)觀察TADW算法的網(wǎng)絡(luò)中節(jié)點(diǎn)表示學(xué)習(xí)，發(fā)現(xiàn)它不但考慮了目標(biāo)節(jié)點(diǎn)周圍的網(wǎng)絡(luò)結(jié)構(gòu)信息，而且也將節(jié)點(diǎn)的相關(guān)文本信息作為輸入，并通過(guò)深度學(xué)習(xí)的方法不斷結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)相關(guān)的文本信息，訓(xùn)練得到節(jié)點(diǎn)的最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)的特征向量表示。通過(guò)實(shí)驗(yàn)表明，使用TADW算法訓(xùn)練出網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)在向量空間上的分布，這也可以很好地計(jì)算目標(biāo)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)不僅在網(wǎng)絡(luò)結(jié)構(gòu)上而且在文本內(nèi)容上潛在的相似性。受到TADW模型的啟發(fā)，本文提出了基于網(wǎng)絡(luò)節(jié)點(diǎn)文本增強(qiáng)的鏈路預(yù)測(cè)算法。首先基于TADW算法并結(jié)合了與目標(biāo)網(wǎng)絡(luò)相關(guān)的文本矩陣T分解目標(biāo)矩陣M，得到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的向量表示，然后根據(jù)余弦相似性算法，計(jì)算出任意兩個(gè)節(jié)點(diǎn)的相似度，從而構(gòu)建出最終的相似度矩陣。另外，本文算法通過(guò)TADW框架訓(xùn)練每個(gè)節(jié)點(diǎn)的表示向量，故本文的算法復(fù)雜度主要來(lái)自于訓(xùn)練TADW模型。由于TADW算法的訓(xùn)練復(fù)雜度為O(|V|2)，因此，本文提出的TELP算法的時(shí)間復(fù)雜度為O(|V|2)。

定義1網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)i、j之間的網(wǎng)絡(luò)結(jié)構(gòu)相似性為：

(5)

本文中，基于文本增強(qiáng)的鏈路預(yù)測(cè)TELP算法的具體框架如圖1所示。

圖1 基于網(wǎng)絡(luò)節(jié)點(diǎn)文本增強(qiáng)的鏈路預(yù)測(cè)算法框架

本文的算法主要由網(wǎng)絡(luò)特征構(gòu)建模塊、網(wǎng)絡(luò)表示學(xué)習(xí)模塊、相似度矩陣構(gòu)建模塊、鏈路預(yù)測(cè)模塊4個(gè)模塊組成，每個(gè)模塊的主要任務(wù)處理如下所示：

1) 網(wǎng)絡(luò)特征構(gòu)建模塊：將目標(biāo)網(wǎng)絡(luò)轉(zhuǎn)化成鄰接矩陣的形式，然后使得矩陣M=(A+A2)/2為網(wǎng)絡(luò)的特征矩陣。

3) 相似度矩陣構(gòu)建模塊：對(duì)得到的目標(biāo)矩陣WT矩陣中的每一行、每一列，利用定義1的余弦相似度算法計(jì)算任意節(jié)點(diǎn)的相似度，得到目標(biāo)網(wǎng)絡(luò)的相似度矩陣S=[Sij],其中0≤i≤|V|-1,0≤j≤|V|-1。

4) 鏈路預(yù)測(cè)模塊：將WT矩陣分為訓(xùn)練集和測(cè)試集，使用AUC評(píng)價(jià)指標(biāo)，評(píng)估本文算法的鏈路預(yù)測(cè)性能。

本文算法的主要流程由以上4個(gè)模塊組成，為了更進(jìn)一步詳細(xì)展示本文算法，下面提供本文算法的偽代碼：

輸入：

目標(biāo)網(wǎng)絡(luò)G的鄰接矩陣:A

數(shù)據(jù)集的訓(xùn)練率:training ratio

向量表示長(zhǎng)度:k

輸出：AUC

1. 計(jì)算鄰接矩陣A:A=[aij]

if(i,j)∈E，aij=1/di

elseaij=0

2. 網(wǎng)絡(luò)特征矩陣M:

M=(A+A2)/2

3.1 獲取每個(gè)節(jié)點(diǎn)的標(biāo)題

3.2 刪除標(biāo)題中的停用字

3.3 為每個(gè)詞賦一個(gè)向量，并構(gòu)建詞表D

3.4 使用循環(huán)控制生成文本特征矩陣T|V|×ft:

(1) 若標(biāo)題中的詞出現(xiàn)在詞表D中：

將該位置設(shè)置為1，否則設(shè)置為0

(2) 直到最后一條標(biāo)題

4. 使用IMC算法分解:M

(W,H,time)=IMC(E,M,T,k…)

5. 將WT作為目標(biāo)網(wǎng)絡(luò)的節(jié)點(diǎn)向量:

[ei]←WT

6. 構(gòu)建相似度矩陣S:

S=[Sij]=sim(i,j)

7. 計(jì)算測(cè)試集的AUC值:

7.1 將網(wǎng)絡(luò)G分成測(cè)試集和訓(xùn)練集:

7.2 AUC←[training set,testing set]

結(jié)束

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

3.1 數(shù)據(jù)集和實(shí)驗(yàn)參數(shù)設(shè)置

本文所采用的三個(gè)數(shù)據(jù)集均為真實(shí)的科研合作網(wǎng)絡(luò)，通過(guò)比較本文所提出的算法和現(xiàn)存的多種鏈路預(yù)測(cè)算法，進(jìn)一步驗(yàn)證本文所提算法的有效性。本文所使用的數(shù)據(jù)集分別為Citeseer數(shù)據(jù)集、DBLP數(shù)據(jù)集和Cora數(shù)據(jù)集，有關(guān)數(shù)據(jù)集的詳細(xì)信息如表1所示。

表1 數(shù)據(jù)集描述

通過(guò)表1可以看出，這三個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)數(shù)大概都在3 000個(gè)左右，然而這三個(gè)網(wǎng)絡(luò)中的邊數(shù)卻大不相同。其中，DBLP數(shù)據(jù)集中的邊數(shù)最多，幾乎為Citeseer和Cora 中邊數(shù)的7倍多。顯然，在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)幾乎相同的情況下，網(wǎng)絡(luò)中的連邊數(shù)S直接影響了該網(wǎng)絡(luò)的稠密度、平均度以及平均聚類系數(shù)的大小。正因如此，三個(gè)數(shù)據(jù)集中，相比其他兩個(gè)網(wǎng)絡(luò)，DBLP網(wǎng)絡(luò)的密度最大，平均度也最大，網(wǎng)絡(luò)直徑和平均聚類系數(shù)也最大。

在本文中使用的Citeseer、DBLP和Cora三個(gè)引文網(wǎng)絡(luò)數(shù)據(jù)集不僅包含了節(jié)點(diǎn)之間的連邊關(guān)系，同時(shí)也包含了每個(gè)節(jié)點(diǎn)的標(biāo)題文本，該節(jié)點(diǎn)文本為引文網(wǎng)絡(luò)中的論文題目。本文引入的TELP算法不僅建模了節(jié)點(diǎn)之間的連接關(guān)系，同時(shí)也建模了節(jié)點(diǎn)與節(jié)點(diǎn)文本之間的關(guān)系。因此，TELP算法訓(xùn)練得到的節(jié)點(diǎn)表示向量中既含有連接因子，也含有文本影響因子。

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

鏈路預(yù)測(cè)算法精確度的衡量指標(biāo)通常有AUC[32]、精確度和排序分等。本文采用的是AUC評(píng)價(jià)指標(biāo)來(lái)衡量本文算法的準(zhǔn)確性。AUC指標(biāo)將實(shí)驗(yàn)數(shù)據(jù)隨機(jī)地獨(dú)立劃分為測(cè)試集和訓(xùn)練集兩部分，其中90%作為訓(xùn)練集，10%作為數(shù)據(jù)集。通過(guò)在測(cè)試集中隨機(jī)地選擇一條已經(jīng)存在的連邊的分?jǐn)?shù)值比一條不存在的連邊的分?jǐn)?shù)值高的概率。即，每次隨機(jī)地從測(cè)試集中選一條連邊，再?gòu)牟淮嬖诘倪B邊中隨機(jī)選一條。若測(cè)試集中的連邊分?jǐn)?shù)值大于不存在連邊的分?jǐn)?shù)，就加1分;若兩者相等就加0.5分。通過(guò)獨(dú)立地比較n次，若有n′次測(cè)試集中的連邊分?jǐn)?shù)值比不存在連邊的分?jǐn)?shù)值大，有n″次兩者分?jǐn)?shù)值相等，則AUC的值可以表示為：

AUC=(n′+n″)/n

(6)

一般而言，AUC評(píng)價(jià)指標(biāo)的值應(yīng)至少大于0.5,但不超過(guò)1。訓(xùn)練集越大，對(duì)應(yīng)的AUC的值越高，算法的精確度也就越高。

3.3 對(duì)比分析

本文將目標(biāo)網(wǎng)絡(luò)的鄰接矩陣分解為三個(gè)低維矩陣的乘積：M=WT×H×TT。然后基于余弦相似度方法構(gòu)建網(wǎng)絡(luò)的相似度矩陣，最后在Citeseer、DBLP和Cora三個(gè)數(shù)據(jù)集上做了仿真實(shí)驗(yàn)。為了進(jìn)一步驗(yàn)證本文所提算法的有效性，用所列出的現(xiàn)存的多種預(yù)測(cè)方法與我們所提出的方法進(jìn)行了對(duì)比。在本實(shí)驗(yàn)中，設(shè)置訓(xùn)練比例分別為0.7、0.75、0.8、0.85、0.9和0.95，以及經(jīng)過(guò)訓(xùn)練所得到的向量長(zhǎng)度為200，實(shí)驗(yàn)結(jié)果如表2所示。

表2 Citesser、DBLP和Cora數(shù)據(jù)集上的鏈路預(yù)測(cè)結(jié)果

從表2中看到，本文所提出的TELP算法和現(xiàn)存的多種常用的鏈路預(yù)測(cè)方法進(jìn)行了比較，通過(guò)對(duì)實(shí)驗(yàn)結(jié)果分析發(fā)現(xiàn)MFI算法在Citeseer、DBLP和Cora三個(gè)數(shù)據(jù)集上都表現(xiàn)出了最優(yōu)的性能，Katz算法在這三個(gè)數(shù)據(jù)集上的表現(xiàn)基本相同，尤其在Citeseer數(shù)據(jù)集上表現(xiàn)較優(yōu)。本文提出的TELP算法其性能也優(yōu)于表2中剩余的多種算法，尤其是在Citeseer數(shù)據(jù)集上表現(xiàn)得比較明顯。根據(jù)上述分析可知:本文所提出來(lái)的TELP算法的性能優(yōu)于現(xiàn)存的絕大多數(shù)鏈路預(yù)測(cè)算法，是因?yàn)楸疚乃惴ㄊ褂昧嘶跍\層神經(jīng)網(wǎng)絡(luò)的方法，并且充分地考慮了已知網(wǎng)絡(luò)的結(jié)構(gòu)和豐富的文本信息；通過(guò)對(duì)目標(biāo)網(wǎng)絡(luò)進(jìn)行無(wú)監(jiān)督學(xué)習(xí)來(lái)訓(xùn)練網(wǎng)絡(luò)的節(jié)點(diǎn)表示向量，有助于快速地從目標(biāo)網(wǎng)絡(luò)中提取信息，便于更加準(zhǔn)確和深入地理解學(xué)習(xí)目標(biāo)網(wǎng)絡(luò)呈現(xiàn)其特征。

3.4 度分布

度分布是對(duì)一個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)的總體描述，網(wǎng)絡(luò)的度分布通常指的是網(wǎng)絡(luò)中節(jié)點(diǎn)的度的概率分布?，F(xiàn)存的絕大多數(shù)復(fù)雜網(wǎng)絡(luò)都具有無(wú)標(biāo)度性，即其度分布服從冪律分布的網(wǎng)絡(luò)?？梢钥闯?，研究網(wǎng)絡(luò)的度分布指數(shù)可以基本確定一個(gè)網(wǎng)絡(luò)的類型。通過(guò)研究復(fù)雜網(wǎng)絡(luò)的度分布，可以幫我們更好地認(rèn)識(shí)、分析目標(biāo)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和動(dòng)力學(xué)行為等?？梢姡确植际菑?fù)雜網(wǎng)絡(luò)中的一個(gè)非常重要的參數(shù)，對(duì)網(wǎng)絡(luò)的度分布研究也具有十分重要的研究?jī)r(jià)值。本文通過(guò)Matlab編程計(jì)算出Citeseer、DBLP和Cora三個(gè)數(shù)據(jù)集網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的度分布及頻率,如圖2所示。

(a) Citeseer 數(shù)據(jù)集

(b) DBLP數(shù)據(jù)集

(c) Cora數(shù)據(jù)集圖2 在Citeseer、DBLP和Cora數(shù)據(jù)集上的度

圖2中的橫坐標(biāo)表示數(shù)據(jù)集中該節(jié)點(diǎn)度的大小，縱坐標(biāo)表示數(shù)據(jù)集中該度值對(duì)應(yīng)的節(jié)點(diǎn)個(gè)數(shù)。根據(jù)這三個(gè)數(shù)據(jù)集的度分布可以看出，Citeseer數(shù)據(jù)集和DBLP數(shù)據(jù)集中大度節(jié)點(diǎn)相對(duì)較多，但大度節(jié)點(diǎn)出現(xiàn)的頻率卻明顯很低，反之，小度節(jié)點(diǎn)有較高的出現(xiàn)頻率，其最高次數(shù)可達(dá)170余次。而Cora數(shù)據(jù)集則恰好與之相反，在Cora數(shù)據(jù)集中，雖然節(jié)點(diǎn)的度值都相對(duì)較小，但其度值出現(xiàn)的頻率卻明顯高于前兩個(gè)數(shù)據(jù)集，其度值出現(xiàn)的頻率最高可達(dá)560余次?？梢奀iteseer數(shù)據(jù)集、DBLP數(shù)據(jù)集和Cora數(shù)據(jù)集并不是一個(gè)高稠密的網(wǎng)絡(luò)。

3.5 調(diào)參與分析

在本文實(shí)驗(yàn)中，需要設(shè)置向量長(zhǎng)度k值和訓(xùn)練比例的值。通過(guò)調(diào)整訓(xùn)練比例可以將已知數(shù)據(jù)分成兩部分，一部分為訓(xùn)練集，一部分為測(cè)試集。我們對(duì)訓(xùn)練集中數(shù)據(jù)的鄰接矩陣使用本文提出的算法進(jìn)行分解，從而得到目標(biāo)網(wǎng)絡(luò)矩陣存儲(chǔ)形式。實(shí)驗(yàn)的訓(xùn)練率對(duì)算法預(yù)測(cè)結(jié)果的影響如圖3所示。

(a) Citeseer數(shù)據(jù)集

(b) DBLP數(shù)據(jù)集

(c) Cora數(shù)據(jù)集圖3 訓(xùn)練率與預(yù)測(cè)結(jié)果之間的關(guān)聯(lián)關(guān)系

從圖3中可以看到，設(shè)置的向量長(zhǎng)度分別為：50、100、150、200、300，其相應(yīng)的訓(xùn)練集比例為：0.75、0.8、0.85、0.9、0.95。通過(guò)分析圖3可以得出，由于Citeseer數(shù)據(jù)集和Cora數(shù)據(jù)集是一個(gè)相對(duì)稀疏的網(wǎng)絡(luò)，當(dāng)向量長(zhǎng)度為100時(shí)，且對(duì)應(yīng)的訓(xùn)練比例為0.75時(shí)，AUC獲得了較好的性能；當(dāng)向量長(zhǎng)度增大到300時(shí)，且對(duì)應(yīng)的訓(xùn)練比例為0.95時(shí)，AUC獲得了最優(yōu)的性能；然而DBLP數(shù)據(jù)集是一個(gè)相對(duì)稠密的網(wǎng)絡(luò)，當(dāng)向量長(zhǎng)度大于100時(shí)，其訓(xùn)練比例在0.75和0.95之間，AUC的變化幅度相差都不大。因此，對(duì)于稀疏網(wǎng)絡(luò)而言，向量長(zhǎng)度和訓(xùn)練集比例的大小對(duì)AUC的影響比較大，而對(duì)于越稠密的網(wǎng)絡(luò)，影響相對(duì)較小。

3.6 網(wǎng)絡(luò)表示可視化

本文從Citeseer、DBLP和Cora三個(gè)數(shù)據(jù)集中，分別隨機(jī)地選取3個(gè)類別，并隨機(jī)地在每個(gè)類別中選取150個(gè)節(jié)點(diǎn)，使用T-SNE(T-distributed Stochastic Neighbor Embedding)可視化降維算法[35]，將數(shù)據(jù)集中的450個(gè)節(jié)點(diǎn)投影到2維坐標(biāo)平面上，用3種不同的形狀分別表示每個(gè)數(shù)據(jù)集中的3個(gè)不同類別。本算法的網(wǎng)絡(luò)表示可視化的投影結(jié)果如圖4所示(說(shuō)明：圖4中橫縱坐標(biāo)的值為降維到2維后在坐標(biāo)軸上的值，該刻度值無(wú)單位，隨著可視化算法的降維效果而不斷地發(fā)生變化)。

(a) Citeseer 數(shù)據(jù)集的可視化

(b) DBLP數(shù)據(jù)集的可視化

(c) Cora數(shù)據(jù)集的可視化圖4 三個(gè)數(shù)據(jù)集上的網(wǎng)絡(luò)表示2維可視化

通過(guò)觀察圖4可以看出，網(wǎng)絡(luò)的2維可視化結(jié)果表現(xiàn)出了很好的區(qū)分能力。因此，基于網(wǎng)絡(luò)節(jié)點(diǎn)文本增強(qiáng)的鏈路預(yù)測(cè)算法表示的網(wǎng)絡(luò)節(jié)點(diǎn)具有很好的標(biāo)簽分類性能。從可視化結(jié)果中可以看出，同一種線型表示具有同類標(biāo)簽的節(jié)點(diǎn)的集合，對(duì)同類標(biāo)簽節(jié)點(diǎn)的歸類之后，再使用降維T-SNE算法,將其投影到同一個(gè)2維坐標(biāo)平面上。從圖4的3個(gè)數(shù)據(jù)集的可視化結(jié)果中可以看出，相同形狀的節(jié)點(diǎn)具有很明顯的聚類現(xiàn)象，且它們表示在二維平面上的距離也比較近。因此，可以進(jìn)一步表明，基于網(wǎng)絡(luò)節(jié)點(diǎn)文本增強(qiáng)的鏈路預(yù)測(cè)算法可以很好地將目標(biāo)網(wǎng)絡(luò)的結(jié)構(gòu)信息和節(jié)點(diǎn)的文本結(jié)合起來(lái)，通過(guò)預(yù)測(cè)將具有相似的網(wǎng)絡(luò)結(jié)構(gòu)節(jié)點(diǎn)聚集到一個(gè)相對(duì)較近的距離空間中，體現(xiàn)了很好的聚類性能；反之，也可將相差較大的網(wǎng)絡(luò)節(jié)點(diǎn)表示到較遠(yuǎn)的距離空間中。因此，基于聚類性質(zhì)的網(wǎng)絡(luò)節(jié)點(diǎn)文本增強(qiáng)的方法可以很好地應(yīng)用于鏈路預(yù)測(cè)領(lǐng)域。

3.7 案例研究

為了更好地理解基于文本增強(qiáng)的鏈路預(yù)測(cè)算法的有效性，在DBLP數(shù)據(jù)集中做了實(shí)驗(yàn)，DBLP數(shù)據(jù)集是一個(gè)引文網(wǎng)絡(luò)，根據(jù)該數(shù)據(jù)集中論文的方向可將其分為4個(gè)領(lǐng)域，分別為計(jì)算機(jī)視覺(jué)領(lǐng)域、數(shù)據(jù)庫(kù)領(lǐng)域、人工智能領(lǐng)域和數(shù)據(jù)挖掘領(lǐng)域。在該數(shù)據(jù)集中，設(shè)置目標(biāo)節(jié)點(diǎn)的向量表示長(zhǎng)度為200，其訓(xùn)練比例為0.9，并隨機(jī)選取一個(gè)標(biāo)題為：“Factorial Hidden Markov Models”的目標(biāo)節(jié)點(diǎn)，分別使用DeepWalk 算法和本文所提出的TELP算法計(jì)算其對(duì)應(yīng)的余弦相似度值。通過(guò)統(tǒng)計(jì)得到該標(biāo)題中5個(gè)相似度值最高的鄰居節(jié)點(diǎn)，最終分別篩選出了5條標(biāo)題與目標(biāo)標(biāo)題“Factorial Hidden Markov Models”所對(duì)應(yīng)。使用兩種預(yù)測(cè)算法篩選出的5條標(biāo)題的具體的信息如表3和表4所示。

表3 DeepWalk算法案例實(shí)證研究

表4 本文算法案例實(shí)證研究

在表3和表4中，通過(guò)對(duì)網(wǎng)絡(luò)表示的相似度計(jì)算，分別用DeepWalk算法和TELP算法返回了5條與目標(biāo)標(biāo)題最相關(guān)的標(biāo)題。通過(guò)比較可以發(fā)現(xiàn)，本文提出的TELP算法要比已有的DeepWalk算法相似度高。通過(guò)計(jì)算對(duì)應(yīng)的余弦相似性，發(fā)現(xiàn)DeepWalk算法預(yù)測(cè)出來(lái)的5條標(biāo)題雖然與目標(biāo)標(biāo)題能達(dá)到結(jié)構(gòu)上的相似，但是不能夠達(dá)到文本上的相似。而在表4中，使用TELP算法預(yù)測(cè)出的5條相關(guān)標(biāo)題與目標(biāo)標(biāo)題之間不僅在結(jié)構(gòu)上而且也在文本上達(dá)到了很高的相似性。每個(gè)相關(guān)標(biāo)題幾乎都包含了目標(biāo)標(biāo)題中的關(guān)鍵字“Markov Models”或“Hidden”。在該實(shí)例中，本文算法顯然優(yōu)于DeepWalk算法。其中，使用本文算法預(yù)測(cè)出的5條標(biāo)題中，第一條標(biāo)題里幾乎包含了所有的關(guān)鍵字，可以看出，這條標(biāo)題與目標(biāo)標(biāo)題“Factorial Hidden Markov Models”的相似性達(dá)到了最高。因此，基于文本增強(qiáng)的鏈路預(yù)測(cè)算法可以有效地將網(wǎng)絡(luò)的結(jié)構(gòu)信息和節(jié)點(diǎn)的屬性信息結(jié)合起來(lái)，從而更好地學(xué)習(xí)并挖掘網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)關(guān)聯(lián)性，達(dá)到更好的預(yù)測(cè)效果。

4 結(jié) 語(yǔ)

針對(duì)目前鏈路預(yù)測(cè)問(wèn)題研究中的研究方法主要是基于已知網(wǎng)絡(luò)的結(jié)構(gòu)信息,沒(méi)有考慮到與已知網(wǎng)絡(luò)相關(guān)的文本信息，本文提出了一種基于網(wǎng)絡(luò)文本增強(qiáng)的鏈路預(yù)測(cè)算法，并應(yīng)用到了三個(gè)真實(shí)的科研合作網(wǎng)絡(luò)Citeseer、DBLP和Cora中，運(yùn)用基于淺層神經(jīng)網(wǎng)絡(luò)的無(wú)監(jiān)督學(xué)習(xí)方法對(duì)其進(jìn)行預(yù)測(cè)。實(shí)驗(yàn)結(jié)果表明，在真實(shí)的網(wǎng)絡(luò)環(huán)境中，本文算法表現(xiàn)出了較為優(yōu)異的預(yù)測(cè)性能。通過(guò)進(jìn)一步對(duì)目標(biāo)網(wǎng)絡(luò)的可視化研究發(fā)現(xiàn)，基于本文算法,在實(shí)驗(yàn)過(guò)程中，所訓(xùn)練得到的網(wǎng)絡(luò)節(jié)點(diǎn)也具有十分明顯的聚類現(xiàn)象，即該方法可以很好地應(yīng)用于分類任務(wù)中。最后通過(guò)對(duì)實(shí)驗(yàn)案例的研究，充分地證明了具有相似結(jié)構(gòu)和內(nèi)部相似的網(wǎng)絡(luò)節(jié)點(diǎn)之間的空間距離相比其他節(jié)點(diǎn)而言更為相近。因此，綜上所述，本文算法是一種新的且行之有效的鏈路預(yù)測(cè)算法，它能夠在真實(shí)的網(wǎng)絡(luò)環(huán)境中表現(xiàn)出較為優(yōu)異的預(yù)測(cè)性能。在今后的研究過(guò)程中，我們將把該方法擴(kuò)展到大規(guī)模的復(fù)雜網(wǎng)絡(luò)中進(jìn)行預(yù)測(cè)分析及驗(yàn)證，同時(shí)，還會(huì)進(jìn)一步研究更多的鏈路預(yù)測(cè)指標(biāo)以適應(yīng)更為復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)。