融合節(jié)點(diǎn)標(biāo)簽與強(qiáng)弱關(guān)系的鏈路預(yù)測(cè)算法

王曙燕，鞏婧怡

西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，西安710121

鏈路預(yù)測(cè)通過(guò)已知的網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)信息等因素[1]，預(yù)測(cè)網(wǎng)絡(luò)中兩節(jié)點(diǎn)連接的可能性或發(fā)現(xiàn)已存在但未識(shí)別的隱式連邊。在社交網(wǎng)絡(luò)中，將用戶(hù)視為節(jié)點(diǎn)，各用戶(hù)社會(huì)關(guān)系視為連邊，對(duì)可能存在關(guān)系的用戶(hù)進(jìn)行鏈路預(yù)測(cè)[2]。

常見(jiàn)的鏈路預(yù)測(cè)方法有：基于節(jié)點(diǎn)屬性信息、基于網(wǎng)絡(luò)結(jié)構(gòu)和最大似然估計(jì)法[3]。然而，僅對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)屬性的預(yù)測(cè)不能夠真實(shí)精確地反映出目標(biāo)網(wǎng)絡(luò)的特性，并且與節(jié)點(diǎn)的屬性信息相比，更容易獲得網(wǎng)絡(luò)的結(jié)構(gòu)信息，而且網(wǎng)絡(luò)的結(jié)構(gòu)信息也相對(duì)比較可靠[4]。Liben-Nowell等[5]通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)相似性分析社交網(wǎng)絡(luò)。后來(lái)出現(xiàn)的基于節(jié)點(diǎn)度的共同鄰居CN（common neighbors）[6]根據(jù)節(jié)點(diǎn)的共同鄰居進(jìn)行推薦。王智強(qiáng)等[7]認(rèn)為可借助鏈路預(yù)測(cè)檢測(cè)由于信息或數(shù)據(jù)的噪聲產(chǎn)生的不必要鏈接。

根據(jù)研究發(fā)現(xiàn)，僅考慮節(jié)點(diǎn)屬性或網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鏈路連接很難對(duì)節(jié)點(diǎn)信息進(jìn)行較完全的刻畫(huà)并不能更加精確地對(duì)節(jié)點(diǎn)進(jìn)行鏈路預(yù)測(cè)。本文提出一種融合節(jié)點(diǎn)標(biāo)簽與強(qiáng)弱關(guān)系的鏈路預(yù)測(cè)（node labels and strong &weak relationships link prediction，NRLP）算法。該算法提取社交網(wǎng)絡(luò)部分子圖，通過(guò)對(duì)局部子圖生成的目標(biāo)矩陣進(jìn)行分解，并將子網(wǎng)絡(luò)結(jié)構(gòu)融入節(jié)點(diǎn)標(biāo)簽、文本屬性與關(guān)系強(qiáng)度的動(dòng)態(tài)權(quán)重。該算法得到的節(jié)點(diǎn)向量兼顧網(wǎng)絡(luò)結(jié)構(gòu)屬性、關(guān)系強(qiáng)弱與節(jié)點(diǎn)屬性，且通過(guò)局部子圖分析預(yù)測(cè)可能性比全圖降低算法運(yùn)行時(shí)間。

1 相關(guān)工作

鏈路預(yù)測(cè)是預(yù)測(cè)網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)是否可能具有鏈路[8]。鑒于網(wǎng)絡(luò)的普遍存在，它有許多應(yīng)用，如朋友推薦[9-10]、知識(shí)圖完成[11]和代謝網(wǎng)絡(luò)重建[12]等。

一般來(lái)說(shuō)，鏈路預(yù)測(cè)的研究可分為三大類(lèi)：?jiǎn)l(fā)式方法、基于網(wǎng)絡(luò)嵌入的方法和基于圖神經(jīng)網(wǎng)絡(luò)的方法[4]。啟發(fā)式方法[13-14]側(cè)重于通過(guò)特定假設(shè)下節(jié)點(diǎn)之間的不同啟發(fā)式節(jié)點(diǎn)相似性來(lái)估計(jì)連邊的可能性。現(xiàn)有的啟發(fā)式算法通常包括基于共同鄰居CN 法[15]，當(dāng)節(jié)點(diǎn)的共同鄰居越多則對(duì)其連邊，但此方法與現(xiàn)實(shí)生活情況不符。基于路徑的算法：余弦相似性法[16]、Jaccard法[17]、基于路徑的相似性法[18]（如Katz指標(biāo)[19]、LHN-II指標(biāo)[20]）等?；诠餐従拥牡乃惴ū容^簡(jiǎn)單直觀，但未挖掘網(wǎng)絡(luò)所含有的豐富信息導(dǎo)致算法精確度受限，基于路徑的算法雖考慮節(jié)點(diǎn)間的路徑信息但計(jì)算復(fù)雜度較大。并且啟發(fā)式方法對(duì)節(jié)點(diǎn)何時(shí)可能存在鏈接有很強(qiáng)的假設(shè)，當(dāng)其假設(shè)在目標(biāo)場(chǎng)景中不成立時(shí)，可能會(huì)失敗[21]。

網(wǎng)絡(luò)表示學(xué)習(xí)通過(guò)將節(jié)點(diǎn)表示為低維向量保留網(wǎng)絡(luò)結(jié)構(gòu)，然而在大型信息網(wǎng)絡(luò)中該方法計(jì)算復(fù)雜、效率較低。隨著skip-gram[22]算法出現(xiàn)的啟發(fā)，DeepWalk[23]將基于隨機(jī)游走產(chǎn)生的節(jié)點(diǎn)序列放入skip-gram模型輸出表示。張學(xué)佩[24]定義了局部隨機(jī)游走的節(jié)點(diǎn)相似度指標(biāo)，并與其他相似性指標(biāo)進(jìn)行比較。結(jié)果表明，其提出的算法具有更低的計(jì)算復(fù)雜度。然而基于網(wǎng)絡(luò)嵌入大多數(shù)算法具有很高的精度，但在學(xué)習(xí)節(jié)點(diǎn)表示時(shí)沒(méi)有考慮到節(jié)點(diǎn)和邊緣的豐富屬性。

隨著現(xiàn)有網(wǎng)絡(luò)常用圖表示，其中節(jié)點(diǎn)表示個(gè)體或群體，邊表示個(gè)體或群體間的交互行為[25]，觀察節(jié)點(diǎn)和邊結(jié)構(gòu)的內(nèi)部特征，在保留復(fù)雜網(wǎng)絡(luò)本身特征的同時(shí)，可以生成其獨(dú)特的屬性。為了提高預(yù)測(cè)性能，劉樹(shù)新等[26]在網(wǎng)絡(luò)拓?fù)涮卣髦性黾痈郊有畔ⅲ谔嵘阅艿耐瑫r(shí)會(huì)增加計(jì)算復(fù)雜性。并且由于網(wǎng)絡(luò)的復(fù)雜性，導(dǎo)致連接關(guān)系存在優(yōu)劣性[27]，文獻(xiàn)[28]提出可以用權(quán)重矩陣衡量關(guān)系的方法。

通過(guò)對(duì)現(xiàn)有研究成果的觀察，時(shí)間效率和精確度都是鏈路預(yù)測(cè)中重要的因素?？紤]現(xiàn)有研究在信息與屬性方面的挖掘不足，本文采用雙半徑節(jié)點(diǎn)標(biāo)簽（double radius node label，DRNL）算法[29]，借鑒TELP 算法的思想，在分解目標(biāo)網(wǎng)絡(luò)的同時(shí)融入節(jié)點(diǎn)屬性信息，并在其中考慮同一節(jié)點(diǎn)對(duì)于不同中心節(jié)點(diǎn)的關(guān)系強(qiáng)弱，賦予不同的動(dòng)態(tài)權(quán)值，提出一種融合節(jié)點(diǎn)標(biāo)簽與強(qiáng)弱關(guān)系的鏈路預(yù)測(cè)NRLP 算法。其不僅通過(guò)局部子圖可以更快速地挖掘網(wǎng)絡(luò)所含節(jié)點(diǎn)位置信息，且在學(xué)習(xí)節(jié)點(diǎn)表示時(shí)考慮到節(jié)點(diǎn)和邊緣的關(guān)系屬性映射現(xiàn)實(shí)生活中的不同關(guān)系強(qiáng)度。最后，在三個(gè)數(shù)據(jù)上進(jìn)行驗(yàn)證，并與常見(jiàn)鏈路預(yù)測(cè)算法進(jìn)行對(duì)比，結(jié)果證明本文算法預(yù)測(cè)效果較好。

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

對(duì)于網(wǎng)絡(luò)圖G=(V,E),其中，V為點(diǎn)集，E為邊集，屬性矩陣為T(mén)∈ft為屬性特征的維度。由文獻(xiàn)[30]的結(jié)果表明，局部子圖保留了與鏈接相關(guān)的豐富信息，所以給定兩個(gè)節(jié)點(diǎn)x,y∈V，生成(x,y)的h深度局部子圖。

2.1 節(jié)點(diǎn)標(biāo)簽

為每個(gè)節(jié)點(diǎn)生成節(jié)點(diǎn)標(biāo)簽，表示為函數(shù)fl:V→N。對(duì)于在局部子圖的每一個(gè)節(jié)點(diǎn)i，為其生成一個(gè)整數(shù)標(biāo)簽f(i)，在局部子圖中使用不同的標(biāo)簽來(lái)標(biāo)記中心節(jié)點(diǎn)與其他節(jié)點(diǎn)。通過(guò)節(jié)點(diǎn)表示差異性，在網(wǎng)絡(luò)中準(zhǔn)確找到目標(biāo)節(jié)點(diǎn)并獲得其相應(yīng)結(jié)構(gòu)信息[31]。

節(jié)點(diǎn)i在一個(gè)局部子圖中的拓?fù)湮恢每梢杂盟鄬?duì)于兩個(gè)中心節(jié)點(diǎn)的半徑(d(i,x),d(i,y))表述。如果d(i,x)=d(j,x)并且d(i,y)=d(j,y)，則節(jié)點(diǎn)i和節(jié)點(diǎn)j在圖中擁有相同標(biāo)簽。

首先，將中心節(jié)點(diǎn)標(biāo)簽設(shè)置為1。然后，對(duì)于(d(i,x),d(i,y))=(1,1)的任何節(jié)點(diǎn)，設(shè)置標(biāo)簽f(i)=2。半徑為（1，2）或（2，1）的節(jié)點(diǎn)標(biāo)簽為3，以此類(lèi)推。

兩個(gè)中心節(jié)點(diǎn)，其中標(biāo)簽f(i)和雙半徑(d(i,x),d(i,y))滿(mǎn)足：

（1）如果d(i,x)+d(i,y)≠d(j,x)+d(j,y)，則

（2）如果d(i,x)+d(i,y)=d(j,x)+d(j,y)，則

使用DRNL算法生成一個(gè)整數(shù)標(biāo)簽fl(i)函數(shù)，如公式（1）所示：

其中，dx=d(i,x)，dy=d(i,y)，d=dx-dy。對(duì)于d(i,x)=∞或d(i,y)=∞的節(jié)點(diǎn)，將其記做空標(biāo)簽0。

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

DeepWalk算法其實(shí)質(zhì)為矩陣分解，因此，DeepWalk算法的目標(biāo)函數(shù)為[4]：

其中，W∈?,H∈?,Ω則為矩陣M的觀測(cè)集，‖?‖F(xiàn)是矩陣M的F-范數(shù)，λ是平衡因子，它主要用來(lái)優(yōu)化分解后的W和H矩陣，其原理等同于L2范數(shù)。

曹蓉等[4]提出了基于網(wǎng)絡(luò)節(jié)點(diǎn)文本增強(qiáng)的鏈路預(yù)測(cè)算法TELP，在基于文本信息（text associated Deep-Walk，TADW）算法的基礎(chǔ)上對(duì)目標(biāo)矩陣M進(jìn)行分解，并根據(jù)余弦相似性算法，計(jì)算出任意兩個(gè)節(jié)點(diǎn)的相似度，從而構(gòu)建出最終的相似度矩陣。

在目標(biāo)矩陣M的分解過(guò)程中，使得下式達(dá)到最小：

2.3 融合節(jié)點(diǎn)標(biāo)簽與強(qiáng)弱關(guān)系的鏈路預(yù)測(cè)算法

定義1（余弦相似度）圖中任意兩個(gè)節(jié)點(diǎn)的相似度可用余弦相似度表示為sim(x,y)=cos(x,y)+a，其中，x和y分別為目標(biāo)節(jié)點(diǎn)和對(duì)比節(jié)點(diǎn)，a為調(diào)節(jié)參數(shù)，避免相似度過(guò)低導(dǎo)致的無(wú)效狀態(tài)。

然而根據(jù)關(guān)系相關(guān)理論[32-33]，本文在余弦相似度計(jì)算公式的基礎(chǔ)上根據(jù)關(guān)系強(qiáng)弱的特點(diǎn)，提出了一種融合節(jié)點(diǎn)標(biāo)簽與強(qiáng)弱關(guān)系的鏈路預(yù)測(cè)NRLP算法，其具體框架如圖1所示。

圖1 融合節(jié)點(diǎn)標(biāo)簽的屬性增強(qiáng)鏈路預(yù)測(cè)方法框架Fig.1 Attribute-enhanced link prediction method framework for fusion node labels

如圖1所示，該方法在已有的關(guān)系網(wǎng)絡(luò)中任意選擇兩個(gè)節(jié)點(diǎn)記為中心節(jié)點(diǎn)A、B，對(duì)關(guān)系網(wǎng)絡(luò)使用DRNL算法生成節(jié)點(diǎn)i相對(duì)于中心節(jié)點(diǎn)A、B構(gòu)建節(jié)點(diǎn)標(biāo)簽圖G。其次基于γ衰減理論局部子圖保存了豐富節(jié)點(diǎn)的信息，則以節(jié)點(diǎn)A、B 為中心構(gòu)建深度為h的局部子圖，提取局部子圖中節(jié)點(diǎn)的特征矩陣M，基于式（2）對(duì)生成的特征矩陣M進(jìn)行分解，并在矩陣分解過(guò)程中，引入屬性特征矩陣T，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行向量表示并使其融入節(jié)點(diǎn)屬性因子，使分解后的矩陣、Hn×ft分別包含矩陣M、T的分解因子。其中，| |V1為h深度的局部子圖中節(jié)點(diǎn)個(gè)數(shù)，n為向量長(zhǎng)度。最后使用矩陣WT作為節(jié)點(diǎn)的向量表示，結(jié)合NRLP 算法，得到任意兩個(gè)節(jié)點(diǎn)之間的相似度，對(duì)相似度高的中心節(jié)點(diǎn)進(jìn)行連接，實(shí)現(xiàn)鏈路預(yù)測(cè)。

對(duì)所有分解得到的矩陣WT按比例分為訓(xùn)練集和測(cè)試集，并使用AUC評(píng)價(jià)指標(biāo)，對(duì)本文算法性能進(jìn)行評(píng)估。本算法的通過(guò)DRNL 算法計(jì)算節(jié)點(diǎn)標(biāo)簽其時(shí)間復(fù)雜度為O(|V|2)及TELP 模型學(xué)習(xí)節(jié)點(diǎn)向量表示其訓(xùn)練復(fù)雜度為O(|V|2)，但本文在節(jié)點(diǎn)表示向量的訓(xùn)練中才用局部子圖進(jìn)行訓(xùn)練，其復(fù)雜度明顯小于原模型全圖所有節(jié)點(diǎn)進(jìn)行訓(xùn)練。所以本文提出的NRLP 算法時(shí)間復(fù)雜度為O(|V|2)。

NRLP 算法考慮節(jié)點(diǎn)之間存在強(qiáng)弱關(guān)系，賦予其不同的權(quán)重，表示節(jié)點(diǎn)i相對(duì)于兩個(gè)中心節(jié)點(diǎn)x、y的不同關(guān)系程度。在局部子圖中，當(dāng)節(jié)點(diǎn)i的dx=1,dy=1,f(i)=2 時(shí)，則節(jié)點(diǎn)i對(duì)于中心節(jié)點(diǎn)x、y為強(qiáng)關(guān)系，反之則為弱關(guān)系。若節(jié)點(diǎn)i的中心節(jié)點(diǎn)的半徑dx＜dy，則節(jié)點(diǎn)i相對(duì)于節(jié)點(diǎn)y與節(jié)點(diǎn)x有著更強(qiáng)的關(guān)系程度，反之亦然。而當(dāng)dx=dy，則節(jié)點(diǎn)i與節(jié)點(diǎn)x、y有著相同的關(guān)系程度。由于節(jié)點(diǎn)i，對(duì)于不同中心節(jié)點(diǎn)生成的局部子圖會(huì)擁有不同的強(qiáng)弱關(guān)系，所以對(duì)其賦予不同的動(dòng)態(tài)權(quán)值，其計(jì)算表達(dá)式如下所示：

公式（4）～（9）參數(shù)含義如表1。

表1 NRLP算法參數(shù)說(shuō)明Table 1 NRLP algorithm parameter description

對(duì)于節(jié)點(diǎn)標(biāo)簽為1的節(jié)點(diǎn)x、y，生成各自的相似度矩陣Sx=[Six]、Sy=[Siy]。構(gòu)建Sx、Sy的相似度矩陣差S=Sx-Sy，在局部子圖中，當(dāng)除中心節(jié)點(diǎn)x、y以外的節(jié)點(diǎn)標(biāo)簽全為0時(shí)，則兩個(gè)節(jié)點(diǎn)完全不相似，其|SST|=0也認(rèn)定兩節(jié)點(diǎn)不能連接。當(dāng)其余節(jié)點(diǎn)標(biāo)簽不全為0，且|SST|<ε時(shí)，對(duì)節(jié)點(diǎn)x、y進(jìn)行鏈路連接。其中ε為相似閾值，只有相似度小于閾值時(shí)，認(rèn)為兩個(gè)節(jié)點(diǎn)可能成為好友。

2.4 NRLP算法

NRLP算法描述如下：

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

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

根據(jù)第2章所述一種融合節(jié)點(diǎn)標(biāo)簽與強(qiáng)弱關(guān)系的鏈路預(yù)測(cè)算法，對(duì)數(shù)據(jù)進(jìn)行驗(yàn)證。實(shí)驗(yàn)環(huán)境為Windows 10系統(tǒng)、Intel Core i7 處理器、32 GB 內(nèi)存，采用PyCharm開(kāi)發(fā)環(huán)境，Python 3.6進(jìn)行算法實(shí)現(xiàn)。采用三個(gè)常見(jiàn)的數(shù)據(jù)集Citeseer、DBLP和Cora數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證本文提出的算法有效性。數(shù)據(jù)集包含了節(jié)點(diǎn)之間的連邊關(guān)系和每個(gè)節(jié)點(diǎn)的屬性類(lèi)類(lèi)別。數(shù)據(jù)集信息如表2所示。

表2 數(shù)據(jù)集信息Table 2 Data set information

通過(guò)表2 可以看出，當(dāng)節(jié)點(diǎn)個(gè)數(shù)大致相同時(shí)，邊的個(gè)數(shù)影響了圖的稠密度、平均度及平均聚類(lèi)系數(shù)的大小。本文提出的NRLP 算法建模帶有屬性節(jié)點(diǎn)之間的關(guān)系，且對(duì)社會(huì)關(guān)系設(shè)置動(dòng)態(tài)權(quán)重，得到的表示向量包含關(guān)系因子，結(jié)構(gòu)因子及屬性因子。

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

常見(jiàn)的鏈路預(yù)算精確度衡量指標(biāo)有AUC、準(zhǔn)確率、排序分等。本文采用AUC 評(píng)價(jià)指標(biāo)衡量算法的準(zhǔn)確性。鏈路預(yù)測(cè)算法在經(jīng)過(guò)訓(xùn)練后可以得到網(wǎng)絡(luò)中每一對(duì)節(jié)點(diǎn)的相似值。AUC評(píng)價(jià)指標(biāo)即是基于測(cè)試集中邊的相似值和不存在的邊的相似值的比較，如果測(cè)試集中邊的相似值大于不存在邊的相似值，則證明算法預(yù)測(cè)效果好。將數(shù)據(jù)集劃分為測(cè)試集和訓(xùn)練集，其中90%作為訓(xùn)練集，10%作為測(cè)試集。從測(cè)試集中每次隨機(jī)選一條存在的連邊，再隨機(jī)選一條不存在的連邊。若存在的連邊分值大于不存在的連邊分值，則加1；相等則加0.5。通過(guò)n次獨(dú)立比較，若有n′次大于的情況，n″次相等的情況，則AUC表示為：

AUC評(píng)價(jià)指標(biāo)取值范圍應(yīng)為[0.5，1）。當(dāng)訓(xùn)練集越大，對(duì)應(yīng)的AUC值越高，則算法的精確度越高。

3.3 對(duì)比分析

為進(jìn)一步驗(yàn)證本文提出的算法有效性，將本文算法與現(xiàn)有的多種預(yù)測(cè)方法進(jìn)行對(duì)比。在實(shí)驗(yàn)中，對(duì)三個(gè)數(shù)據(jù)集設(shè)置訓(xùn)練比例為0.7、0.8、0.9，子圖深度h為2，向量長(zhǎng)度為200，相似閾值為0.000 16，實(shí)驗(yàn)鏈路預(yù)測(cè)結(jié)果如表3所示。

從表3 可以得出，將本文所提出的NRLP 算法與常見(jiàn)的鏈路預(yù)測(cè)方法比較，通過(guò)對(duì)比結(jié)果得出本文提出的NRLP 算法在三個(gè)數(shù)據(jù)集上的性能優(yōu)于表3 中多種方法，并在Citeseer數(shù)據(jù)集性能最佳。由結(jié)果分析可知：本文所提出的NRLP算法優(yōu)于目前大多數(shù)鏈路預(yù)測(cè)方法，其原因在于考慮節(jié)點(diǎn)的連接與屬性信息；并考慮連接關(guān)系的強(qiáng)弱，區(qū)分其關(guān)系強(qiáng)度與程度生成新的相似度計(jì)算方法；并通過(guò)無(wú)監(jiān)督學(xué)習(xí)訓(xùn)練節(jié)點(diǎn)表示向量，快速提取節(jié)點(diǎn)信息及其結(jié)構(gòu)特征。

表3 數(shù)據(jù)集不同訓(xùn)練比例鏈路預(yù)測(cè)AUCTable 3 Link prediction AUC with different training ratios in data set %

3.4 調(diào)參與分析

在本文實(shí)驗(yàn)中，需要設(shè)置訓(xùn)練比例、向量長(zhǎng)度n和局部子圖深度h的值。通過(guò)調(diào)整局部子圖的深度，獲取兩中心節(jié)點(diǎn)的不同鄰居節(jié)點(diǎn)及其局部子圖范圍內(nèi)的各節(jié)點(diǎn)屬性，比較局部子圖與原圖之間的差異。

由圖2 可知，本文對(duì)三個(gè)數(shù)據(jù)集在深度h為1～5 的局部子圖性能進(jìn)行評(píng)估，當(dāng)h=2 時(shí)，均達(dá)到最佳性能。AUC 值在h>2 時(shí)減小，這表明子圖越深可能會(huì)從遠(yuǎn)處節(jié)點(diǎn)引入噪聲。當(dāng)h=1 時(shí)，因?yàn)槁窂捷^短時(shí)，節(jié)點(diǎn)及屬性信息較少導(dǎo)致差異較大。當(dāng)長(zhǎng)度變大時(shí)，引入路徑信息減少局部子圖與原圖之間的差異。

圖2 局部子圖與原圖對(duì)比圖Fig.2 Comparison of partial sub-image and original image

不同的訓(xùn)練比例與向量長(zhǎng)度對(duì)精確度擁有不同的影響，當(dāng)局部子圖深度為2，相似閾值為0.000 16，得到的訓(xùn)練率及向量長(zhǎng)度對(duì)預(yù)測(cè)結(jié)果如圖3所示。

通過(guò)分析圖3 可以得出，向量長(zhǎng)度為50、100、150、200、300，訓(xùn)練集比例為0.70、0.75、0.80、0.85、0.90、0.95，Citeseer數(shù)據(jù)集和Cora數(shù)據(jù)集為較稀疏圖。當(dāng)向量長(zhǎng)度分別為300、150，訓(xùn)練率分別為0.75、0.90 時(shí)，AUC 指標(biāo)最優(yōu)；DBLP 數(shù)據(jù)集為較稠密圖，向量長(zhǎng)度大于100，訓(xùn)練率在0.75～0.95之間，AUC幅度相差不大，基本在一定范圍波動(dòng)。對(duì)于稀疏圖，向量長(zhǎng)度與訓(xùn)練率對(duì)AUC 影響較大，對(duì)于稠密圖，影響相對(duì)較小。

圖3 訓(xùn)練率、向量長(zhǎng)度與預(yù)測(cè)結(jié)果的關(guān)系Fig.3 Relationship between training rate，vector length and prediction result

為了證明NRLP 算法的效率，同時(shí)對(duì)比TELP 算法在原圖和本文算法在局部子圖上進(jìn)行的時(shí)間見(jiàn)表4。

從表4 中可以看出，數(shù)據(jù)量較大時(shí)，在局部子圖上算法效率更高，局部子圖的噪音少于原圖且表示向量更加高效，所以表現(xiàn)明顯優(yōu)勢(shì)。

表4 算法運(yùn)行時(shí)間對(duì)比Table 4 Comparison of algorithm running time s

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

本文通過(guò)對(duì)節(jié)點(diǎn)生成標(biāo)簽構(gòu)造h深度子圖在鏈路預(yù)測(cè)時(shí)提高算法運(yùn)行時(shí)間與效率，并采用TELP模型為基礎(chǔ)，分析不同關(guān)系強(qiáng)度對(duì)鏈路連接的重要性，并將余弦相似度算法與動(dòng)態(tài)權(quán)重相融合，提出一種融合節(jié)點(diǎn)標(biāo)簽與強(qiáng)弱關(guān)系的鏈路預(yù)測(cè)NRLP 算法。該算法同時(shí)考慮網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)屬性及連接關(guān)系強(qiáng)弱對(duì)鏈接的影響，通過(guò)隨機(jī)選擇兩個(gè)中心節(jié)點(diǎn)判斷其成功鏈接的可能性。實(shí)驗(yàn)結(jié)果通過(guò)在三種文獻(xiàn)的集成數(shù)據(jù)庫(kù)Citeseer、DBLP 和Cora 數(shù)據(jù)集驗(yàn)證NRLP 算法的準(zhǔn)確性和高效性。下一步工作將考慮對(duì)新聞資訊相關(guān)性或社交網(wǎng)絡(luò)人際關(guān)系預(yù)測(cè)實(shí)現(xiàn)鏈路預(yù)測(cè)，并嘗試將模型拓展融合更豐富的屬性進(jìn)行教育資訊的社會(huì)化推薦。