聯(lián)合子圖模式和網(wǎng)絡(luò)表征的路網(wǎng)鏈路預(yù)測(cè)模型

王 斌,李毅磊,盛津芳,孫澤軍,2,盧 奔

1(中南大學(xué) 計(jì)算機(jī)學(xué)院,長(zhǎng)沙 410083)2(平頂山學(xué)院 網(wǎng)絡(luò)中心,河南 平頂山 467000)

1 引 言

交通路網(wǎng)是城市社會(huì)經(jīng)濟(jì)活動(dòng)和貨物運(yùn)輸?shù)闹匾d體.從網(wǎng)絡(luò)拓?fù)涞慕嵌瓤?網(wǎng)絡(luò)結(jié)構(gòu)能夠在很大程度上影響道路的運(yùn)營(yíng)效率[1].近年來(lái),具有小世界和無(wú)標(biāo)度特性的復(fù)雜網(wǎng)絡(luò)因?yàn)槠鹾虾芏喱F(xiàn)實(shí)網(wǎng)絡(luò),比如社交網(wǎng)絡(luò),萬(wàn)維網(wǎng)等,受到了越來(lái)越多學(xué)者的青睞和研究.復(fù)雜網(wǎng)絡(luò)在社團(tuán)發(fā)現(xiàn)、關(guān)鍵節(jié)點(diǎn)檢測(cè)以及鏈路預(yù)測(cè)等方面都有了比較大的研究進(jìn)展[2,3].很多學(xué)者將復(fù)雜網(wǎng)絡(luò)相關(guān)理論應(yīng)用于路網(wǎng)結(jié)構(gòu)分析,如通過(guò)復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)理論研究路網(wǎng)結(jié)構(gòu)穩(wěn)健性[4],通過(guò)引入節(jié)點(diǎn)重要性分析局部攻擊策略對(duì)路網(wǎng)系統(tǒng)的影響等[5].

作為復(fù)雜網(wǎng)絡(luò)研究的重要分支之一,鏈路預(yù)測(cè)的主要任務(wù)是根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)屬性等信息預(yù)測(cè)網(wǎng)絡(luò)中尚未連邊的節(jié)點(diǎn)之間連邊的可能性[6].鏈路預(yù)測(cè)與網(wǎng)絡(luò)的結(jié)構(gòu)與演化有著密切的聯(lián)系[7],通過(guò)對(duì)整個(gè)網(wǎng)絡(luò)未知邊的預(yù)測(cè)可以從宏觀上衡量網(wǎng)絡(luò)演化的方向.將其應(yīng)用于路網(wǎng)結(jié)構(gòu)特征挖掘,對(duì)路網(wǎng)未來(lái)的演化進(jìn)行合理的推測(cè),從而給路網(wǎng)設(shè)計(jì)者提供有價(jià)值的信息,這在城市路網(wǎng)規(guī)劃[8]中有著重大的意義.

在路網(wǎng)上進(jìn)行鏈路預(yù)測(cè)研究具有很大的挑戰(zhàn)性.首先,路網(wǎng)具有其特殊的結(jié)構(gòu)復(fù)雜性,不同城市的路網(wǎng)的結(jié)構(gòu)特征因?yàn)榈乩砦恢谩⒔?jīng)濟(jì)水平、設(shè)計(jì)理念等的不同往往有著巨大的差異,這導(dǎo)致簡(jiǎn)單的啟發(fā)式鏈路預(yù)測(cè)方法(如LP[9]、Katz[10]、SimRank[11]等)不能適用于所有的路網(wǎng).其次,相較于蛋白質(zhì)相互作用網(wǎng)絡(luò)(PPI)、美國(guó)航空網(wǎng)絡(luò)(NS)等,路網(wǎng)具有高度的稀疏性,以何種方法提取有用的路網(wǎng)結(jié)構(gòu)信息也是一個(gè)關(guān)鍵的問(wèn)題.最后,路網(wǎng)還有一定的特殊結(jié)構(gòu),比如路網(wǎng)多為平行的橫縱交錯(cuò)道路結(jié)構(gòu),道路交叉口相關(guān)的道路往往只有兩三條等等,如何在模型中表示這樣的結(jié)構(gòu),提取其中的有效信息也是至關(guān)重要的.

對(duì)于路網(wǎng)特殊的復(fù)雜性,Zhang[12]提出的WLNM模型給我們提供了一個(gè)可行的思路.WLNM將子圖模式[13]應(yīng)用到復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)中,將待測(cè)邊作為目標(biāo)邊,通過(guò)既定的規(guī)則構(gòu)建節(jié)點(diǎn)個(gè)數(shù)一定的封閉子圖,然后將子圖的鄰接矩陣作為特征參與到分類模型訓(xùn)練中.基于封閉子圖的鏈路預(yù)測(cè)模型能夠?qū)W習(xí)不同的網(wǎng)絡(luò)結(jié)構(gòu)特征,但是僅用鄰接矩陣表示子圖特征只能表現(xiàn)子圖鄰域的連接特性,對(duì)一些其它比較重要的信息(如節(jié)點(diǎn)之間的高階相似性,子圖在全局中的角色等)無(wú)法保留,這種信息的缺失在稀疏網(wǎng)絡(luò)中表現(xiàn)更為明顯.

基于隨機(jī)游走的網(wǎng)絡(luò)表征技術(shù)[14]將網(wǎng)絡(luò)映射到低維向量空間中,實(shí)現(xiàn)節(jié)點(diǎn)的向量化的同時(shí)保留著網(wǎng)絡(luò)結(jié)構(gòu)特性.一方面,向量化的節(jié)點(diǎn)融合了整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)信息,含義更加豐富;另一方面,有效的隨機(jī)游走策略可以很好地保持網(wǎng)絡(luò)特殊結(jié)構(gòu),使得網(wǎng)絡(luò)表征更有針對(duì)性.

基于上述分析,本文提出了一種針對(duì)路網(wǎng)的鏈路預(yù)測(cè)模型GRSC(General Road Subgraph Classification),將子圖模型和網(wǎng)絡(luò)表征有機(jī)地結(jié)合起來(lái),共同作用于路網(wǎng)的鏈路預(yù)測(cè).如圖1所示,在模型中,我們首先根據(jù)路網(wǎng)的特殊結(jié)構(gòu)和實(shí)際意義提出了一種新的基于隨機(jī)游走的網(wǎng)絡(luò)表征算法road2vec,將網(wǎng)絡(luò)映射到d維向量空間,然后將目標(biāo)邊按照既定的排序選取規(guī)則生成包含k個(gè)節(jié)點(diǎn)的封閉子圖,并根據(jù)其鄰接矩陣構(gòu)建子圖結(jié)構(gòu)特征,隨后根據(jù)表征結(jié)果和子圖節(jié)點(diǎn)序列生成對(duì)應(yīng)的游走距離特征,與子圖結(jié)構(gòu)特征一起構(gòu)建封閉子圖的總特征,稱之為廣義路網(wǎng)子圖特征.最后,通過(guò)logistic回歸分類模型學(xué)習(xí)廣義路網(wǎng)子圖特征與節(jié)點(diǎn)連邊之間的關(guān)系,進(jìn)而完成鏈路預(yù)測(cè)任務(wù).

相比于其它的鏈路預(yù)測(cè)方法,GRSC主要有以下幾點(diǎn)優(yōu)勢(shì):1)適應(yīng)性強(qiáng).模型在不同國(guó)家,不同結(jié)構(gòu)的路網(wǎng)中均表現(xiàn)出良好的預(yù)測(cè)精度;2)穩(wěn)定性高.當(dāng)模型中的超參數(shù)達(dá)到一定閾值后,預(yù)測(cè)精度能夠穩(wěn)定地在一個(gè)小區(qū)間波動(dòng);3)可擴(kuò)展性好.雖然整個(gè)構(gòu)建過(guò)程比較復(fù)雜,但是對(duì)于每一個(gè)階段,甚至某些階段的各個(gè)步驟(如rode2vec),都是可以并行執(zhí)行的,這大大提高了整體的可擴(kuò)展性.

圖1 GRSC模型原理圖Fig.1 Schematic of GRSC

2 相關(guān)工作

2.1 網(wǎng)絡(luò)表征技術(shù)

鏈路預(yù)測(cè)作為復(fù)雜網(wǎng)絡(luò)研究熱點(diǎn)之一,有著很多成熟的模型與方法.呂[7]等人在文獻(xiàn)中對(duì)前人工作進(jìn)行了總結(jié),包含基于局部相似性指標(biāo)方法(如基于一階相似性的CN、PA指標(biāo)等)、基于路徑相似性指標(biāo)方法(如基于高階相似性的katz指標(biāo)等)、基于隨機(jī)游走的方法(如基于余弦相似性的CosPlus)等.這些經(jīng)典的啟發(fā)式方法在特定的網(wǎng)絡(luò)中有著十分良好的表現(xiàn),但往往適應(yīng)性不強(qiáng).

網(wǎng)絡(luò)表征技術(shù)(又稱網(wǎng)絡(luò)嵌入技術(shù))旨在將網(wǎng)絡(luò)映射到低維向量空間中,使節(jié)點(diǎn)能夠向量化表示,進(jìn)而進(jìn)行數(shù)據(jù)挖掘任務(wù).復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)表征算法主要分為三種:基于矩陣分解的方法、基于神經(jīng)網(wǎng)絡(luò)的方法和基于隨機(jī)游走的方法.基于矩陣分解的網(wǎng)絡(luò)嵌入技術(shù)主要對(duì)矩陣進(jìn)行線性或者非線性的轉(zhuǎn)化,從而將特征矩陣降維,如SVD[15]通過(guò)奇異值分解進(jìn)行特征分解、SPC[16]通過(guò)譜聚類的方式進(jìn)行相似變換等.基于神經(jīng)網(wǎng)絡(luò)的方法則是利用神經(jīng)網(wǎng)絡(luò)或者深度學(xué)習(xí)技術(shù),學(xué)習(xí)網(wǎng)絡(luò)特征,如LINE[17]利用機(jī)器學(xué)習(xí)方法、SDNE[18]利用深度學(xué)習(xí)方法學(xué)習(xí)網(wǎng)絡(luò)的一階和二階鄰域結(jié)構(gòu)特征.特別地,自然語(yǔ)言處理技術(shù)的快速發(fā)展為復(fù)雜網(wǎng)絡(luò)表征學(xué)習(xí)提供了新的思路,促使了基于隨機(jī)游走的表征方法的產(chǎn)生.DeepWalk[19]采用了深度優(yōu)先遍歷算法進(jìn)行隨機(jī)游走,使用word2vec[20]算法進(jìn)行表征嵌入,得到了節(jié)點(diǎn)在d維向量空間中的映射;Node2vec[21]對(duì)DeepWalk算法進(jìn)一步優(yōu)化,通過(guò)調(diào)節(jié)初始化的偏移概率增加探索鄰域的靈活性.網(wǎng)絡(luò)表征通常作為普適方法應(yīng)用于不同的網(wǎng)絡(luò)中,在多數(shù)情況下,將其直接用于路網(wǎng)鏈路預(yù)測(cè)優(yōu)于一些經(jīng)典的啟發(fā)式算法,但針對(duì)性較差,需要額外的措施來(lái)提升效果.

2.2 子圖排序算法

在基于子圖模式的復(fù)雜網(wǎng)絡(luò)相關(guān)研究中,基本思路是通過(guò)特定的選取規(guī)則和排序算法,從原始網(wǎng)絡(luò)中生成一系列子圖,繼而對(duì)子圖進(jìn)行特征提取與分類,實(shí)現(xiàn)數(shù)據(jù)挖掘任務(wù).在此過(guò)程中,子圖排序算法至關(guān)重要,排序的好壞直接影響著子圖對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的刻畫程度.一般情況下子圖排序算法是一個(gè)迭代收斂的過(guò)程.Weisfeiler-Lehman[22]算法在每一次迭代中根據(jù)節(jié)點(diǎn)自身原有標(biāo)簽以及鄰居標(biāo)簽來(lái)更新自身的標(biāo)簽,之后通過(guò)字典序?qū)φ麄€(gè)子圖進(jìn)行重新排序.Hashing-based WL[23]算法通過(guò)一個(gè)哈希函數(shù)對(duì)節(jié)點(diǎn)的標(biāo)簽賦予權(quán)重值以降低復(fù)雜度,但是容易出現(xiàn)迭代不收斂問(wèn)題.最近,Palette-WL算法[12]結(jié)合了WL算法收斂性和Hashing-based WL時(shí)間復(fù)雜性低的優(yōu)點(diǎn),但其選取Nauty算法[24]作為最后的排序,從子圖提取的有效信息較少.

3 模型的設(shè)計(jì)與實(shí)現(xiàn)

GRSC模型的主要思想是將目標(biāo)邊通過(guò)一定的規(guī)則生成一個(gè)包含k個(gè)節(jié)點(diǎn)的子圖,結(jié)合路網(wǎng)表征算法road2vec,構(gòu)建對(duì)應(yīng)的廣義路網(wǎng)子圖特征,然后參與到鏈路預(yù)測(cè)分類訓(xùn)練算法中.整個(gè)模型的構(gòu)建可以分為以下三個(gè)階段:

1)通過(guò)road2vec進(jìn)行路網(wǎng)表征.首先根據(jù)我們提出的隨機(jī)游走概率模型獲得路網(wǎng)游走序列,進(jìn)而通過(guò)SGD算法學(xué)習(xí)到每個(gè)頂點(diǎn)的d維向量表示.

2)構(gòu)建廣義路網(wǎng)子圖特征.根據(jù)一定的選取規(guī)則和提出的排序算法得到有序k個(gè)節(jié)點(diǎn),生成封閉子圖對(duì)應(yīng)的子圖結(jié)構(gòu)特征,結(jié)合1)中學(xué)習(xí)得到的表征向量,生成游走距離特征,構(gòu)建總特征.

3)通過(guò)logistic回歸模型對(duì)廣義子圖特征進(jìn)行訓(xùn)練,學(xué)習(xí)節(jié)點(diǎn)連邊與廣義路網(wǎng)子圖特征之間的關(guān)系.

3.1 路網(wǎng)分析與定義

在GIS領(lǐng)域,對(duì)實(shí)際路網(wǎng)進(jìn)行抽象通常會(huì)有兩種方法:一種是廣義拓?fù)浞椒?即將道路作為邊,道路交叉口作為節(jié)點(diǎn),如圖2(b);一種是對(duì)偶拓?fù)浞椒?即將道路按名稱映射為節(jié)點(diǎn),道路的交叉口映射為邊,如圖2(c).相較于廣義拓?fù)?對(duì)偶拓?fù)淠芨由钊氲胤治雎肪W(wǎng)結(jié)構(gòu)和道路特性,如道路間的連接關(guān)系,路網(wǎng)的連通性等.此外,對(duì)偶拓?fù)涑橄蟪鰜?lái)的路網(wǎng)模型更加契合復(fù)雜網(wǎng)絡(luò)的輸入要求,因此采用路網(wǎng)對(duì)偶圖作為研究目標(biāo).

通過(guò)對(duì)路網(wǎng)的分析,發(fā)現(xiàn)不同地域、不同城市的路網(wǎng)在很多方面差異明顯,如一線大城市更多為環(huán)狀方格狀網(wǎng)絡(luò),而三線城市更多為放射狀網(wǎng)絡(luò)[25].與此同時(shí),不同類型的路網(wǎng)在結(jié)構(gòu)上又有著類似的特征,比如局部結(jié)構(gòu)多為平行的橫縱交錯(cuò)道路,道路交叉口相關(guān)的道路往往只有兩三條等,而這些特征在對(duì)偶圖里面以一種十分有趣的方式表現(xiàn)出來(lái),稱之為路網(wǎng)三角結(jié)構(gòu)的特殊性.一方面,兩個(gè)相鄰的橫(縱)干道(如圖2(b)中的3,9),雖然與其共同相交的道路很多,但是兩者基本不會(huì)有交叉口,這一特點(diǎn)阻礙了路網(wǎng)對(duì)偶圖中三角結(jié)構(gòu)的建立;另一方面路網(wǎng)對(duì)偶圖雖然具有一定量的三角結(jié)構(gòu),但是基本是由三條路與其交叉口構(gòu)成的,也就是類似圖2(b)中的7,9,10三條路構(gòu)成的.這一發(fā)現(xiàn)給我們的后續(xù)工作提供了重要參考價(jià)值.

圖2 路網(wǎng)表示方式Fig.2 Urban road network representation

定義圖G=(V,E)為一個(gè)無(wú)向連通圖,其中V={v1,v2,…,vn}為頂點(diǎn)集合,E?V×V為圖中無(wú)向邊的集合,定義N=|V|為圖G節(jié)點(diǎn)個(gè)數(shù),M=|E|為邊的個(gè)數(shù).用鄰接矩陣A來(lái)表示圖G,如果vi與vj有連邊則Aij=1,否則Aij=0.具體描述為:

(1)

定義d(vi,vj)為節(jié)點(diǎn)vi與vj之間最短路徑長(zhǎng)度,即從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj之間所有路徑的邊數(shù)長(zhǎng)度最小值.degree(c)代表節(jié)點(diǎn)的度.Γ(c)或者Γ1(c)代表節(jié)點(diǎn)c(c∈V)的所有路徑長(zhǎng)度為1的節(jié)點(diǎn)集合,即一階鄰居集合,Γn(c)代表節(jié)點(diǎn)c的所有路徑長(zhǎng)度為n的節(jié)點(diǎn)集合,即n階鄰居集合.特別的,Γ0(c)代表節(jié)點(diǎn)c本身.定義e=(vpair-0,vpair-1)為目標(biāo)邊,v={vpair-0,vpair-1}為目標(biāo)節(jié)點(diǎn)對(duì)集合.

3.2 網(wǎng)絡(luò)表征模型road2vec

本小節(jié)提出了一種新的基于隨機(jī)游走的網(wǎng)絡(luò)表征模型road2vec,將應(yīng)用在路網(wǎng)上的隨機(jī)游走策略賦予了具體的意義:模擬物體在真實(shí)路網(wǎng)上的行走過(guò)程.road2vec首先根據(jù)隨機(jī)游走策略生成一系列的游走序列,然后根據(jù)游走序列對(duì)路網(wǎng)進(jìn)行網(wǎng)絡(luò)表征,將其嵌入到d維的向量空間中,最后根據(jù)表征結(jié)果定義節(jié)點(diǎn)與節(jié)點(diǎn)間的隨機(jī)游走距離,作為子圖特征的參照指標(biāo).

3.2.1 隨機(jī)游走策略

為了模擬物體在實(shí)際路網(wǎng)上的行走過(guò)程,更好地使物體探索整個(gè)網(wǎng)絡(luò),設(shè)定了兩個(gè)基本行走規(guī)則:

1)單方向行走.單方向行走有兩個(gè)方面的表現(xiàn):一是在單條路上行走過(guò)程不能折返;二是行走到某個(gè)交叉路口時(shí),以很小概率選擇原路作為行走目標(biāo).

2)有傾向性地選擇.在選擇下一條路的時(shí)候,傾向選擇交叉口數(shù)目更多的路作為下一個(gè)目標(biāo),這樣可以保證下次選擇道路時(shí)有更多的選擇,即有更大的可能對(duì)城市進(jìn)行探索.

顯然,根據(jù)這樣的策略進(jìn)行隨機(jī)游走,我們會(huì)盡可能地遠(yuǎn)離起始點(diǎn),對(duì)城市道路進(jìn)行深度探索.

接下來(lái)探討游走策略在路網(wǎng)對(duì)偶圖中的具體實(shí)現(xiàn).當(dāng)行走到網(wǎng)絡(luò)中某一個(gè)節(jié)點(diǎn)時(shí),需要從當(dāng)前節(jié)點(diǎn)的所有一階鄰居中選擇一個(gè)節(jié)點(diǎn)作為下一個(gè)行走對(duì)象.如圖3(a)所示,t為行走前一個(gè)節(jié)點(diǎn),v為當(dāng)前節(jié)點(diǎn),Γ(v)={X1,X2,X3,t}構(gòu)成了節(jié)點(diǎn)v一階鄰居集合.定義wvx(x∈Γ(v))為節(jié)點(diǎn)v與節(jié)點(diǎn)x的偏向權(quán)重,權(quán)重與行走的選擇概率成正比,即權(quán)重越大則選擇x為行走下一站的概率就越大.wvx的計(jì)算公式如下:

(2)

圖3 隨機(jī)游走策略在對(duì)偶圖的實(shí)現(xiàn)Fig.3 Implementation of random walk strategy in dual graph

其中ε為常量,通常取很小的值,代表“返回權(quán)重”,即行走過(guò)程中折返的權(quán)重.d(t,x)表示節(jié)點(diǎn)t與節(jié)點(diǎn)x的最短路徑長(zhǎng)度,易知當(dāng)d(t,x)取值為0時(shí),x節(jié)點(diǎn)為t節(jié)點(diǎn);d(t,x)取值為1時(shí),說(shuō)明t、v、x三個(gè)頂點(diǎn)構(gòu)成三角結(jié)構(gòu),由三角結(jié)構(gòu)的特殊性可知,此時(shí)選擇x作為下一節(jié)點(diǎn)需要返回,違反了單向行走原則;當(dāng)d(t,x)取值為2時(shí)將x的度作為偏向權(quán)重.定義px(x∈Γ(v))為選取x為下一行走節(jié)點(diǎn)的概率,可以得出:

(3)

圖3(b)展示了當(dāng)ε取0.01時(shí)的概率分布.

3.2.2 網(wǎng)絡(luò)表征

通過(guò)游走策略得到一系列游走序列后,需要將路網(wǎng)表征到一個(gè)d維向量空間中,本文采用了與node2vec相同的方式,將特征學(xué)習(xí)表示為最大似然優(yōu)化問(wèn)題.

算法1.路網(wǎng)表征算法road2vec

輸入:路網(wǎng)G=(V,E)、返回權(quán)重ε、表征維度d、每個(gè)節(jié)點(diǎn)游走次數(shù)n、游走長(zhǎng)度l、上下文窗口大小w

輸出:|V|×d矩陣W,代表所有節(jié)點(diǎn)的表征向量

1. Initializewalksto Empty

2. 根據(jù)式(3)計(jì)算概率集合P=calculate(G,ε)

3. foriter←1 tondo

4. for all nodesu∈Vdo

5.walk=rode2vecWalk(G,u,P,l)

6. appendwalktowalks

end for

end for

7.W=SGD(walks,w,d)

8. returnW

9.road2vecWalk(GraphG,nodeu,mapP,lengthl)

10. Initializewalktou

11. foriter←1 toldo

12.cur_node=walk[-1]

13.neighbors=GetNeighbors(cur_node)

14. Ifcur_node=u

15.next_node=find_next(cur_node,P,neighbors)

16. else

17.pre_node=walk[-2]

18.next_node=find_next(cur_node,P,pre_node,neighbors)

19. appendnext_nodetowalk

20. end for

21. Returnwalk

定義g:V→Rd作為網(wǎng)絡(luò)節(jié)點(diǎn)到d維空間的映射函數(shù).對(duì)于任意一個(gè)節(jié)點(diǎn)c∈V,Λ(c)?V代表以節(jié)點(diǎn)c作為行走起點(diǎn),根據(jù)游走策略生成的游走序列節(jié)點(diǎn)集合,條件概率P(Λ(c)|g(c))代表節(jié)點(diǎn)c的特征向量出現(xiàn)其鄰居節(jié)點(diǎn)的可能性,定義目標(biāo)函數(shù):

(4)

同樣,為了使目標(biāo)函數(shù)更容易處理,假設(shè)概率分布具有條件獨(dú)立性,對(duì)于每個(gè)節(jié)點(diǎn)向量出現(xiàn)其鄰近點(diǎn)的概率等于鄰近點(diǎn)中每個(gè)點(diǎn)出現(xiàn)概率的乘積,可以得到如下式子:

(5)

另外,根據(jù)節(jié)點(diǎn)的對(duì)稱性,源節(jié)點(diǎn)和圖中其它節(jié)點(diǎn)在特征空間中具有彼此對(duì)稱的效果.可以得出:

(6)

根據(jù)上式,我們可以將目標(biāo)函數(shù)進(jìn)一步優(yōu)化為以下形式

(7)

其中,Zu=∑u∈Vexp(g(u)·g(v)).隨后利用梯度下降算法stochastic gradient ascent(SGD)最優(yōu)化目標(biāo)函數(shù),不難看出,Zu的計(jì)算需要遍歷圖中的所有節(jié)點(diǎn),當(dāng)圖的規(guī)模非常大時(shí)需要很高的時(shí)間開(kāi)銷,因此采用負(fù)采樣算法[26]提高效率.road2vec整體過(guò)程如算法1所示,其中road2vecWalk表示根據(jù)隨機(jī)游走策略生成游走序列的過(guò)程.

通過(guò)road2vec將網(wǎng)絡(luò)嵌入到d維空間,得到節(jié)點(diǎn)的向量表示,在此基礎(chǔ)上,定義節(jié)點(diǎn)與節(jié)點(diǎn)之間的游走距離:

(8)

其中x,y∈V,代表圖中任意兩個(gè)節(jié)點(diǎn),x、y代表x、y在d維空間上的表征向量.根據(jù)本節(jié)提出的游走策略和表征方法的目標(biāo)函數(shù)可以得到一個(gè)合理的猜測(cè):兩個(gè)節(jié)點(diǎn)的游走距離越小,表明節(jié)點(diǎn)在向量空間上的距離越近,在路網(wǎng)上表示為兩條道路出現(xiàn)在同一條游走序列的概率越大,兩條路之間的關(guān)系對(duì)彼此越重要.

3.3 廣義路網(wǎng)子圖構(gòu)建

3.3.1 子圖結(jié)構(gòu)特征構(gòu)建

GRSC中目標(biāo)邊的子圖結(jié)構(gòu)特征為其封閉子圖鄰接矩陣的線性表示.封閉子圖指的是從圖的結(jié)構(gòu)層面出發(fā),結(jié)合路網(wǎng)表征算法,得到與待測(cè)節(jié)點(diǎn)對(duì)關(guān)系最緊密的k個(gè)節(jié)點(diǎn),并按照特定的順序重新構(gòu)成的子圖.顯然,構(gòu)建子圖需要解決兩個(gè)問(wèn)題:一是以何種規(guī)則選取目標(biāo)邊相關(guān)的子圖節(jié)點(diǎn);二是如何對(duì)選取的節(jié)點(diǎn)進(jìn)行排序,從而使子圖特征更具代表性和普適性.

對(duì)于第一點(diǎn),GRSC以目標(biāo)節(jié)點(diǎn)對(duì)為中心,向外擴(kuò)散的方式選取節(jié)點(diǎn).具體方法為:首先選取目標(biāo)節(jié)點(diǎn)對(duì)v的所有一階鄰居節(jié)點(diǎn),判斷此時(shí)選取節(jié)點(diǎn)數(shù)量是否大于k;不大于k則繼續(xù)選取所有二階鄰居節(jié)點(diǎn),以此類推.直到選出距離目標(biāo)邊距離最近的m(m≥k-2)個(gè)節(jié)點(diǎn),與目標(biāo)節(jié)點(diǎn)對(duì)共同構(gòu)成子圖節(jié)點(diǎn)集合Ψ(v).

得到了子圖節(jié)點(diǎn)集合后,我們需要對(duì)子圖節(jié)點(diǎn)進(jìn)行結(jié)構(gòu)化編號(hào).此外,如果子圖節(jié)點(diǎn)集合的節(jié)點(diǎn)數(shù)量大于k,還需要根據(jù)一定的規(guī)則淘汰掉一些節(jié)點(diǎn),從而保證封閉子圖是一個(gè)固定的包含k個(gè)節(jié)點(diǎn)的子圖.這本質(zhì)是一個(gè)迭代排序的過(guò)程.

定義rank(c)代表節(jié)點(diǎn)c此時(shí)的編號(hào),節(jié)點(diǎn)的rank值越小代表節(jié)點(diǎn)排序越靠前,最后子圖節(jié)點(diǎn)排序結(jié)果是按照rank值從小到大排列(沒(méi)有重復(fù)的rank值).如果此時(shí)節(jié)點(diǎn)數(shù)量大于k,則取前k個(gè)rank值最小的元素作為邊對(duì)應(yīng)的封閉子圖.

整個(gè)結(jié)構(gòu)化編號(hào)過(guò)程可以分為初始標(biāo)號(hào)、迭代排序和最終排序三個(gè)步驟,具體描述如下:

1)初始標(biāo)號(hào).為了保留節(jié)點(diǎn)選取規(guī)則的方向性,通過(guò)初始化rank值來(lái)保持節(jié)點(diǎn)選取順序,對(duì)于子圖中的所有節(jié)點(diǎn)c∈Ψ(v),用節(jié)點(diǎn)c與vpair-0和vpair-1的最短路徑長(zhǎng)度乘積作為點(diǎn)c的初始權(quán)重值:

d(c)=d(c,vpair-0)·d(c,vpair-1)

(9)

其中d(c)表示節(jié)點(diǎn)c的初始權(quán)重,d(c,v)表示節(jié)點(diǎn)c與節(jié)點(diǎn)v之間的最短路徑長(zhǎng)度.隨后根據(jù)權(quán)重值序列對(duì)節(jié)點(diǎn)賦予初始rank值.直觀地可以看出,待測(cè)節(jié)點(diǎn)對(duì)的初始權(quán)重都為0,故其初始rank值為1.距離待測(cè)節(jié)點(diǎn)對(duì)越遠(yuǎn),其初始權(quán)重值就越大,對(duì)應(yīng)的初始rank值越大.

2)迭代排序.根據(jù)PALETTE-WL算法對(duì)子圖進(jìn)行迭代排序,每次迭代中節(jié)點(diǎn)權(quán)重的更新公式為:

(10)

其中rank(c)代表當(dāng)前節(jié)點(diǎn)c的rank值,φ(n)為第n個(gè)素?cái)?shù)值.文獻(xiàn)[12]證明了PALETTE-WL算法同時(shí)具有穩(wěn)定性和一致性,且在子圖節(jié)點(diǎn)數(shù)范圍之內(nèi)能夠快速收斂.

3)最終排序.根據(jù)式(10)迭代收斂后,可能還有一些節(jié)點(diǎn)rank值相等,需要在保證rank值不同的節(jié)點(diǎn)序列不變的情況下對(duì)rank值相同的節(jié)點(diǎn)進(jìn)行最后的排序.類比節(jié)點(diǎn)與節(jié)點(diǎn)間的游走距離,定義節(jié)點(diǎn)c與目標(biāo)邊e的隨機(jī)游走距離:

wd(e,c)=sqrt(wd(c,vpair-0)·wd(c,vpair-1))

(11)

權(quán)重更新公式為:

(12)

根據(jù)此規(guī)則更新權(quán)重后,對(duì)子圖節(jié)點(diǎn)進(jìn)行最后一次排序,如果此時(shí)節(jié)點(diǎn)個(gè)數(shù)大于k,淘汰節(jié)點(diǎn)序列中的前k個(gè)之外的節(jié)點(diǎn),得到個(gè)數(shù)為k且rank值從小到大的節(jié)點(diǎn)序列χ.最后,根據(jù)χ構(gòu)建封閉子圖,將子圖鄰接矩陣按行連接線性表示,作為子圖結(jié)構(gòu)特征s_feature.無(wú)論是否連邊,我們都將鄰接矩陣中目標(biāo)節(jié)點(diǎn)對(duì)相應(yīng)位置置0,這樣可以在構(gòu)造過(guò)程中去除目標(biāo)邊的影響.

3.3.2 游走距離特征

本節(jié)根據(jù)χ對(duì)子圖結(jié)構(gòu)特征進(jìn)行拓展,將χ中所有節(jié)點(diǎn)(除了目標(biāo)節(jié)點(diǎn)對(duì))與目標(biāo)節(jié)點(diǎn)對(duì)的游走距離作為新的特征加入到總特征的構(gòu)建過(guò)程中,稱之為游走距離特征(wd_feature).由節(jié)點(diǎn)排序算法的規(guī)則可以得出,目標(biāo)節(jié)點(diǎn)對(duì){vpair-0,vpair-1}在χ中始終占據(jù)著第一和第二的位置,所以構(gòu)建游走距離特征的方法可以描述為,定義一個(gè)初始化為空的數(shù)組,從χ的第三個(gè)頂點(diǎn)依次向后遍歷,對(duì)每次遍歷的節(jié)點(diǎn)c∈χ,計(jì)算c在游走向量空間中與目標(biāo)節(jié)點(diǎn)對(duì)之間的游走距離{wd(c,χ(0)),wd(c,χ(1))},計(jì)算完畢后將結(jié)果追加到數(shù)組的尾部.迭代k-2次,即遍歷整個(gè)節(jié)點(diǎn)序列,此時(shí)數(shù)組就是我們所求的游走距離特征,特征所含元素為2k-4個(gè).

隨機(jī)游走距離的加入具有兩方面的意義,一是從網(wǎng)絡(luò)表征層面刻畫了子圖節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)對(duì)之間的相對(duì)位置關(guān)系,彌補(bǔ)了僅由子圖結(jié)構(gòu)特征所含信息的局限性.二是該特征的引入對(duì)應(yīng)了在排序編號(hào)過(guò)程中式(12)的排序規(guī)則,使得排序和擴(kuò)展具有形式和意義上的一致性.

至此,目標(biāo)邊的子圖結(jié)構(gòu)特征、游走距離特征已經(jīng)構(gòu)建完畢,兩者結(jié)合構(gòu)成了廣義子圖特征,即general_feature.整個(gè)構(gòu)建過(guò)程如算法2所示,其中s函數(shù)的作用是根據(jù)權(quán)重大小重新調(diào)整節(jié)點(diǎn)序列順序.

算法2.廣義子圖特征構(gòu)建算法

輸入:路網(wǎng)G=(V,E)、節(jié)點(diǎn)對(duì)v={vpair-0,vpair-1},子圖節(jié)點(diǎn)個(gè)數(shù)k、表征矩陣W

輸出:廣義子圖特征general_feature

1. 通過(guò)節(jié)點(diǎn)對(duì)擴(kuò)散方法得到子圖節(jié)點(diǎn)集合Ψ(v)

2. define Ψ(v) as χ

3. calculated(c) by(9)for allc∈χ

4.rank(χ)=s(d(χ))

5. whilerank(χ) has not converged do

6. calculate hashing valuesh(c) for allc∈χ

7. update allrank(χ)=s(h(χ))

8. end while

9. finally calculatewalking-distancel(c)

10. then updaterank(χ)=s(l(c))

11. 根據(jù)最終排序結(jié)果取前k個(gè)節(jié)點(diǎn)χ=pickTopK(χ,k)

12. 取封閉子圖鄰接矩陣線性表示作為子圖結(jié)構(gòu)特征:

s_feature=build-s-feature(G,χ)

13. 根據(jù)3.3.2描述計(jì)算游走距離特征wd_feature

14. 將兩種特征線性結(jié)合得到廣義路網(wǎng)子圖特征

general_feature=combine(s_feature,wd_feature)

15. returngeneral_feature

3.3 訓(xùn)練分類模型

將得到的一系列目標(biāo)邊的廣義路網(wǎng)子圖特征作為輸入,結(jié)合目標(biāo)邊的實(shí)際連邊情況,訓(xùn)練logistic回歸分類模型,從而學(xué)習(xí)連邊與廣義路網(wǎng)子圖特征之間的關(guān)系,隨后將訓(xùn)練好的模型用于路網(wǎng)鏈路預(yù)測(cè)任務(wù)中.

4 實(shí) 驗(yàn)

4.1 數(shù)據(jù)集構(gòu)建

本文收集了包含中國(guó)和美國(guó)境內(nèi)的6個(gè)城市路網(wǎng)作為數(shù)據(jù)集,每個(gè)路網(wǎng)對(duì)應(yīng)的節(jié)點(diǎn)、邊、平均度和聚類系數(shù)如表1所示.從表中可以看出,不同地區(qū)的城市路網(wǎng)規(guī)模具有明顯的層次性差異.此外,雖然網(wǎng)絡(luò)規(guī)模不同,但是數(shù)據(jù)集中路網(wǎng)的平均度基本穩(wěn)定分布在在4左右,相對(duì)于政治博客網(wǎng)絡(luò)PB(平均度31.2),UsAir網(wǎng)絡(luò)(平均度12.8),蛋白質(zhì)相互作用網(wǎng)絡(luò)(平均度9.1),路網(wǎng)是比較稀疏的,這也從一定層面上反映出在路網(wǎng)上,子圖結(jié)構(gòu)特征所包含的信息量是比較少的.聚類系數(shù)代表網(wǎng)絡(luò)的集聚程度,從表中明顯可以看出路網(wǎng)集聚程度普遍較低.

表1 城市路網(wǎng)數(shù)據(jù)集
Table 1 Urban road network datasets

城市名稱節(jié)點(diǎn)邊平均度聚類系數(shù)HengYang.China72614303.930.192ChangSha.China5018104974.180.221BeiJing.China11319213223.770.203Rockford.USA4767105594.430.294Seattle.USA8191177324.320.244SanFrancisco.USA11669240674.120.242

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

鏈路預(yù)測(cè)模型的預(yù)測(cè)效果評(píng)價(jià)方法一般都采用AUC[4]評(píng)價(jià)指標(biāo),AUC指標(biāo)主要從模型的整體上來(lái)衡量預(yù)測(cè)的準(zhǔn)確性,可以理解為在測(cè)試集中邊的分?jǐn)?shù)值比隨機(jī)選擇的一個(gè)不存在的邊的分?jǐn)?shù)值高的概率.當(dāng)訓(xùn)練集中所有分?jǐn)?shù)都是隨機(jī)產(chǎn)生的時(shí)候,AUC的值會(huì)近似等于0.5,AUC超過(guò)0.5的大小代表鏈路預(yù)測(cè)模型比較隨機(jī)模型的優(yōu)越性強(qiáng)度,差值越大,說(shuō)明預(yù)測(cè)效果越好.

4.3 實(shí)驗(yàn)對(duì)比

實(shí)驗(yàn)環(huán)境為:centOS 7,4核cpu,128G內(nèi)存,實(shí)驗(yàn)方式為單線程順序執(zhí)行,無(wú)并發(fā)處理機(jī)制.

4.3.1 預(yù)測(cè)精度與時(shí)間耗費(fèi)

本文將GRSC算法與5種類型,共15種鏈路預(yù)測(cè)方法進(jìn)行比較.主要包括:

1)基于局部信息相似性指標(biāo)的方法.這里相似性指標(biāo)只考慮一階相似性,選取了共同鄰居指標(biāo)CN、Jaccard指標(biāo)、Adamic-Adar(AA)指標(biāo)、優(yōu)先鏈接指標(biāo)PA四種;

2)基于路徑相似性指標(biāo)的方法.這里選取了考慮三階鄰居的LP(LocalPath),考慮高階相似性的Katz指標(biāo)以及考慮節(jié)點(diǎn)間路徑期望值的LHN-II指標(biāo)三種;

3)基于隨機(jī)游走的方法.該類方法指定不同的隨機(jī)游走策略評(píng)價(jià)節(jié)點(diǎn)之間的連邊相似度,該類對(duì)比試驗(yàn)包括余弦相似性指標(biāo)CosPlus,帶重啟的隨機(jī)游走算法RWR,SimRank算法和局部隨機(jī)游走算法LRW;

4)基于網(wǎng)絡(luò)表征的方法.選取了三種不同類型的網(wǎng)絡(luò)表征算法,分別為L(zhǎng)INE,node2vec,SPC;

5)基于子圖模式的方法WLNM.

在參數(shù)方面,設(shè)置katz的權(quán)重因子為0.001,LHNII的參數(shù)φ=0.9,RWR的返回概率為0.85,SimRank的衰減參數(shù)為0.6,LRW的有限步數(shù)為5.對(duì)于所有的網(wǎng)絡(luò)表征算法,設(shè)置嵌入維度為128,對(duì)于Node2vec,設(shè)置其隨機(jī)游走步長(zhǎng)為50,節(jié)點(diǎn)遍歷次數(shù)為10,Node2vec的概率值p=2,q=1.WLNMm表示子圖節(jié)點(diǎn)個(gè)數(shù)選擇為m.

對(duì)于GRSC,為了對(duì)比的公平性,設(shè)置表征維度d=128,節(jié)點(diǎn)游走次數(shù)n=10,游走長(zhǎng)度l=50,返回權(quán)重默認(rèn)設(shè)置為0.01.同WLNM類似,GRSC10代表子圖節(jié)點(diǎn)個(gè)數(shù)為10,GRSC20代表子圖節(jié)點(diǎn)個(gè)數(shù)為20,以此類推.

表2 對(duì)比算法在路網(wǎng)上的表現(xiàn)
Table 2 Comparison algorithm performance on the datasets

MethodHengYangChangShaBeiJingRockfordSeattleSanFranciscoTimeAUCTimeAUCTimeAUCTimeAUCTimeAUCTimeAUCCN0.020.6020.040.6970.100.7150.040.6880.060.6900.120.701Jaccard0.040.6042.350.69712.670.7162.350.6876.430.69113.050.701AA0.010.6040.450.6973.540.7160.410.6891.350.6913.630.702PA0.020.5940.220.5810.990.6030.190.6330.630.6051.020.674LP0.010.8110.050.8690.180.8530.060.9180.100.8670.210.872Katz0.030.8061.120.9036.280.8701.160.9283.190.8976.160.863LHNⅡ0.220.7734.940.90572.440.8824.560.87316.120.879105.370.836CosPlus1.390.873449.870.9532772.420.940249.090.9651219.680.9452957.170.944RWR0.130.8627.340.92141.330.8798.110.94820.650.91845.970.882SimRank0.140.8175.30.92540.280.9139.690.92332.590.919281.580.878LRW0.040.8600.70.9202.850.8931.430.9582.850.9286.380.915LINE1.230.8917.460.94717.550.92612.560.95014.390.94444.140.922Node2vec1.180.8678.40.94018.810.92311.960.95120.730.94120.840.931SPC1.290.830106.030.9521203.390.950102.440.955475.090.9601116.270.938WLNM10196.940.7181446.330.9492951.700.9591457.570.9532470.370.9503419.200.940WLNM20198.270.7041485.350.9353018.220.9381494.370.9482576.630.9483583.920.916GRSC107.790.90174.230.961230.230.96484.600.971158.180.966259.520.969GRSC2011.740.911115.520.968331.800.970122.950.973226.810.976354.450.977

圖4 對(duì)比算法在路網(wǎng)上的平均表現(xiàn)Fig.4 Average performance on the datasets

各對(duì)比方法在時(shí)間耗費(fèi)AUC準(zhǔn)確度上的表現(xiàn)如表2所示.從表中可以看出,與對(duì)比算法相比,GRSC模型在所有數(shù)據(jù)集中都有著最好的表現(xiàn),特別是在子圖節(jié)點(diǎn)個(gè)數(shù)取到20時(shí),在北京、Rockford、Seattle、SanFrancisco等4個(gè)城市路網(wǎng)中AUC指標(biāo)在97%之上,而表現(xiàn)次優(yōu)的方法在不同城市中不盡相同,如衡陽(yáng)為L(zhǎng)INE(89.1%)、長(zhǎng)沙為CosPlus(95.3%)、北京為WLNM(95.9%)等.表明GRSC在不同路網(wǎng)的適應(yīng)性更強(qiáng),更能有效挖掘不同路網(wǎng)的結(jié)構(gòu)特征.

圖4(a)展示了對(duì)比實(shí)驗(yàn)的平均AUC指標(biāo).可以看出,基于局部相似性指標(biāo)的方法精確度遠(yuǎn)遠(yuǎn)低于其他算法,其中表現(xiàn)最差的為PA算法,平均精確度不到65%,說(shuō)明共同鄰居相關(guān)的相似性對(duì)路網(wǎng)連邊影響不大.基于路徑相似性指標(biāo)的方法表現(xiàn)僅優(yōu)于基于局部相似性算法,其中Katz優(yōu)于LP和LHN-II,表明基于高階相似性的方法優(yōu)于基于低階相似性的方法.基于游走的方法、基于網(wǎng)絡(luò)表征方法和基于子圖模式的方法表現(xiàn)相對(duì)較好,且三者AUC指標(biāo)相差不大,均處于90%-95%的范圍內(nèi),說(shuō)明隨機(jī)游走方法和網(wǎng)絡(luò)表征方法在路網(wǎng)上是有效的.在基于隨機(jī)游走的方法中,CosPlus算法的平均AUC表現(xiàn)最好,同時(shí)超過(guò)了基于表征和基于子圖的方法,在所有對(duì)比方法中排名第三.此外,基于網(wǎng)絡(luò)表征的的方法精確度表現(xiàn)排序?yàn)镾PC、LINE、Node2vec,效果微低于Cosplus與GRSC.GRSC模型在子圖節(jié)點(diǎn)個(gè)數(shù)為10和20的時(shí)候平均AUC分別為95.5%和96.3%,領(lǐng)先于其它的對(duì)比算法.

圖4(b)展示了對(duì)比試驗(yàn)的平均時(shí)間消耗.在所有對(duì)比實(shí)驗(yàn)中,耗時(shí)最短的是基于局部相似性指標(biāo)的方法.耗時(shí)最長(zhǎng)的為基于子圖的WLNM模型,但其在預(yù)測(cè)精度上并沒(méi)有展現(xiàn)出太大的優(yōu)勢(shì),且在規(guī)模較小的城市衡陽(yáng)中的AUC表現(xiàn)甚至低于基于路徑相似性指標(biāo)的方法,印證了單靠子圖模式在稀疏路網(wǎng)上進(jìn)行鏈路預(yù)測(cè)的局限性.GRSC模型在時(shí)間耗費(fèi)上遠(yuǎn)低于精確度排名第3的CosPlus和排名第4的SPC.總之,無(wú)論是在預(yù)測(cè)精度還是時(shí)間耗費(fèi)上,GRSC都表現(xiàn)良好.

4.3.2 超參數(shù)對(duì)結(jié)果的影響

本節(jié)主要探索GRSC模型的超參數(shù)對(duì)結(jié)果的影響,超參數(shù)主要包含子圖節(jié)點(diǎn)數(shù)k、表征維度d、游走步長(zhǎng)l.用控制變量法進(jìn)行測(cè)試比較.圖5展示了在嵌入維度為4,返回權(quán)重取0.01時(shí)子圖節(jié)點(diǎn)數(shù)k對(duì)結(jié)果的影響.從圖中可以看出,當(dāng)k從3到9的過(guò)程中,AUC隨著k的增加變化較快,但增加率一直變小,在k=12后趨于穩(wěn)定.這一特點(diǎn)說(shuō)明在其它參數(shù)固定條件下預(yù)測(cè)精度會(huì)隨著k收斂.同樣,我們采用類似的方法探究了表征維度d,游走步長(zhǎng)l對(duì)結(jié)果的影響,結(jié)果如圖6、圖7所示.圖中都表明在參數(shù)比較小的時(shí)候預(yù)測(cè)精度對(duì)參數(shù)變化十分敏感,但在參數(shù)超過(guò)某一閾值(圖6中d=32,圖7中l(wèi)=64)后,AUC比較穩(wěn)定地在一定區(qū)間內(nèi)上下波動(dòng).這些現(xiàn)象說(shuō)明GRSC具有一定意義上的穩(wěn)定性.

圖5 子圖節(jié)點(diǎn)個(gè)數(shù)k對(duì)結(jié)果的影響Fig.5 Effect of k on the results

圖6 表征維度d對(duì)結(jié)果的影響Fig.6 Effect of d on the results

此外,圖7展示了不同返回權(quán)重ε對(duì)實(shí)驗(yàn)結(jié)果的影響,其中ε取4代表路網(wǎng)平均度.可以看出ε小于1時(shí)AUC明顯高于大于1的表現(xiàn),印證了隨機(jī)游走策略規(guī)則的有效性.在取0.1和0.001時(shí)結(jié)果相近,表明相對(duì)較小的返回權(quán)重已經(jīng)能夠刻畫路網(wǎng)結(jié)構(gòu).

圖7 游走步數(shù)l對(duì)結(jié)果的影響Fig.7 Effect of l on the results

4.4 分析與討論

實(shí)驗(yàn)展示了GRSC模型在路網(wǎng)數(shù)據(jù)集中有著十分好的表現(xiàn),表明在模型實(shí)現(xiàn)上的一些假設(shè)和規(guī)則對(duì)路網(wǎng)鏈路預(yù)測(cè)是有著積極作用的.本節(jié)從一個(gè)新的角度解釋模型的有效性.一方面,GRSC是根據(jù)廣度擴(kuò)散的方式選取目標(biāo)邊子圖節(jié)點(diǎn)的,這樣構(gòu)建的子圖結(jié)構(gòu)特征維持著目標(biāo)邊在廣度方面的鄰域結(jié)構(gòu);另一方面,road2vec設(shè)定了比較小的返回權(quán)重ε,在圖搜索層面相當(dāng)于限制了廣度游走的途徑,更多地讓節(jié)點(diǎn)深度游走,使得節(jié)點(diǎn)的表征更有全局特性.兩者結(jié)合共同構(gòu)建的廣義路網(wǎng)子圖特征兼顧目標(biāo)邊子圖的廣度和深度特性,將子圖刻畫地更有立體性,從而提升了子圖表達(dá)的精確度.

5 結(jié) 論

本文提出的GRSC模型將復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)方法應(yīng)用到路網(wǎng)中.在GRSC中,提出了一種新的針對(duì)路網(wǎng)特性的網(wǎng)絡(luò)嵌入模型,使得游走策略在路網(wǎng)上更有意義.同時(shí),將子圖特征與網(wǎng)絡(luò)嵌入有機(jī)地結(jié)合在一起,共同組成了廣義路網(wǎng)子圖特征,彌補(bǔ)了子圖模式在稀疏路網(wǎng)中信息保留過(guò)少的缺點(diǎn).在實(shí)驗(yàn)評(píng)估階段,GRSC模型在不同國(guó)家,不同層次類型的路網(wǎng)上都有著比較良好的表現(xiàn),超過(guò)了一些最近提出的網(wǎng)絡(luò)表征和基于子圖的方法.但是,該模型因?yàn)椴襟E稍顯復(fù)雜,在無(wú)并行措施下消耗的時(shí)間比較久,不能很好地應(yīng)對(duì)海量的路網(wǎng)數(shù)據(jù).因此,設(shè)計(jì)一套可靠的并行方案以節(jié)省更多的時(shí)間是我們接下來(lái)研究的重點(diǎn).