基于節(jié)點(diǎn)相似性的二階鏈路預(yù)測(cè)方法

劉 臣，王嘉賓

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

現(xiàn)實(shí)世界中的很多復(fù)雜系統(tǒng)，如社交關(guān)系、交通運(yùn)輸、生物系統(tǒng)、信息系統(tǒng)等，都可以建模為網(wǎng)絡(luò)。其中，將某個(gè)實(shí)體對(duì)象表示為節(jié)點(diǎn)，它們之間的交互關(guān)系表示為連邊（或鏈接）。然而，由于收集數(shù)據(jù)時(shí)人為統(tǒng)計(jì)的失誤或者數(shù)據(jù)本身有隱私設(shè)置等原因，構(gòu)建的網(wǎng)絡(luò)并不一定反映真實(shí)的數(shù)據(jù)，使得收集網(wǎng)絡(luò)數(shù)據(jù)的完整結(jié)構(gòu)變得尤為困難［1-2］。因此，根據(jù)觀察到的網(wǎng)絡(luò)信息預(yù)測(cè)缺失的節(jié)點(diǎn)或者鏈路是一項(xiàng)極為重要的工作，其對(duì)于補(bǔ)全相對(duì)完整的網(wǎng)絡(luò)具有重要意義［3］。

鏈路預(yù)測(cè)的目的是根據(jù)觀察到的鏈路和節(jié)點(diǎn)屬性估計(jì)兩個(gè)節(jié)點(diǎn)之間存在鏈路的可能性，如果兩個(gè)節(jié)點(diǎn)彼此相似，則它們之間也更有可能存在鏈路。鏈路預(yù)測(cè)方法主要有三大類：基于相似性的方法、基于概率和最大似然的方法以及基于降維的方法?；谙嗨菩缘姆椒ㄊ腔卩徲蚪Y(jié)構(gòu)計(jì)算節(jié)點(diǎn)之間的相似度，分別從局部和全局的角度計(jì)算。局部相似度指標(biāo)通常使用節(jié)點(diǎn)的近鄰和節(jié)點(diǎn)度的信息進(jìn)行計(jì)算，包括共同鄰居指標(biāo)（CN）［4］、優(yōu)先鏈接指標(biāo)（PA）［5］等，計(jì)算復(fù)雜度低，在聚類系數(shù)低的稀疏網(wǎng)絡(luò)中很難得到高的準(zhǔn)確率。全局相似度指標(biāo)如Katz 指標(biāo)［6］和SimRank 指標(biāo)［7］是利用網(wǎng)絡(luò)的整個(gè)拓?fù)湫畔⑦M(jìn)行計(jì)算，計(jì)算復(fù)雜度較高且不適用于大型網(wǎng)絡(luò)。基于概率［8-9］和最大似然［10-11］的方法依賴網(wǎng)絡(luò)的層次結(jié)構(gòu)判斷節(jié)點(diǎn)連邊的可能性，操作復(fù)雜且耗時(shí)，不適用于真實(shí)的大型網(wǎng)絡(luò)。面對(duì)高維度的難題，研究者將網(wǎng)絡(luò)嵌入和矩陣分解技術(shù)作為降維技術(shù)，也將其用于鏈路預(yù)測(cè)。DeepWalk 和Node2vec 網(wǎng)絡(luò)嵌入方法通過保留節(jié)點(diǎn)的鄰域結(jié)構(gòu)，將圖中的高維節(jié)點(diǎn)映射到較低維度的表示空間［12-13］。Berahmand 等［14］將網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性相結(jié)合，引入新的鏈接預(yù)測(cè)隨機(jī)游走模型用于解決屬性網(wǎng)絡(luò)中的鏈路預(yù)測(cè)。Menon 等［15］將結(jié)構(gòu)鏈接預(yù)測(cè)問題建模為矩陣補(bǔ)全問題，并使用矩陣分解進(jìn)一步求解。

鏈路預(yù)測(cè)在不同的網(wǎng)絡(luò)類型中都有相應(yīng)研究，在不同的領(lǐng)域也都有成熟的應(yīng)用，例如在社交網(wǎng)絡(luò)中從大量的注冊(cè)用戶中為單個(gè)用戶自動(dòng)推薦熟人；在科學(xué)合作網(wǎng)絡(luò)中預(yù)測(cè)哪些作者或團(tuán)體在未來可能合作，以更好地了解一些研究領(lǐng)域的發(fā)展情況。這些研究針對(duì)兩個(gè)節(jié)點(diǎn)之間是否存在鏈路展開，本文探討網(wǎng)絡(luò)中的二階鏈路該如何預(yù)測(cè)，在計(jì)算節(jié)點(diǎn)對(duì)之間的相似性時(shí)，識(shí)別一個(gè)中間節(jié)點(diǎn)，同時(shí)預(yù)測(cè)涉及中間節(jié)點(diǎn)的兩條鏈接。本文學(xué)習(xí)基于相似性的鏈路預(yù)測(cè)算法，提出了一種基于節(jié)點(diǎn)相似性的二階鏈路預(yù)測(cè)方法，用于為用戶或者合作者雙方找到可以實(shí)現(xiàn)通信的第三方，還可以在社交網(wǎng)絡(luò)中為兩個(gè)本不相識(shí)的用戶識(shí)別出可能各自與他們相熟的目標(biāo)用戶，為雙方用戶搭建溝通的橋梁。一個(gè)更有意義的工作是監(jiān)控恐怖主義網(wǎng)絡(luò)中的隱藏關(guān)系［16］，推測(cè)不同的恐怖分子或團(tuán)體是經(jīng)由哪一個(gè)團(tuán)體或個(gè)人聯(lián)絡(luò)，即使他們之間的交互沒有被直接觀察到，以據(jù)此做好安全防范工作。

在鏈路預(yù)測(cè)中，一個(gè)相當(dāng)大的挑戰(zhàn)是數(shù)據(jù)稀疏性。如果網(wǎng)絡(luò)中的數(shù)據(jù)過于稀疏，則無法從簡(jiǎn)單的公共鄰居數(shù)量或其他相關(guān)變體指標(biāo)中提取出有價(jià)值的相似性信息［17］，此時(shí)只考慮局部信息可能會(huì)導(dǎo)致較差的預(yù)測(cè)。顧秋陽(yáng)等［18］使用高階路徑作為判別特征對(duì)復(fù)雜網(wǎng)絡(luò)中的缺失鏈接進(jìn)行有效預(yù)測(cè)；LYU 等［19］使用較長(zhǎng)的路徑（長(zhǎng)度大于2 的路徑）度量節(jié)點(diǎn)相似性。但由于涉及高階信息，計(jì)算過程中會(huì)產(chǎn)生很多噪聲，不利于相似度計(jì)算。Liao 等［20］發(fā)現(xiàn)基于相關(guān)性的方法在計(jì)算基于高階路徑的相似度時(shí)非常有效，不會(huì)受噪聲影響，進(jìn)一步與資源分配方法相結(jié)合，對(duì)稀疏網(wǎng)絡(luò)和密集網(wǎng)絡(luò)都適用。目標(biāo)網(wǎng)絡(luò)的稀疏性會(huì)導(dǎo)致一個(gè)問題，即一條鏈路的先驗(yàn)概率通常都很小，很難建立統(tǒng)計(jì)模型。與傳統(tǒng)的鏈路預(yù)測(cè)任務(wù)不同，本文提出在網(wǎng)絡(luò)中實(shí)現(xiàn)二階鏈路預(yù)測(cè)，為一對(duì)已知節(jié)點(diǎn)識(shí)別中間節(jié)點(diǎn)并補(bǔ)全二階鏈路。本文構(gòu)造新的計(jì)算指標(biāo)用于識(shí)別節(jié)點(diǎn)，并構(gòu)建了一個(gè)二階可達(dá)網(wǎng)絡(luò)以篩選可能的節(jié)點(diǎn)，一方面減小了計(jì)算復(fù)雜度，另一方面也緩解了數(shù)據(jù)稀疏性。利用鄰接矩陣構(gòu)造二階可達(dá)矩陣，記錄網(wǎng)絡(luò)中的二階鏈路信息。相比于原始網(wǎng)絡(luò)中傳達(dá)的一階信息，二階可達(dá)矩陣所對(duì)應(yīng)的二階可達(dá)網(wǎng)絡(luò)保留了原始網(wǎng)絡(luò)中所有的二階鏈路，有助于實(shí)現(xiàn)本文的二階鏈路預(yù)測(cè)。

1 問題描述

令G=(V，E)表示無權(quán)無向網(wǎng)絡(luò)，V是網(wǎng)絡(luò)G中節(jié)點(diǎn)的集合，節(jié)點(diǎn)數(shù)為|V|，E是網(wǎng)絡(luò)G中邊（或鏈接）的集合，邊數(shù)為|E|。將不相連的節(jié)點(diǎn)對(duì)vi與vj記為(vi，vj)，節(jié)點(diǎn)對(duì)之間的相似性定義為sim(vi，vj)，該值越大，節(jié)點(diǎn)對(duì)之間越有可能存在鏈接。因此，可以將sim(vi，vj)看作節(jié)點(diǎn)對(duì)之間是否存在鏈接的評(píng)分。網(wǎng)絡(luò)G的鏈接用鄰接矩陣A表示，當(dāng)節(jié)點(diǎn)vu與vw之間存在鏈接時(shí)，鄰接矩陣中的元素auw值為1，否則為0。如果節(jié)點(diǎn)vu和vw之間存在鏈接，則這兩個(gè)節(jié)點(diǎn)互為鄰居節(jié)點(diǎn)，稱vu和vw之間是一階可達(dá)的。如果節(jié)點(diǎn)vu和vw不直接相連，存在節(jié)點(diǎn)vk使之形成二階鏈路vu-vk-vw，則稱vu和vw之間是二階可達(dá)的，互為二階鄰節(jié)點(diǎn)。

二階鏈路預(yù)測(cè)任務(wù)通過在一對(duì)已知節(jié)點(diǎn)的二階鄰域交集中確認(rèn)最有可能分別與節(jié)點(diǎn)對(duì)存在鏈路的同一個(gè)節(jié)點(diǎn)身份，實(shí)現(xiàn)已知節(jié)點(diǎn)對(duì)之間的二階鏈路預(yù)測(cè)。如圖1 所示，在可觀測(cè)節(jié)點(diǎn)集{v1，v2，v3，v4，v5，v6，v7，v8}中，v1的二階鄰域節(jié)點(diǎn)集為{v3，v5，v8}，v6的二階鄰域節(jié)點(diǎn)集為{v3，v8}。從節(jié)點(diǎn)對(duì)(v1，v6)的二階鄰域交集{v3，v8}中比較它們各自與節(jié)點(diǎn)v1、v6的相似性，如sim(v1，v3)，sim(v3，v6)，若與v1、v6均有較大相似性的節(jié)點(diǎn)為v3，則可以確認(rèn)v1、v6之間的一條二階鏈路為v1-v3-v6。

Fig.1 Second-order link prediction task圖1 二階鏈路預(yù)測(cè)任務(wù)

2 網(wǎng)絡(luò)中的二階鏈路預(yù)測(cè)

本文利用節(jié)點(diǎn)相似性進(jìn)行二階鏈路預(yù)測(cè)，首先將目標(biāo)節(jié)點(diǎn)的搜索范圍縮小至節(jié)點(diǎn)對(duì)的二階鄰域，然后基于相似性指標(biāo)sim(vi，vj)進(jìn)行加工，求得與節(jié)點(diǎn)對(duì)均有很高相似度的節(jié)點(diǎn)，以確認(rèn)目標(biāo)節(jié)點(diǎn)的身份，從而實(shí)現(xiàn)二階鏈路預(yù)測(cè)任務(wù)。圖2描述了網(wǎng)絡(luò)中的二階鏈路預(yù)測(cè)過程。

2.1 二階可達(dá)網(wǎng)絡(luò)

當(dāng)網(wǎng)絡(luò)中的部分鏈接不被觀察到或網(wǎng)絡(luò)中的部分鏈接被去除，剩下的網(wǎng)絡(luò)結(jié)構(gòu)偏向于稀疏圖，這不利于提取節(jié)點(diǎn)的鄰居信息，因此首先處理數(shù)據(jù)稀疏問題。網(wǎng)絡(luò)中的鏈接用鄰接矩陣A表示，對(duì)鄰接矩陣A進(jìn)行變換操作，得到矩陣A2，其中每個(gè)元素就是節(jié)點(diǎn)vi和vj之間長(zhǎng)度為2 的路徑的數(shù)目。將其對(duì)角線元素置0，非零元素的數(shù)值替換為1，得到一個(gè)0-1 矩陣，稱之為二階可達(dá)矩陣。也即當(dāng)節(jié)點(diǎn)對(duì)vi與vj之間存在二階鏈路時(shí)，二階可達(dá)矩陣中的元素值為1，否則為0。根據(jù)二階可達(dá)矩陣所描述的節(jié)點(diǎn)間的鏈接信息構(gòu)建新的無向網(wǎng)絡(luò)，稱之為二階可達(dá)網(wǎng)絡(luò)G'。

本研究主要介紹了組合可調(diào)式Halo -骨盆固定支具的設(shè)計(jì)及初步臨床應(yīng)用結(jié)果，仍存在一些不足：①樣本量少，尤其是針對(duì)結(jié)核性脊柱后凸畸形方面需要進(jìn)一步積累臨床病例；②缺乏與其他類型脊柱牽引技術(shù)的對(duì)照研究；③Halo -骨盆固定支具剛性牽引作用力大，容易導(dǎo)致盆針切割及變形，盆針的穿針方式、牽引策略及器材設(shè)計(jì)有待進(jìn)一步改善。

當(dāng)一對(duì)節(jié)點(diǎn)是二階可達(dá)，但它們之間的鏈路不被檢測(cè)到時(shí)，中間節(jié)點(diǎn)的身份是未知的。受基于相似性的鏈路預(yù)測(cè)算法啟發(fā)，兩個(gè)存在鏈接的節(jié)點(diǎn)相似性必定極高，且它們之間存在公共鄰居節(jié)點(diǎn)，則目標(biāo)節(jié)點(diǎn)與已知節(jié)點(diǎn)在網(wǎng)絡(luò)中可能是二階可達(dá)的。因此，可以從已知節(jié)點(diǎn)對(duì)的二階可達(dá)節(jié)點(diǎn)集的交集內(nèi)找到目標(biāo)節(jié)點(diǎn)，而候選目標(biāo)節(jié)點(diǎn)的集合在二階可達(dá)網(wǎng)絡(luò)中可見。

2.2 二階鏈路預(yù)測(cè)指標(biāo)

當(dāng)去除網(wǎng)絡(luò)中的一部分鏈接時(shí)，網(wǎng)絡(luò)變得稀疏，由于基于節(jié)點(diǎn)局部信息的相似性指標(biāo)不能計(jì)算沒有共同鄰居的節(jié)點(diǎn)之間的相似性［17］，因此鏈接預(yù)測(cè)指標(biāo)在稀疏網(wǎng)絡(luò)中很難得到高的準(zhǔn)確率。為了解決這一不足，本文考慮將目標(biāo)節(jié)點(diǎn)的搜索范圍放在二階可達(dá)網(wǎng)絡(luò)內(nèi)，不僅降低了計(jì)算復(fù)雜度，而且預(yù)測(cè)準(zhǔn)確率也在一定程度上得以提高。在網(wǎng)絡(luò)中分別與節(jié)點(diǎn)vi、vj存在鏈路的節(jié)點(diǎn)很有可能不止一個(gè)，是否為同一個(gè)目標(biāo)節(jié)點(diǎn)還需作進(jìn)一步判斷。本文擬在可能與節(jié)點(diǎn)vi或節(jié)點(diǎn)vj存在鏈路的多個(gè)節(jié)點(diǎn)中，找到可能同時(shí)與節(jié)點(diǎn)vi、vj存在鏈路的目標(biāo)節(jié)點(diǎn)。

基于節(jié)點(diǎn)相似性，本文提出二階鏈路預(yù)測(cè)指標(biāo)，用于在已知節(jié)點(diǎn)對(duì)的二階鄰域內(nèi)尋找公共一階鄰節(jié)點(diǎn)。指標(biāo)如下：

其中，sim(x，y)是度量節(jié)點(diǎn)相似度的一個(gè)指標(biāo)，評(píng)分值越大，節(jié)點(diǎn)對(duì)之間存在鏈路的可能性越大，它可以是任意一個(gè)普通的鏈接預(yù)測(cè)指標(biāo)。Γ2(vi)指節(jié)點(diǎn)vi的二階可達(dá)節(jié)點(diǎn)集，v是vi、vj的二階可達(dá)節(jié)點(diǎn)集交集中的節(jié)點(diǎn)。

2.3 基礎(chǔ)鏈路預(yù)測(cè)指標(biāo)

基于節(jié)點(diǎn)局部信息的相似性指標(biāo)如CN 指標(biāo)、AA 指標(biāo)、RA 指標(biāo)、PA 指標(biāo)可以計(jì)算節(jié)點(diǎn)間的相似度，因此借助這類指標(biāo)完成二階鏈路預(yù)測(cè)任務(wù)。

CN（Common Neighbors）指標(biāo)即共同鄰居指標(biāo)，基于共同鄰域大小度量節(jié)點(diǎn)間的相似性，如果兩個(gè)未知鏈接的節(jié)點(diǎn)i和j共同的鄰居越多，則它們之間產(chǎn)生鏈接的可能性就越大［4］。相似度計(jì)算如下：

其中，Γ(i)為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的集合；Γ(j)為節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)的集合。

其中，kz為節(jié)點(diǎn)z的度數(shù)。

JC（Jaccard Coefficient）指標(biāo)是基于CN 指標(biāo)，考慮節(jié)點(diǎn)度的影響所產(chǎn)生的同樣基于共同鄰居思想的相似性指標(biāo)。

AA（Adamic-Adar）指標(biāo)在CN 指標(biāo)的基礎(chǔ)上考慮了共同鄰居間的權(quán)重差異，認(rèn)為共同鄰居的節(jié)點(diǎn)度越小，對(duì)相似度的貢獻(xiàn)越大，為度較小的鄰居節(jié)點(diǎn)分配更高的權(quán)重［22］。

PA（Preferential Attachment）指標(biāo)認(rèn)為節(jié)點(diǎn)i和j產(chǎn)生新鏈接的可能性與節(jié)點(diǎn)度的乘積成正比［5］。

2.4 樣本構(gòu)造

針對(duì)網(wǎng)絡(luò)中滿足最小度為4 的目標(biāo)節(jié)點(diǎn)，按一定比例剔除一部分與之相連的鏈接，將被剔除鏈接的目標(biāo)節(jié)點(diǎn)之外的節(jié)點(diǎn)兩兩組合構(gòu)造正節(jié)點(diǎn)對(duì)。在網(wǎng)絡(luò)的二階可達(dá)矩陣中，節(jié)點(diǎn)度大于2 且元素值為0 所對(duì)應(yīng)的節(jié)點(diǎn)對(duì)為負(fù)節(jié)點(diǎn)對(duì)。

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

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

本文使用4 個(gè)真實(shí)網(wǎng)絡(luò)的數(shù)據(jù)對(duì)二階鏈路預(yù)測(cè)算法性能進(jìn)行評(píng)估。Cora 是一個(gè)引文網(wǎng)絡(luò)，其中節(jié)點(diǎn)代表機(jī)器學(xué)習(xí)方面的論文，只有當(dāng)其中一篇論文被另一篇論文引用時(shí)，兩篇論文之間才會(huì)形成一條邊緣，該網(wǎng)絡(luò)由2 708 個(gè)節(jié)點(diǎn)和5 429 條邊組成。Citeseer 同樣是引文網(wǎng)絡(luò)，由3 312個(gè)節(jié)點(diǎn)和4 715 條邊組成。Washington 和Texas 包含兩所大學(xué)網(wǎng)站中的網(wǎng)頁(yè)引用，節(jié)點(diǎn)和邊分別代表網(wǎng)頁(yè)和網(wǎng)頁(yè)之間的引用。Washington 由230 個(gè)節(jié)點(diǎn)和446 條邊組成，Texas 由187 個(gè)節(jié)點(diǎn)和328 條邊組成。4 個(gè)網(wǎng)絡(luò)的統(tǒng)計(jì)信息如表1所示。

Table 1 Statistical information of four networks表1 4個(gè)網(wǎng)絡(luò)的統(tǒng)計(jì)信息

3.2 實(shí)驗(yàn)相關(guān)設(shè)置

3.2.1 參數(shù)設(shè)置

每次獨(dú)立實(shí)驗(yàn)中，去除目標(biāo)節(jié)點(diǎn)的鏈接比例為0.2，將數(shù)據(jù)集按照0.7、0.1、0.2 的比例劃分為訓(xùn)練集、驗(yàn)證集和測(cè)試集。

3.2.2 評(píng)估指標(biāo)

由于隨機(jī)因素的存在，根據(jù)二階鏈路預(yù)測(cè)指標(biāo)計(jì)算得到的最大指標(biāo)值所對(duì)應(yīng)的節(jié)點(diǎn)并不一定是真正缺失的目標(biāo)節(jié)點(diǎn)。Liben-Nowell 等［23］通過幾個(gè)相似性度量提取兩個(gè)節(jié)點(diǎn)之間的相似性。根據(jù)這些相似性為每對(duì)節(jié)點(diǎn)分配排名，然后將排名較高的節(jié)點(diǎn)對(duì)指定為預(yù)測(cè)鏈接。因此，本文將得到的計(jì)算指標(biāo)由大到小排序，對(duì)應(yīng)得到一系列可能的缺失節(jié)點(diǎn){v1，v2，v3，…}。為了驗(yàn)證該指標(biāo)的有效性，給定一個(gè)閾值，設(shè)置為k，在這一系列節(jié)點(diǎn)的前k個(gè)節(jié)點(diǎn)中檢驗(yàn)是否真正找回目標(biāo)節(jié)點(diǎn)并關(guān)注找到節(jié)點(diǎn)的精確率，進(jìn)而評(píng)判該指標(biāo)的預(yù)測(cè)性能。

本文采用的評(píng)估指標(biāo)是AUC 和Precision，AUC 用于評(píng)估是否識(shí)別到缺失的鏈路，Precision 用于評(píng)估在閾值內(nèi)識(shí)別到真實(shí)目標(biāo)節(jié)點(diǎn)的精確度。AUC 在鏈接預(yù)測(cè)中的定義為從測(cè)試集和負(fù)樣本中各隨機(jī)取一條鏈接，比較這兩條鏈接的分?jǐn)?shù)。假設(shè)在n次獨(dú)立比較中，測(cè)試集中的鏈接比負(fù)樣本中的鏈接擁有更高分?jǐn)?shù)的次數(shù)為n1，兩者擁有相同分?jǐn)?shù)的次數(shù)為n2，則AUC 的計(jì)算公式為：

精確率（Precision）指在識(shí)別為真鏈接的樣本中真正是真鏈接的樣本所占比例，精確率越高，說明模型效果越好。

3.3 結(jié)果分析

本文基于普通鏈路預(yù)測(cè)算法的相似性指標(biāo)，利用RA、JC、AA、PA 這4 項(xiàng)指標(biāo)作為基準(zhǔn)鏈路預(yù)測(cè)指標(biāo)幫助實(shí)現(xiàn)本文提出的二階鏈路預(yù)測(cè)方法，并在4 個(gè)真實(shí)網(wǎng)絡(luò)中檢驗(yàn)其效果。表2 和表3 分別列出了相應(yīng)的AUC 值和Precision值，其中每個(gè)網(wǎng)絡(luò)的最優(yōu)值用加粗表示。由表2 可知，各項(xiàng)基準(zhǔn)指標(biāo)在Citeseer 網(wǎng)絡(luò)上均表現(xiàn)良好；JC 指標(biāo)和PA 指標(biāo)可以分別在其中兩個(gè)網(wǎng)絡(luò)上實(shí)現(xiàn)較好的性能。在Washington 和Texas 網(wǎng)絡(luò)中，JC 指標(biāo)相比其他指標(biāo)得到的AUC值提升了0.29%～17.15%；在Cora 和Citeseer 網(wǎng)絡(luò)中，PA 指標(biāo)相比其他指標(biāo)得到的AUC 值提升了1.92%～2.05%。但相比而言本文提出的方法在Texas 網(wǎng)絡(luò)上表現(xiàn)并不好，在Washington 網(wǎng)絡(luò)上的表現(xiàn)也不顯著，這與網(wǎng)絡(luò)本身的結(jié)構(gòu)有關(guān)。當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，按一定比例剔除部分鏈接會(huì)使網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生很大改變，容易造成采樣不充分，因此在這樣的網(wǎng)絡(luò)上進(jìn)行二階鏈路預(yù)測(cè)任務(wù)效果并不好。

Table 2 AUC values of four networks表2 4個(gè)網(wǎng)絡(luò)中的AUC值

Table 3 Precision values of four networks表3 4個(gè)網(wǎng)絡(luò)中的Precision值

由表3 可知，將每對(duì)節(jié)點(diǎn)所得的計(jì)算指標(biāo)做排序之后，各項(xiàng)基準(zhǔn)指標(biāo)均可以在候選目標(biāo)節(jié)點(diǎn)集的前兩位中找到最優(yōu)節(jié)點(diǎn)，說明它們的預(yù)測(cè)性能較好。其中，4 項(xiàng)基準(zhǔn)指標(biāo)在Cora 網(wǎng)絡(luò)中均呈現(xiàn)出較高的精確率，因此可以推測(cè)本文的二階鏈路預(yù)測(cè)方法在Cora 這樣的大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)中有不錯(cuò)的表現(xiàn)。而Citeseer 網(wǎng)絡(luò)中的精確率較低，與表2中的AUC 結(jié)果不相符合，原因可能在于AUC 是從全局考察預(yù)測(cè)方法的性能，而Precision 是從幾條鏈接中檢驗(yàn)預(yù)測(cè)精度，二者評(píng)價(jià)任務(wù)不一樣。綜合而言，該方法在Citeseer 網(wǎng)絡(luò)中的表現(xiàn)依然不錯(cuò)。

為了進(jìn)一步說明構(gòu)建二階可達(dá)網(wǎng)絡(luò)以緩解數(shù)據(jù)稀疏性對(duì)本文所提方法的必要性，本文從所用數(shù)據(jù)集的網(wǎng)絡(luò)密度角度對(duì)各網(wǎng)絡(luò)上的表現(xiàn)進(jìn)行比較分析。首先，一個(gè)包含N 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)的密度ρ 是指網(wǎng)絡(luò)中實(shí)際存在的邊數(shù)M與最大可能的邊數(shù)之比。對(duì)于無向網(wǎng)絡(luò)，網(wǎng)絡(luò)的密度ρ有：

本文數(shù)據(jù)集所對(duì)應(yīng)的網(wǎng)絡(luò)密度如表1 所示，可見稀疏度的關(guān)系表現(xiàn)為：Citeseer ＞ Cora ＞ Washington ＞ Texas，因此本文選擇在稀疏度上有所區(qū)分的前3 個(gè)網(wǎng)絡(luò)上根據(jù)AUC 指標(biāo)值評(píng)估該方法的性能，實(shí)驗(yàn)結(jié)果如圖3所示。

Fig.3 Changes of AUC value under different indicators圖3 不同指標(biāo)下的AUC值變化

在各項(xiàng)基準(zhǔn)指標(biāo)下，稀疏度最大的網(wǎng)絡(luò)Citeseer 保持最優(yōu)的AUC 值，稀疏度中等的Cora 次之，稀疏度最小的Washington 網(wǎng)絡(luò)AUC 值最低。由此可見，網(wǎng)絡(luò)稀疏度越大，該方法的性能越好，因此本文所提出的方法相對(duì)適用于稀疏度較大的網(wǎng)絡(luò)。

為了探索訓(xùn)練集比例對(duì)預(yù)測(cè)效果的影響以及各項(xiàng)指標(biāo)的相對(duì)表現(xiàn)，本文在Cora 和Citeseer 網(wǎng)絡(luò)上作了進(jìn)一步探究。圖4 給出了訓(xùn)練集比例從0.4 增長(zhǎng)到0.7 時(shí)，Cora 和Citeseer 網(wǎng)絡(luò)中基于不同基準(zhǔn)鏈路預(yù)測(cè)指標(biāo)的AUC 值變化。在Cora 網(wǎng)絡(luò)中，AUC 值初始呈上升趨勢(shì)，是因?yàn)橛?xùn)練集比例增加能夠提供更多的訓(xùn)練信息，從而提高了AUC值。隨著訓(xùn)練集的增加，測(cè)試集會(huì)相應(yīng)減少，當(dāng)訓(xùn)練集的比例增加到一定程度，在測(cè)試集中獲取鏈接的概率會(huì)降低，因而不易找到缺失的二階鏈路，故AUC 值會(huì)下降。在Citeseer 網(wǎng)絡(luò)中，AUC 值初始呈下降趨勢(shì)，是因?yàn)榇藭r(shí)并沒有在訓(xùn)練集中學(xué)到有用信息，而中間上升的值說明開始在訓(xùn)練集中學(xué)到有效的訓(xùn)練信息，并表現(xiàn)出來；之后，AUC 值表現(xiàn)出下降趨勢(shì)同樣是因?yàn)橛?xùn)練集增加到一定程度，在測(cè)試集中獲取鏈接的可能性會(huì)減小。此外，網(wǎng)絡(luò)本身的結(jié)構(gòu)特征（度數(shù)）在各項(xiàng)基準(zhǔn)指標(biāo)中占據(jù)著不一致的重要性，因此AUC 值在不同基準(zhǔn)指標(biāo)上的表現(xiàn)會(huì)有所差異。

Fig.4 Changes of AUC value when ratio of training set increases from 40% to 70% in Cora and Citeseer network圖4 Cora和Citeseer網(wǎng)絡(luò)中訓(xùn)練集比例由40%增加到70%時(shí)AUC的變化

4 結(jié)語(yǔ)

本文提出了基于節(jié)點(diǎn)相似性的二階鏈路預(yù)測(cè)方法，并構(gòu)造了二階鏈路預(yù)測(cè)指標(biāo)以識(shí)別節(jié)點(diǎn)對(duì)的中間節(jié)點(diǎn)，然后補(bǔ)全節(jié)點(diǎn)對(duì)之間的二階鏈路。該方法可以結(jié)合RA、JC、AA、PA 4 項(xiàng)相似性指標(biāo)加以實(shí)現(xiàn)，為了驗(yàn)證各指標(biāo)性能及方法的有效性，分別在4 個(gè)真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn)。結(jié)果表明，此方法在稀疏度較大的網(wǎng)絡(luò)上會(huì)表現(xiàn)出相對(duì)更好的性能，在AUC 和Precision 指標(biāo)上表現(xiàn)良好，能夠精確地預(yù)測(cè)到所丟失的鏈路。下一步研究的重點(diǎn)是在基準(zhǔn)預(yù)測(cè)指標(biāo)上找到更加合適的搭配，比如基于節(jié)點(diǎn)的嵌入向量等，同時(shí)期待能夠在更普遍的網(wǎng)絡(luò)上發(fā)揮該方法的作用。