基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈路預(yù)測(cè)算法*

楊曉翠，宋甲秀，張曦煌

江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122

1 引言

如今，人類處于以互聯(lián)網(wǎng)為代表的網(wǎng)絡(luò)信息技術(shù)迅速發(fā)展的時(shí)代，多種形式的信息網(wǎng)絡(luò)出現(xiàn)在現(xiàn)實(shí)生活中，包括社會(huì)網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和萬(wàn)維網(wǎng)等。這些網(wǎng)絡(luò)的規(guī)模從數(shù)百個(gè)頂點(diǎn)到數(shù)百萬(wàn)個(gè)甚至數(shù)十億個(gè)頂點(diǎn)不等。分析此類網(wǎng)絡(luò)對(duì)不同學(xué)科的各種新興應(yīng)用起著至關(guān)重要的作用。然而，對(duì)這些復(fù)雜網(wǎng)絡(luò)的有效分析在很大程度上取決于網(wǎng)絡(luò)表現(xiàn)的方式。通常，用一個(gè)離散鄰接矩陣來(lái)表示網(wǎng)絡(luò)，此方式只捕獲頂點(diǎn)之間的相鄰關(guān)系，但不能體現(xiàn)如路徑、頻繁的子結(jié)構(gòu)等更復(fù)雜的高階結(jié)構(gòu)關(guān)系。

最近，網(wǎng)絡(luò)表示學(xué)習(xí)（network representation learning，NRL）引起了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，復(fù)雜網(wǎng)絡(luò)的研究邁入了全新紀(jì)元，其目的是學(xué)習(xí)網(wǎng)絡(luò)頂點(diǎn)的潛在低維表示，同時(shí)保留網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、頂點(diǎn)內(nèi)容和其他方面的信息。在學(xué)習(xí)新的頂點(diǎn)表示后，通過(guò)在獲得的低維向量空間中應(yīng)用傳統(tǒng)的基于向量的機(jī)器學(xué)習(xí)算法，可以容易且高效地執(zhí)行網(wǎng)絡(luò)分析任務(wù)，從而避免了派生應(yīng)用于原始網(wǎng)絡(luò)的復(fù)雜算法的必要性。鏈路預(yù)測(cè)，作為網(wǎng)絡(luò)研究的分析利器之一，在未來(lái)的科學(xué)和工程發(fā)展中角色的重要性毋庸置疑。其相關(guān)研究對(duì)于分析網(wǎng)絡(luò)演化以研究網(wǎng)絡(luò)缺失數(shù)據(jù)補(bǔ)齊具有重要的理論意義，在信息檢索和推薦系統(tǒng)等領(lǐng)域具有巨大的應(yīng)用價(jià)值[1]。然而，當(dāng)前的鏈路預(yù)測(cè)算法大都基于原始網(wǎng)絡(luò)而設(shè)計(jì)，不可否認(rèn)，網(wǎng)絡(luò)表示學(xué)習(xí)對(duì)鏈路預(yù)測(cè)的研究提供了一種新的視角和方法，將極大推動(dòng)領(lǐng)域內(nèi)相關(guān)工作的進(jìn)展。

2 相關(guān)工作

近年來(lái)，鏈路預(yù)測(cè)吸引了廣大研究者的興趣，取得了很多顯著成果。其中，基于相似性的一類算法，主要利用了包括實(shí)體或節(jié)點(diǎn)的屬性和網(wǎng)絡(luò)的拓?fù)鋬煞N類型的信息。這種鏈接預(yù)測(cè)方法的基本假設(shè)是，如果兩個(gè)節(jié)點(diǎn)彼此相似，則更有可能具有鏈路。根據(jù)研究網(wǎng)絡(luò)范圍的差異，基于節(jié)點(diǎn)相似性的鏈路預(yù)測(cè)方法大致分為3類[2]：基于網(wǎng)絡(luò)局部結(jié)構(gòu)的預(yù)測(cè)方法、基于網(wǎng)絡(luò)全局結(jié)構(gòu)的預(yù)測(cè)方法、基于準(zhǔn)局部結(jié)構(gòu)的預(yù)測(cè)方法。

基于網(wǎng)絡(luò)局部結(jié)構(gòu)的預(yù)測(cè)方法只利用節(jié)點(diǎn)的鄰居信息，PA（preferential attachment）[3]、CN（common neighbors）[3]、Salton[3]、JC（Jaccard）[3]、AA（Adamic-Adar）[3]和RA（resource allocation）[3]等最為常見(jiàn)。此類方法計(jì)算復(fù)雜度低，但預(yù)測(cè)精度受信息量的限制。相對(duì)于局部結(jié)構(gòu)的預(yù)測(cè)方法，全局結(jié)構(gòu)相似性方法則考慮了整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)，包括Katz[3]、LHN2（Leicht Holme-Newman）[3]、ACT（average commute time）[3]、RWR（random walk with restart）[3]、SimRank[3]、MFI（matrix-forest theory）[3]等?；跍?zhǔn)局部結(jié)構(gòu)的預(yù)測(cè)算法，無(wú)需全局網(wǎng)絡(luò)拓?fù)湫畔?，而是利用比局部指?biāo)更多的信息，如LP（local path）[3]、LRW（local random walk）[3]、SRW（superposed random walk）[3]。近期該方法領(lǐng)域的研究成果有：Cannistraci等人[4]通過(guò)強(qiáng)化經(jīng)典相似性指標(biāo)與共同鄰居節(jié)點(diǎn)之間的聯(lián)系，設(shè)計(jì)了相似性指標(biāo)，稱為CAR（Cannistraci-resource-allocation）。賈等人提出用H指標(biāo)[5]代替度，以加權(quán)方式來(lái)衡量引文網(wǎng)絡(luò)中文章的重要性，達(dá)到了增強(qiáng)Salton[3]、Sorenson[3]和AA[3]這3種經(jīng)典鏈路預(yù)測(cè)方法的效果。Gao等人[6]基于網(wǎng)絡(luò)中最小的局部結(jié)構(gòu)三元閉包，提出了3個(gè)相似性指標(biāo)TWCN（common neighbors with triadic closure weight）、TWAA（Adamic-Adar with triadic closure weight）、TWRA（resource allocation with triadic closure weight）和具有調(diào)節(jié)參數(shù)的3個(gè)相似性指標(biāo)TWCN*、TWAA*、TWRA*，以O(shè)(N3)的時(shí)間復(fù)雜度為代價(jià)提高了預(yù)測(cè)精度。Liu等人[7]從局部路徑上資源交換的角度，提出了擴(kuò)展資源分配指標(biāo)ERA（extended resource allocation index），通過(guò)在兩個(gè)端點(diǎn)之間的公共鄰居和非共同鄰居交互的資源量來(lái)測(cè)量相似性。Wu等人[8]提出適用于大規(guī)模網(wǎng)絡(luò)的NLC（similarity index based on node and link clustering information）算法，以節(jié)點(diǎn)聚類信息和邊聚類信息融入相似性計(jì)算指標(biāo)的方式更加充分地挖掘了共同鄰居在鏈路預(yù)測(cè)中的作用。

概率模型或生成模型是鏈路預(yù)測(cè)的另一類有效方法。如Gao等人[9]提出了一種利用網(wǎng)絡(luò)中多個(gè)信息源獲取鏈路發(fā)生概率的模型。Barbieri等人[10]提出了一種用于定向和節(jié)點(diǎn)歸屬圖的鏈路預(yù)測(cè)的隨機(jī)主題模型。該模型不僅預(yù)測(cè)鏈接，而且還為每個(gè)預(yù)測(cè)的鏈接生成不同類型的解釋。Hu等人[11]提出了一種在社會(huì)網(wǎng)絡(luò)中檢測(cè)人體運(yùn)動(dòng)的概率模型，并提出了一種使用基于約束的遺傳算法對(duì)人體運(yùn)動(dòng)進(jìn)行標(biāo)記的方法來(lái)優(yōu)化模型。Zhang等人[12]通過(guò)結(jié)合機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)技術(shù)，提出Weisfeiler-Lehman神經(jīng)機(jī)器（Wlnm）模型，以圖形形式學(xué)習(xí)拓?fù)涮卣?，預(yù)測(cè)鏈接的形成，取得了比大多數(shù)基于節(jié)點(diǎn)鄰居的方法更好的結(jié)果。模型類算法在網(wǎng)絡(luò)分析和實(shí)際應(yīng)用中具有許多優(yōu)點(diǎn)。然而，這樣的模型一般需要鏈接外觀的預(yù)定義分布，參數(shù)學(xué)習(xí)和推理通常不易。

相關(guān)還有一些基于最大似然估計(jì)和矩陣分解技術(shù)的算法研究。最大似然估計(jì)類算法將假定的規(guī)則和參數(shù)與已知結(jié)構(gòu)的最大概率結(jié)合來(lái)預(yù)測(cè)網(wǎng)絡(luò)中缺失的鏈路。如Clauset等人[13-14]提出了一種基于分層網(wǎng)絡(luò)結(jié)構(gòu)的算法，對(duì)具有層次結(jié)構(gòu)的網(wǎng)絡(luò)給出了很好的預(yù)測(cè)。Lv等人[15]提出了結(jié)構(gòu)一致性的概念，用于反映網(wǎng)絡(luò)的固有鏈路可預(yù)測(cè)性，并提出了一種比現(xiàn)有技術(shù)方法更為準(zhǔn)確和魯棒的鏈路預(yù)測(cè)的結(jié)構(gòu)擾動(dòng)方法。而基于矩陣分解的預(yù)測(cè)算法是一種從網(wǎng)絡(luò)數(shù)據(jù)中學(xué)習(xí)潛在特征以進(jìn)行鏈接預(yù)測(cè)的方法，通過(guò)將網(wǎng)絡(luò)中的節(jié)點(diǎn)投影到潛在空間，以節(jié)點(diǎn)在該空間中的位置來(lái)衡量鏈路的存在概率[16-17]。潛在空間的每個(gè)特征都被認(rèn)為是一個(gè)潛在屬性，若兩節(jié)點(diǎn)具有相似的潛在特征，它們則更有可能是相似的[18]。從另一個(gè)角度來(lái)看，復(fù)雜網(wǎng)絡(luò)的相似性矩陣可以近似為兩個(gè)低維特征矩陣的乘積，分別對(duì)應(yīng)基矩陣和系數(shù)矩陣，限制其元素非負(fù)，則可以通過(guò)非負(fù)矩陣分解算法來(lái)求解。此類方法的缺陷是潛在特征的數(shù)量很難確定。

到目前為止，多數(shù)鏈路預(yù)測(cè)算法都是基于高維稀疏表示的網(wǎng)絡(luò)結(jié)構(gòu)而設(shè)計(jì)，利用網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)實(shí)現(xiàn)鏈路預(yù)測(cè)任務(wù)的算法尚未得到廣泛研究。本文基于隨機(jī)游走的NRL算法思維，并結(jié)合幾何布朗運(yùn)動(dòng)（geometric Brownian motion，GBM）與傳統(tǒng)網(wǎng)絡(luò)圖理論原理，提出了基于幾何布朗運(yùn)動(dòng)的隨機(jī)游走算法（GBM-based random walk algorithm，GbmRw），用于建模網(wǎng)絡(luò)中的信息流動(dòng)，即收集頂點(diǎn)序列，將信息傳播的隨機(jī)性質(zhì)進(jìn)行量化，從而實(shí)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系的捕獲；繼而將此算法和通過(guò)最大化每個(gè)輸入頂點(diǎn)與其周圍上下文的條件概率的Skip-Gram模型[19]相結(jié)合，設(shè)計(jì)出信息網(wǎng)絡(luò)表示學(xué)習(xí)算法（information network representation learning algorithm based on geometric Brown motion，GBMLA）。最后，以頂點(diǎn)表示向量之間的歐式距離表征鏈路相似性，提出鏈路預(yù)測(cè)算法（link prediction algorithm based on geometric Brown motion，GBMLP）。該算法首先是容易理解和實(shí)現(xiàn)；其次，預(yù)測(cè)效果好且性能穩(wěn)定，實(shí)驗(yàn)結(jié)果表明其在多個(gè)數(shù)據(jù)集中的AUC值較于對(duì)比算法提高了1%～10%不等，且Precision保持領(lǐng)先；再次，魯棒性高，與網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)的融合，使其能有效應(yīng)對(duì)規(guī)模不斷增長(zhǎng)的網(wǎng)絡(luò)。

3 算法描述

3.1 定義描述

信息網(wǎng)絡(luò)[20]：一個(gè)信息網(wǎng)絡(luò)定義為G=(V,E,X,Y)。其中，V表示節(jié)點(diǎn)集，E?(V×V)為邊集，X∈R|V|×m表示節(jié)點(diǎn)屬性矩陣，m為屬性個(gè)數(shù)，元素Xij代表節(jié)點(diǎn)i在第j個(gè)屬性上的值，Y∈R|V|×y為節(jié)點(diǎn)標(biāo)簽矩陣，y為標(biāo)簽集，當(dāng)節(jié)點(diǎn)i具有第k個(gè)標(biāo)簽時(shí)，Yik=1；否則，Yik=-1。對(duì)于每個(gè)(i,j)∈E，若G為無(wú)向信息網(wǎng)絡(luò)，則有(j,i)∈E；若G有向，(j,i)∈E不一定成立。當(dāng)G是二進(jìn)制/無(wú)權(quán)網(wǎng)絡(luò)時(shí)，則每個(gè)(i,j)∈E伴有權(quán)重wij=1。

網(wǎng)絡(luò)表示學(xué)習(xí)[20]也稱為網(wǎng)絡(luò)嵌入（network embedding，NE），給定一個(gè)信息網(wǎng)絡(luò)G=(V,E,X,Y)，網(wǎng)絡(luò)表示學(xué)習(xí)的目標(biāo)是學(xué)習(xí)一個(gè)映射函數(shù)f:v→rv∈Rd，這里rv為節(jié)點(diǎn)v的學(xué)習(xí)表示，d為學(xué)習(xí)表示的維度。映射函數(shù)f需要保留原始網(wǎng)絡(luò)信息，使得在原始網(wǎng)絡(luò)相似的頂點(diǎn)在學(xué)習(xí)向量空間里依然相似。同時(shí)，學(xué)習(xí)的頂點(diǎn)表示需要滿足低維、信息完整、連續(xù)性等條件。換而言之，即其維數(shù)應(yīng)該遠(yuǎn)小于原始鄰接矩陣表示的維度；應(yīng)該保持由網(wǎng)絡(luò)結(jié)構(gòu)和頂點(diǎn)屬性和/或頂點(diǎn)標(biāo)簽反映的頂點(diǎn)鄰近度；應(yīng)該具有連續(xù)的實(shí)際值以支持后續(xù)的網(wǎng)絡(luò)分析任務(wù)。

幾何布朗運(yùn)動(dòng)（GBM）[21]也叫作指數(shù)布朗運(yùn)動(dòng)，是連續(xù)時(shí)間情況下的隨機(jī)過(guò)程，其中隨機(jī)變量的對(duì)數(shù)遵循布朗運(yùn)動(dòng)。即隨機(jī)過(guò)程St在滿足隨機(jī)微分方程dSt=μStdt+σStdWt的情況下被認(rèn)為遵循幾何布朗運(yùn)動(dòng)。這里Wt是一個(gè)維納過(guò)程,或者說(shuō)是布朗運(yùn)動(dòng)，而μ（漂移百分比）和σ（波動(dòng)百分比）則是常量，分別代表確定性趨勢(shì)和這種模型中不可預(yù)測(cè)事件的影響。

鏈路預(yù)測(cè)[3]：針對(duì)任意無(wú)向網(wǎng)絡(luò)G，N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，總邊數(shù)為M。令U為N(N?1)/2個(gè)節(jié)點(diǎn)對(duì)組成的全集。U?E則是網(wǎng)絡(luò)中所有不存在/缺少的鏈接的集合。鏈接預(yù)測(cè)的目的就是從集合U?E中找出缺失的鏈接。給定一種鏈路預(yù)測(cè)方法，該方法為每對(duì)沒(méi)有連邊的節(jié)點(diǎn)對(duì)(x,y)賦予一個(gè)分?jǐn)?shù)值Sxy。這個(gè)分?jǐn)?shù)值可以理解為一種接近性，它與兩節(jié)點(diǎn)的鏈接概率正相關(guān)。即所有不存在的鏈接根據(jù)其分?jǐn)?shù)按降序排序，分?jǐn)?shù)越高的節(jié)點(diǎn)對(duì)表明該鏈接存在的可能性越大。

3.2 基本算法介紹

針對(duì)基于相似性的預(yù)測(cè)算法，本文選擇四個(gè)經(jīng)典算法 CN[3]、JC[3]、AA[3]和 LP[3]，以及兩個(gè)近年來(lái)具有代表性的高質(zhì)量算法CAR[3]和NLC[8]為基準(zhǔn)，各算法相似性指標(biāo)定義描述如下。

（1）CN指標(biāo)。對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)x，定義其鄰居集合為Γ(x)，則兩個(gè)節(jié)點(diǎn)x和y的相似性就定義為它們共同的鄰居數(shù)，即：

（2）JC指標(biāo)。用兩節(jié)點(diǎn)共同鄰居占兩節(jié)點(diǎn)鄰居總和的比例來(lái)表示節(jié)點(diǎn)x和y的相似性，即：

（3）AA指標(biāo)。優(yōu)化的CN指標(biāo)，將不同的權(quán)重分配給該公共鄰居集合中的不同節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的權(quán)重等于該節(jié)點(diǎn)的度的對(duì)數(shù)分之一，即：

（4）LP指標(biāo)。該指標(biāo)通過(guò)利用節(jié)點(diǎn)x和y之間具有長(zhǎng)度為2和3的不同路徑的數(shù)量的信息，來(lái)表征節(jié)點(diǎn)之間的相似性，即：

其中，A為鄰接矩陣，ε為自由參數(shù)。

（5）CAR指標(biāo)。該指標(biāo)是在基于網(wǎng)絡(luò)局部結(jié)構(gòu)的經(jīng)典相似性指標(biāo)RA[3]的基礎(chǔ)上精確引入鏈接/社區(qū)策略而設(shè)計(jì)的變體，定義為：

其中，r(z)為共同鄰居的局部社區(qū)度[4]，即節(jié)點(diǎn)z的鄰居與x和y共同鄰居的交集。

（6）NLC指標(biāo)。將節(jié)點(diǎn)聚類系數(shù)和邊聚類系數(shù)融合實(shí)現(xiàn)節(jié)點(diǎn)相似性的計(jì)算，可以理解為公共節(jié)點(diǎn)z到節(jié)點(diǎn)x和節(jié)點(diǎn)y的局部聚類系數(shù)的總和，定義如下：

其中，CN(x,z)/(kz-1)表示邊聚類系數(shù)，Cz為節(jié)點(diǎn)聚類系數(shù)，tz表示通過(guò)節(jié)點(diǎn)z的三角形數(shù)量。

3.3 基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈路預(yù)測(cè)算法

3.3.1 同化函數(shù)模型

首先，引入同化函數(shù)St如圖1所示，來(lái)模擬頂點(diǎn)本身被游走（同化）的情況。將同化過(guò)程分為同化前期和同化期。在同化前期，該頂點(diǎn)的同化函數(shù)St將呈指數(shù)式增長(zhǎng)，直到St在時(shí)間為T(mén)時(shí)達(dá)到同化閾值并進(jìn)入同化期，并定義該過(guò)程不可逆，即頂點(diǎn)一旦被同化（游走），則不可撤銷。針對(duì)給定網(wǎng)絡(luò)，本文建模同化函數(shù)如下，其中μ表示隨機(jī)過(guò)程平均值的變化：

Fig.1 Assimilation function圖1 同化函數(shù)

然后，添加一個(gè)維納過(guò)程Wt來(lái)解釋隨機(jī)性。根據(jù)維納過(guò)程的特性可知，dWt實(shí)質(zhì)為高斯白噪聲，并且參與同化函數(shù)如式（9）。以此方式，St被建模為幾何布朗運(yùn)動(dòng)過(guò)程，表示為B(μ,σ)，μ和σ為常數(shù)，分別對(duì)應(yīng)漂移和波動(dòng)。

給定初始值S0，根據(jù)伊藤積分，可得隨機(jī)微分方程（9）的解如式（10）。不失一般性，本文取初始同化值S0=1。

3.3.2 基于GBM的隨機(jī)游走算法

假設(shè)從節(jié)點(diǎn)i開(kāi)始游走，則其鄰居節(jié)點(diǎn)j是否加入游走序列取決于j對(duì)i的同化函數(shù)，只有當(dāng)該函數(shù)的值超過(guò)某個(gè)閾值后，j才會(huì)被游走。為了更好地定量分析，以鏈路端節(jié)點(diǎn)及其公共鄰居節(jié)點(diǎn)形成的局部環(huán)境的內(nèi)部影響力為同化閾值，用dij表示，定義為：

其中，第一個(gè)因子表示節(jié)點(diǎn)i在節(jié)點(diǎn)j集體影響力中的占比，理解為節(jié)點(diǎn)j被節(jié)點(diǎn)i影響的直接可能性，而后兩個(gè)因子主要表征間接因素（包括j占i影響力的比重，經(jīng)公共節(jié)點(diǎn)z傳遞的影響力占比）對(duì)j最終被影響的貢獻(xiàn)。kdi為節(jié)點(diǎn)i的度減1，Γ(i)為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集，這里節(jié)點(diǎn)i的集體影響力（collective influence）[22]CIi定義如式（12），Ball(i,j)為圍繞節(jié)點(diǎn)i，且屬于半徑（最短路徑）為l的球內(nèi)的節(jié)點(diǎn)集合，?Ball(i,j)為該球的邊界，l是預(yù)定義的不超過(guò)有限網(wǎng)絡(luò)的網(wǎng)絡(luò)直徑的非負(fù)整數(shù)，本文取l=1。

由于GBM是一個(gè)時(shí)間連續(xù)的隨機(jī)過(guò)程，因此使用每個(gè)持續(xù)時(shí)間δt的時(shí)間步長(zhǎng)來(lái)離散時(shí)間。因此本文設(shè)計(jì)基于GBM的隨機(jī)游走算法GbmRw如算法1。其思路為：開(kāi)始，設(shè)置所有節(jié)點(diǎn)均未被游走。一旦某一節(jié)點(diǎn)i被游走，將其設(shè)置為新游走節(jié)點(diǎn)，并加入游走序列，然后計(jì)算其各個(gè)鄰居節(jié)點(diǎn)的同化函數(shù)，并與同化閾值比較以確定該鄰居節(jié)點(diǎn)是否加入游走序列。對(duì)于每個(gè)j∈Γ(i)，使用tij=0來(lái)初始化i開(kāi)始游走j的時(shí)刻。當(dāng)節(jié)點(diǎn)i所有鄰居節(jié)點(diǎn)都被條件判斷過(guò)之后，將頂點(diǎn)i的狀態(tài)更新為已游走節(jié)點(diǎn)。從游走序列選擇最后加入的游走節(jié)點(diǎn)，重復(fù)此步驟，直至滿足預(yù)設(shè)游走序列長(zhǎng)度。其中表示在時(shí)刻t，節(jié)點(diǎn)j被節(jié)點(diǎn)i同化的函數(shù)，根據(jù)GBM特性，為一高斯變量，記為。在時(shí)刻t，若，則節(jié)點(diǎn)j被加入游走序列且成為新的游走起始點(diǎn)；否則，在下一時(shí)刻t+δt，同化函數(shù)是期望和方差更高的高斯變量，記為

算法1GbmRw算法

輸入：網(wǎng)絡(luò)G(V,E)，游走長(zhǎng)度wl,開(kāi)始節(jié)點(diǎn)i，時(shí)間步長(zhǎng)參數(shù)δ。

輸出：隨機(jī)游走序列walk。

3.3.3 基于GbmRw的網(wǎng)絡(luò)表示學(xué)習(xí)算法

基于GbmRw的網(wǎng)絡(luò)表示學(xué)習(xí)算法GBMLA主要包含兩部分：一個(gè)隨機(jī)游走生成器和一個(gè)表示學(xué)習(xí)過(guò)程。隨機(jī)游走生成器生成固定長(zhǎng)度的隨機(jī)游走序列，每個(gè)節(jié)點(diǎn)生成長(zhǎng)度為wl的γ個(gè)隨機(jī)游走序列，這里γ為迭代次數(shù)。表示學(xué)習(xí)過(guò)程則通過(guò)類比實(shí)現(xiàn)單詞的向量表示的word2vec模型實(shí)現(xiàn)，主要用到了其中的Skip-Gram模型[19]，該模型的思想是建立一個(gè)神經(jīng)網(wǎng)絡(luò)，神經(jīng)網(wǎng)絡(luò)的訓(xùn)練集是由單詞組成的句子。神經(jīng)網(wǎng)絡(luò)的輸入是單詞，輸出是各個(gè)單詞出現(xiàn)在輸入單詞的上下文中的概率。通過(guò)訓(xùn)練集對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，得到神經(jīng)網(wǎng)絡(luò)中的一些參數(shù)，根據(jù)參數(shù)可以得到輸入的單詞的向量表示。本文以節(jié)點(diǎn)為單詞，隨機(jī)游走得到的節(jié)點(diǎn)序列walks為句子進(jìn)行訓(xùn)練，從而實(shí)現(xiàn)節(jié)點(diǎn)的表示學(xué)習(xí)。具體過(guò)程見(jiàn)算法2：首先，將網(wǎng)絡(luò)數(shù)據(jù)集的節(jié)點(diǎn)隨機(jī)排列形成序列O；其次，利用算法1依次對(duì)O中的每個(gè)節(jié)點(diǎn)進(jìn)行游走得到其對(duì)應(yīng)的游走序列walk，將其加入walks；然后以重復(fù)以上操作γ次的最終walks以及設(shè)置的窗口大小w和表示維度d為Skip-Gram模型的輸入進(jìn)行學(xué)習(xí)，得到節(jié)點(diǎn)表示矩陣。

算法2GBMLA算法

輸入：網(wǎng)絡(luò)G(V,E)，窗口大小w，游走長(zhǎng)度wl，表示維度d，迭代次數(shù)γ，時(shí)間步長(zhǎng)參數(shù)δ。

輸出：節(jié)點(diǎn)表示矩陣Φ∈ R(|V|×d)。

最后，定義基于GBMLA的鏈路預(yù)測(cè)算法，記為GBMLP，對(duì)應(yīng)于算法3。其相似性指標(biāo)表示為GBMLA算法所得到的節(jié)點(diǎn)向量表示之間的歐式距離。計(jì)算公式如下，其中rxi和ryi分別表示節(jié)點(diǎn)x和節(jié)點(diǎn)y的表示向量的第i維數(shù)據(jù)，d為表示向量的維度。

算法3GBMLP算法

輸入：網(wǎng)絡(luò)G(V,E)，窗口大小w，游走長(zhǎng)度wl，表示維度d，迭代次數(shù)γ，時(shí)間步長(zhǎng)參數(shù)δ。

輸出：相似性矩陣S∈R(|V|×|V|)。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文選擇四個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行測(cè)試，包括在線社交網(wǎng)絡(luò)數(shù)據(jù)集Facebook[23]、引文網(wǎng)絡(luò)Cora[24]、網(wǎng)頁(yè)網(wǎng)絡(luò) Political Blog（PB）[25]和 Wikipedia[23]。各網(wǎng)絡(luò)數(shù)據(jù)集的詳細(xì)信息如表1所示（其中|V|表示節(jié)點(diǎn)數(shù)，|E|表示邊數(shù)，|y|為網(wǎng)絡(luò)標(biāo)簽數(shù)，Multi-label表示網(wǎng)絡(luò)是否為多標(biāo)簽，N/A表示該列屬性不存在）。

Table 1 Details of networks datasets表1 網(wǎng)絡(luò)數(shù)據(jù)集詳細(xì)信息

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

鏈路預(yù)測(cè)度量指標(biāo)采用AUC和精確度（Precision）。AUC[3]是鏈路預(yù)測(cè)任務(wù)中常用的評(píng)價(jià)指標(biāo)，可以從整體上衡量算法的精確度。其具體含義指在測(cè)試集中隨機(jī)選擇一條邊的分?jǐn)?shù)值高于隨機(jī)選擇的一條不存在的鏈路分?jǐn)?shù)值的概率，如果在n次獨(dú)立重復(fù)實(shí)驗(yàn)中，有n1次測(cè)試集中的邊分?jǐn)?shù)大于不存在的邊分?jǐn)?shù)，有n2次兩分?jǐn)?shù)值相等，AUC定義為：

Precision[3]定義為在前L個(gè)預(yù)測(cè)邊中被預(yù)測(cè)準(zhǔn)確的比例。如果有m個(gè)預(yù)測(cè)準(zhǔn)確，即根據(jù)出現(xiàn)連接的可能性從大到小排列，排在前L的邊中有m個(gè)在測(cè)試集中，則精確度定義為m/L。

4.3 實(shí)驗(yàn)設(shè)置

為了不破壞原始網(wǎng)絡(luò)的結(jié)構(gòu)，對(duì)于每個(gè)網(wǎng)絡(luò)數(shù)據(jù)，在保證網(wǎng)絡(luò)連通的情況下，隨機(jī)抽取90%的連邊作為訓(xùn)練集ET，剩余10%的連邊作為測(cè)試集EP。算法2中網(wǎng)絡(luò)表示學(xué)習(xí)參數(shù)設(shè)置為w=10,γ=10,d=128,wl=80,δ=0.01。AUC中的采樣次數(shù)n=100 000，Precision排列表的長(zhǎng)度L=50、100、150、200、250，最終實(shí)驗(yàn)結(jié)果為各網(wǎng)絡(luò)獨(dú)立運(yùn)行10次的平均值。實(shí)驗(yàn)的硬件環(huán)境為2.80 GHz Intel?CoreTMi7-7700HQ CPU,8 GB RAM，操作系統(tǒng)為Windows,開(kāi)發(fā)環(huán)境為Python3.6.2。

4.4 結(jié)果分析

表2展示了在四個(gè)數(shù)據(jù)集上六種不同的算法與本文算法的AUC值。從結(jié)果數(shù)據(jù)中可以看出GBMLP算法普遍高于其他基于原始網(wǎng)絡(luò)的相似性預(yù)測(cè)算法，算法性能平均提升了1%～10%不等，在一定程度上肯定了該算法的可行性和有效性。其在PB網(wǎng)絡(luò)的預(yù)測(cè)性能尤為突出，提高率明顯；在Cora網(wǎng)絡(luò)的AUC值也保持較高水平,僅次于LP算法。

Table 2 AUCresults for GBMLP and other link prediction algorithms表2 GBMLP與其他鏈路預(yù)測(cè)算法的AUC指標(biāo)結(jié)果

圖2展示了六種算法與GBMLP算法在表1各數(shù)據(jù)集上針對(duì)不同L取值對(duì)應(yīng)的Precision實(shí)驗(yàn)結(jié)果。由圖可知，本文算法在四個(gè)數(shù)據(jù)集上的總體表現(xiàn)優(yōu)于其他算法，隨著L的變化，Precision值均處于領(lǐng)先位置，一方面說(shuō)明了該算法預(yù)測(cè)的穩(wěn)定性，另一方面也證實(shí)了網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)在預(yù)測(cè)缺失鏈路方面的研究?jī)r(jià)值，突出了本文算法的創(chuàng)新意義。

綜合以上實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)：首先，各算法在不同數(shù)據(jù)集上的預(yù)測(cè)性能受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響。如LP算法在Cora數(shù)據(jù)集上取得了最高的AUC值，在Facebook和Wikipedia數(shù)據(jù)集上卻均為最低。GBMLP、NLC等算法在Facebook數(shù)據(jù)集上的精度明顯高于其在Cora上的表現(xiàn)。其次，評(píng)估各預(yù)測(cè)算法性能的AUC和Precision指標(biāo)并不總是同步。如經(jīng)典的JC算法，雖然在四個(gè)數(shù)據(jù)集上都能取得較高水平的AUC值，Precision值卻普遍很低。此現(xiàn)象的原因可能是精確度取值只注重前面的L條邊是否預(yù)測(cè)準(zhǔn)確，而AUC是從整體上衡量算法的精確度。

4.5 時(shí)間復(fù)雜度分析

運(yùn)算效率是評(píng)價(jià)算法性能的一個(gè)重要因素，對(duì)于CN算法來(lái)說(shuō)，計(jì)算節(jié)點(diǎn)對(duì)的共同鄰居的時(shí)間復(fù)雜度為O(＜k＞)，計(jì)算所有節(jié)點(diǎn)的相似性的復(fù)雜度為O(N2＜k＞)，其中 ＜k＞ 為網(wǎng)絡(luò)的平均度。AA、JC兩算法與CN算法計(jì)算過(guò)程相同，時(shí)間復(fù)雜度同為O(N2＜k＞)。LP算法的時(shí)間復(fù)雜度較低，為O(N＜k＞3)。CAR算法與CN算法的差異在于計(jì)算局部社區(qū)度，該過(guò)程的時(shí)間復(fù)雜度為O(＜k＞2)，故CAR算法時(shí)間復(fù)雜度為O(N2＜k＞2)。NLC算法，計(jì)算所有節(jié)點(diǎn)聚類系數(shù)的時(shí)間復(fù)雜度為O(N2)，計(jì)算所有邊聚類系數(shù)的時(shí)間復(fù)雜度為O(N2＜k＞)，分配相似性分?jǐn)?shù)的時(shí)間復(fù)雜度為O(N2＜k＞)，因此其最終復(fù)雜度為O(N2＜k＞)。本文，GbmRw算法的時(shí)間復(fù)雜度為O(wl＜k＞2)，GBMLA算法的時(shí)間復(fù)雜度為O(γ×wl＜k＞2×dNlbN)，而相似性矩陣的計(jì)算復(fù)雜度為O(dN2)，則GBMLP算法的最終時(shí)間復(fù)雜度為O(dN2)。

Fig.2 Precisionresults for GBMLP and other link prediction algorithms圖2 GBMLP與其他鏈路預(yù)測(cè)算法的Precision指標(biāo)結(jié)果

5 結(jié)束語(yǔ)

鏈路預(yù)測(cè)作為網(wǎng)絡(luò)分析的重要方法和研究方向，具有很強(qiáng)的應(yīng)用前景。本文提出了基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈路預(yù)測(cè)算法GBMLP，并通過(guò)多個(gè)實(shí)驗(yàn)證明了其可行性和有效性。該研究的主要貢獻(xiàn)可以歸結(jié)為以下三方面：

（1）定義了同化函數(shù)St來(lái)模擬頂點(diǎn)本身被同化的情況，同時(shí)引入了內(nèi)部影響力的概念，并設(shè)計(jì)了以鏈路端節(jié)點(diǎn)及其公共鄰居節(jié)點(diǎn)形成的局部環(huán)境的內(nèi)部影響力為定義的同化閾值dij。

（2）首次將幾何布朗運(yùn)動(dòng)的思想引入到鏈路預(yù)測(cè)的研究，提出了基于幾何布朗運(yùn)動(dòng)的隨機(jī)游走算法GbmRw，并將其與自然語(yǔ)言處理模型Skip-Gram結(jié)合，進(jìn)一步設(shè)計(jì)出基于幾何布朗運(yùn)動(dòng)的網(wǎng)絡(luò)表示學(xué)習(xí)算法GBMLA。

（3）利用GBMLA算法的嵌入結(jié)果進(jìn)行鏈路預(yù)測(cè)任務(wù)，多個(gè)數(shù)據(jù)集上的多次實(shí)驗(yàn)結(jié)果肯定了該技術(shù)對(duì)鏈路預(yù)測(cè)研究的價(jià)值，對(duì)未來(lái)領(lǐng)域內(nèi)的科研工作具有一定程度的參考意義。

今后，將針對(duì)特定應(yīng)用場(chǎng)景，進(jìn)一步研究融合其他如標(biāo)簽、權(quán)重等屬性的網(wǎng)絡(luò)表示學(xué)習(xí)算法以便更全面地捕獲網(wǎng)絡(luò)信息，提升預(yù)測(cè)結(jié)果。