陳廣福，江 玲，韓輝珍

(1.武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 武夷山 353400;2.認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 武夷山 353400)

0 引 言

真實(shí)世界大量的復(fù)雜系統(tǒng)可由復(fù)雜網(wǎng)絡(luò)來(lái)描述和表示,其中節(jié)點(diǎn)代表實(shí)體和鏈接表示實(shí)體間的關(guān)系。由于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)收集總是不完整及受噪聲影響，如何尋找缺失鏈接間的關(guān)系是復(fù)雜網(wǎng)絡(luò)研究中最有挑戰(zhàn)的問(wèn)題。鏈路預(yù)測(cè)的目標(biāo)是根據(jù)已知網(wǎng)絡(luò)結(jié)構(gòu)及其節(jié)點(diǎn)屬性等信息去推斷節(jié)點(diǎn)對(duì)形成鏈接的可能性[1]。此外，鏈路預(yù)測(cè)還具有以下功能：(1)預(yù)測(cè)缺失的無(wú)向、加權(quán)和有向鏈接，識(shí)別虛假鏈接及消除網(wǎng)絡(luò)噪聲；(2)根據(jù)當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)信息探尋網(wǎng)絡(luò)演化機(jī)制。因此，鏈路預(yù)測(cè)廣泛應(yīng)用于不同的領(lǐng)域。例如在電子郵件系統(tǒng)，鏈路預(yù)測(cè)可阻止和過(guò)濾不相關(guān)的和廣告的郵件[2]；在社交網(wǎng)絡(luò)，鏈路預(yù)測(cè)啟用信任度量保護(hù)用戶的隱私信息[3]；此外，在生物網(wǎng)絡(luò)中，可用于預(yù)測(cè)蛋白質(zhì)間先前未知的相互作用，從而顯著降低經(jīng)驗(yàn)方法的成本等[4]。

當(dāng)前，不同類型鏈路預(yù)測(cè)算法被提出應(yīng)用在不同場(chǎng)景。基于相似度算法是最簡(jiǎn)單和有效的方法，該方法是根據(jù)已知網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性計(jì)算節(jié)點(diǎn)對(duì)的相似度分?jǐn)?shù)，然后按升序?qū)?jié)點(diǎn)分?jǐn)?shù)進(jìn)行排序，分?jǐn)?shù)越排在前面節(jié)點(diǎn)對(duì)越有可能形成鏈接。一般而言，基于相似度方法可分為基于局部相似度、全局方法和半局部方法?；诰植肯嗨贫人惴ɡ镁植拷Y(jié)構(gòu)(如共同鄰居數(shù)量、節(jié)點(diǎn)聚類及度相關(guān)聚類等)信息去計(jì)算未鏈接節(jié)點(diǎn)對(duì)分?jǐn)?shù)，其中共同鄰居(Common Neighbors，CN)[5]、資源分配(Resource Allocation，RA)[6]和Adamic-Adar(AA)[7]是典型代表。AA與RA指標(biāo)核心思想類似，都是啟用懲罰度較大節(jié)點(diǎn)，兩者區(qū)別是AA指標(biāo)是懲罰度權(quán)重大的節(jié)點(diǎn)而RA指標(biāo)是懲罰獲得資源多的節(jié)點(diǎn)。此外，文獻(xiàn)[8]協(xié)同過(guò)濾和自包含協(xié)同過(guò)濾框架融合局部相似度算法CN、AA和RA極大改善了預(yù)測(cè)精度。文獻(xiàn)[9]提出一種基于共同鄰居鄰域拓?fù)涑砻苄约訖?quán)的鏈路預(yù)測(cè)方法,該方法利用共同鄰居的節(jié)點(diǎn)度和鄰域拓?fù)湎鄬?duì)稠密指數(shù)刻畫共同鄰居及其鄰域拓?fù)涞南嗨菩载暙I(xiàn);基于節(jié)點(diǎn)聚類系數(shù)方法利用共同鄰居的節(jié)點(diǎn)聚類能有效提取網(wǎng)絡(luò)局部結(jié)構(gòu)信息。例如文獻(xiàn)[10]在文獻(xiàn)[9]的基礎(chǔ)上考慮節(jié)點(diǎn)和鏈接聚類系數(shù)可獲得可觀察鏈接和節(jié)點(diǎn)聚類系數(shù)信息以及文獻(xiàn)[11]提出度相關(guān)聚類系數(shù)和度相關(guān)聚類能力路徑指標(biāo)衡量節(jié)點(diǎn)聚類能力。上述方法的優(yōu)點(diǎn)是設(shè)計(jì)簡(jiǎn)單及良好的可擴(kuò)展性，可獲得較好的預(yù)測(cè)精度，缺點(diǎn)是僅考慮局部信息，無(wú)法獲得更多網(wǎng)絡(luò)結(jié)構(gòu)或節(jié)點(diǎn)聚類信息導(dǎo)致敏感于稀疏網(wǎng)絡(luò)[12]。

全局方法啟用整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)信息去計(jì)算未鏈接節(jié)點(diǎn)對(duì)分?jǐn)?shù)。例如文獻(xiàn)[13]考慮整個(gè)網(wǎng)絡(luò)路徑信息;文獻(xiàn)[14]提出基于高階路徑相似度算法，該算法利用高階路徑作為判別特征,對(duì)種子節(jié)點(diǎn)對(duì)間的可用長(zhǎng)路徑實(shí)施懲罰；文獻(xiàn)[15]提出線性最優(yōu)化(Linear Optimization，LO)，該方法利用節(jié)點(diǎn)鄰居貢獻(xiàn)捕獲高階路徑信息。上述方法的優(yōu)點(diǎn)是顯著改善了預(yù)測(cè)準(zhǔn)確度，但缺點(diǎn)是耗時(shí)。為平衡局部與全局方法的不足，提出半局部方法，該方法可同時(shí)保持局部及三階路徑信息，其中局部路徑方法(Local Path，LP)[6]是典型的代表。文獻(xiàn)[16]提出一種基于資源傳輸路徑有效性的鏈路預(yù)測(cè)方法,該方法分析節(jié)點(diǎn)間潛在的資源傳輸路徑對(duì)資源傳輸量的影響。

現(xiàn)存大部分方法僅在宏觀上利用網(wǎng)絡(luò)局部和全局結(jié)構(gòu)信息而忽略了微觀上節(jié)點(diǎn)度與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的關(guān)聯(lián)程度。例如Shang等人[17]提出節(jié)點(diǎn)差異性指標(biāo)衡量整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)異質(zhì)性處理稀疏和樹狀網(wǎng)絡(luò)鏈路預(yù)測(cè)問(wèn)題，該方法僅考慮節(jié)點(diǎn)對(duì)的異質(zhì)性，預(yù)測(cè)精度不夠理想。此外，文獻(xiàn)[18]提出自適應(yīng)度懲罰的鏈路預(yù)測(cè)方法，該方法泛化CN、AA和RA構(gòu)建一個(gè)統(tǒng)一泛化框架，該框架取得最優(yōu)預(yù)測(cè)準(zhǔn)確度依賴于網(wǎng)絡(luò)拓?fù)涮卣?。文獻(xiàn)[19]在文獻(xiàn)[18]的基礎(chǔ)上考慮共同鄰居數(shù)量改善預(yù)測(cè)結(jié)果。以上方法通過(guò)懲罰度大的節(jié)點(diǎn)與網(wǎng)絡(luò)結(jié)構(gòu)有著密切關(guān)聯(lián)，尤其文獻(xiàn)[18-19]考慮局部結(jié)構(gòu)信息而敏感于稀疏網(wǎng)絡(luò)。

大部分真實(shí)世界的網(wǎng)絡(luò)呈現(xiàn)稀疏性，然而當(dāng)前大部分網(wǎng)絡(luò)在稀疏網(wǎng)絡(luò)獲得低質(zhì)量性能。因此，該文要解決以下兩個(gè)問(wèn)題：(1)如何衡量網(wǎng)絡(luò)被預(yù)測(cè)節(jié)點(diǎn)對(duì)的異質(zhì)性；(2)節(jié)點(diǎn)對(duì)異質(zhì)性如何與網(wǎng)絡(luò)拓?fù)涮卣飨嚓P(guān)聯(lián)。以下圍繞這兩個(gè)問(wèn)題，提出度異質(zhì)性懲罰的鏈路預(yù)測(cè)指標(biāo)。具體地，節(jié)點(diǎn)度表示節(jié)點(diǎn)與其他節(jié)點(diǎn)的聯(lián)系和關(guān)聯(lián)程度。節(jié)點(diǎn)度越高，節(jié)點(diǎn)就越重要。然而，節(jié)點(diǎn)度高的未必貢獻(xiàn)大，相反節(jié)點(diǎn)度小的反而貢獻(xiàn)大。網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)異質(zhì)性反映節(jié)點(diǎn)間鄰居信息的差異，更全面衡量整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)度分布情況。首先計(jì)算各節(jié)點(diǎn)度，再計(jì)算節(jié)點(diǎn)對(duì)異質(zhì)性，然后懲罰節(jié)點(diǎn)度異質(zhì)性大的節(jié)點(diǎn)對(duì)，構(gòu)建節(jié)點(diǎn)度異質(zhì)性懲罰框架(Node Degree Heterogeneity Penalization，NDHP)。節(jié)點(diǎn)平均聚類系數(shù)和平均最短路徑衡量網(wǎng)絡(luò)節(jié)點(diǎn)聚集能力，通過(guò)可調(diào)參數(shù)與上述框架相融合提出兩個(gè)新穎指標(biāo)，分別是基于節(jié)點(diǎn)度異質(zhì)性懲罰的平均聚類系數(shù)指標(biāo)(Node Degree Heterogeneity Penalization via Average Clustering coefficient，NDHP_AC)和基于節(jié)點(diǎn)度異質(zhì)性懲罰的平均距離(Node Degree Heterogeneity Penalization via Average Distance，NDHP_AD)。

總之，該文貢獻(xiàn)如下：

(1)針對(duì)稀疏網(wǎng)絡(luò)，提出節(jié)點(diǎn)度異質(zhì)性懲罰的鏈路預(yù)測(cè)指標(biāo)，該方法啟用節(jié)點(diǎn)異質(zhì)性衡量節(jié)點(diǎn)對(duì)差異并與網(wǎng)絡(luò)拓?fù)涮卣飨嗳诤细纳葡∈杈W(wǎng)絡(luò)預(yù)測(cè)準(zhǔn)確度；

(2)在8個(gè)真實(shí)世界稀疏網(wǎng)絡(luò)上，啟用AUC和AUPR度量評(píng)價(jià)NDHP_AD和NDHP_AC，結(jié)果表明這兩種方法性能優(yōu)于當(dāng)前現(xiàn)存代表性方法。

1 方 法

1.1 問(wèn)題描述

給定一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G(V,E),其中V表示節(jié)點(diǎn)集，E表示鏈接集，該文不允許多個(gè)鏈接和自循環(huán)存在。用X=[xij]n×n表示G的鄰接矩陣。G是無(wú)向無(wú)權(quán)網(wǎng)絡(luò)，如果節(jié)點(diǎn)之間存在鏈接,則xij=1，否則xij=0。此外，網(wǎng)絡(luò)任意節(jié)點(diǎn)x的度表示為kx,Γ(x)表示節(jié)點(diǎn)x的鄰居集合，z∈Γ(x)∩Γ(y)表示節(jié)點(diǎn)z是節(jié)點(diǎn)x和y的共同鄰居。

1.2 節(jié)點(diǎn)度異質(zhì)性框架

不同真實(shí)世界網(wǎng)絡(luò)中的節(jié)點(diǎn)扮演不同角色。例如在社交網(wǎng)絡(luò)中，有大V節(jié)點(diǎn)也有普通粉絲。在交通運(yùn)輸網(wǎng)，有交通樞紐重要的節(jié)點(diǎn)也有普通站點(diǎn)。節(jié)點(diǎn)的度是反映節(jié)點(diǎn)與其他節(jié)點(diǎn)的關(guān)聯(lián)程度，度越大，該節(jié)點(diǎn)越重要。真實(shí)世界網(wǎng)絡(luò)中度的分布是不均地存在著偏好鏈接的現(xiàn)象。節(jié)點(diǎn)度較高的偏好與度較高的相鏈接，也存在著節(jié)點(diǎn)度較高與較低的相鏈接。因此，這種現(xiàn)象就造成節(jié)點(diǎn)間異質(zhì)性。然而真實(shí)世界網(wǎng)絡(luò)節(jié)點(diǎn)度較大的貢獻(xiàn)不如節(jié)點(diǎn)度小的貢獻(xiàn)，并采用懲罰度較高節(jié)點(diǎn)方法獲得較好的預(yù)測(cè)準(zhǔn)確度。然而，這種方法無(wú)法全面評(píng)估網(wǎng)絡(luò)所有節(jié)點(diǎn)度差異僅關(guān)注節(jié)點(diǎn)共同鄰居的度差異。因此，該文關(guān)注每個(gè)節(jié)點(diǎn)度的異質(zhì)性去捕獲網(wǎng)絡(luò)全局結(jié)構(gòu)信息。設(shè)任意網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)x和y,那么它們的度分別kx和ky，則度異質(zhì)性(Degree Heterogeneity，DH)定義如下：

DH(x,y)=|kx-ky|

(1)

然而在異配網(wǎng)中，式(1)無(wú)法準(zhǔn)確衡量節(jié)點(diǎn)間的異質(zhì)性。因此，為更全面體現(xiàn)度貢獻(xiàn)，重寫式(1)如下：

(2)

式(2)的作用是抑制節(jié)點(diǎn)度的差異。

1.3 所提指標(biāo)(NDHP_AC和NDHP_AD)

式(2)利用度異質(zhì)性衡量被預(yù)測(cè)節(jié)點(diǎn)產(chǎn)生鏈接的可能性，該框架的預(yù)測(cè)準(zhǔn)確度與可調(diào)參數(shù)α有密切關(guān)聯(lián)。為彌補(bǔ)懲罰節(jié)點(diǎn)間差異導(dǎo)致節(jié)點(diǎn)度不均衡，通過(guò)可調(diào)參數(shù)α與網(wǎng)絡(luò)拓?fù)涮卣飨嗳诤汐@得更多網(wǎng)絡(luò)結(jié)構(gòu)信息。當(dāng)前研究已證實(shí)網(wǎng)絡(luò)結(jié)構(gòu)信息是鏈路預(yù)測(cè)重要的組成部分，而聚類系數(shù)和最短路徑是網(wǎng)絡(luò)拓?fù)涮卣髯钪匾闹笜?biāo)。節(jié)點(diǎn)聚類系數(shù)反映了節(jié)點(diǎn)間聚集程度，表明節(jié)點(diǎn)聚類系數(shù)越高，節(jié)點(diǎn)與其他節(jié)點(diǎn)關(guān)聯(lián)程度就越高;而平均最短路徑具有“小世界”特性，節(jié)點(diǎn)間產(chǎn)生鏈接最多不會(huì)超過(guò)6節(jié)點(diǎn)。在社交網(wǎng)絡(luò)中，聚類系數(shù)可以衡量給定用戶的朋友之間成為朋友的傾向，平均最短路徑意味著要成為朋友最多不會(huì)超過(guò)6個(gè)人。因此，該文將平均節(jié)點(diǎn)聚類系數(shù)和平均最短路徑融合到式(2)中彌補(bǔ)稀疏網(wǎng)絡(luò)節(jié)點(diǎn)鄰居信息的不足。由于任意網(wǎng)絡(luò)平均節(jié)點(diǎn)聚類系數(shù)和平均最短路徑都是一個(gè)常數(shù)，先計(jì)算每個(gè)節(jié)點(diǎn)聚類系數(shù)和最短路徑。設(shè)任意網(wǎng)絡(luò)節(jié)點(diǎn)z，聚類系數(shù)定義如下：

(3)

其中，tz表示經(jīng)過(guò)節(jié)點(diǎn)z閉合三角形個(gè)數(shù)，kz表示節(jié)點(diǎn)z的度。由式(3)可得局部平均節(jié)點(diǎn)聚類系數(shù)，有：

(4)

設(shè)網(wǎng)絡(luò)任意節(jié)點(diǎn)間最短距離矩陣為D,那么平均最短距離為：

(5)

式(4)和式(5)與式(2)相融合，提出節(jié)點(diǎn)度異質(zhì)性懲罰的平均聚類系數(shù)指標(biāo)和節(jié)點(diǎn)度異質(zhì)性懲罰的平均最短距離指標(biāo)：

(6)

(7)

其中，α是可調(diào)參數(shù)。

圖1 例證NDHP_AC和NDHP_AD相似度計(jì)算過(guò)程

兩個(gè)指標(biāo)最終預(yù)測(cè)結(jié)果通過(guò)調(diào)整參數(shù)來(lái)獲得。

為實(shí)現(xiàn)以上過(guò)程，所提指標(biāo)執(zhí)行過(guò)程如下：

算法1：NDHP_AC和NDHP_AD。

輸入：任意無(wú)向無(wú)權(quán)網(wǎng)絡(luò)的鄰接矩陣A及可調(diào)參數(shù)α；

輸出： AUC和AUPR平均值。

(1)將任意無(wú)向無(wú)權(quán)數(shù)據(jù)集轉(zhuǎn)為鄰接矩陣；

(2)將鄰接矩陣劃分為訓(xùn)練集和測(cè)試集；

(3)根據(jù)式(2)懲罰節(jié)點(diǎn)對(duì)差異大的度；

(4)根據(jù)式(4)和式(5)計(jì)算節(jié)點(diǎn)平均節(jié)點(diǎn)聚類系數(shù)和平均最短距離；

(5)根據(jù)式(6)和式(7)融合網(wǎng)絡(luò)結(jié)構(gòu)特征計(jì)算被預(yù)測(cè)節(jié)點(diǎn)對(duì)x和y的相似度分?jǐn)?shù)Sxy并生成預(yù)測(cè)分?jǐn)?shù)矩陣；

(6)根據(jù)Sxy計(jì)算AUC和AUPR。

2 實(shí)驗(yàn)結(jié)果

本節(jié)主要介紹評(píng)價(jià)度量、基準(zhǔn)方法、數(shù)據(jù)集和實(shí)驗(yàn)結(jié)果分析。

2.1 評(píng)價(jià)度量

啟用AUC[20]和AUPR[21]二個(gè)度量去衡量所有方法的性能，其中AUPR是綜合性指標(biāo)。AUC和AUPR值越高表示該方法預(yù)測(cè)準(zhǔn)確度越高，兩個(gè)度量具體定義如下：

(1)AUC(Area Under ROC Curve)是ROC曲線下的面積，可以理解為在測(cè)試集EP中的鏈接分?jǐn)?shù)大于隨機(jī)選擇的一個(gè)不存在集U-E中的鏈接分?jǐn)?shù)的概率。獨(dú)立地比較n次，若有n1次測(cè)試集中的鏈接的分?jǐn)?shù)值大于不存在集中的鏈接的分?jǐn)?shù)，有n2次兩分?jǐn)?shù)值相等,AUC定義如下：

(2)AUPR(Area Under Precision-Recall curve)是精度-召回率曲線下的面積。精度-召回率曲線即是閾值曲線，該曲線每一個(gè)點(diǎn)都對(duì)應(yīng)著不同的分?jǐn)?shù)閾值，具有不同的精度和召回率。

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

采用8真實(shí)世界無(wú)向無(wú)權(quán)網(wǎng)絡(luò)評(píng)價(jià)所有指標(biāo)性能,其拓?fù)浣Y(jié)構(gòu)特征統(tǒng)計(jì)在表1中。

其中，|V|是節(jié)點(diǎn)數(shù)，|E|是鏈接數(shù)，表示平均度，r表示網(wǎng)絡(luò)同配系數(shù)，AC表示節(jié)點(diǎn)平均聚類系數(shù)，Density表示網(wǎng)絡(luò)稀疏程度。

表1 8個(gè)真實(shí)世界無(wú)向無(wú)權(quán)網(wǎng)絡(luò)拓?fù)涮卣鹘y(tǒng)計(jì)

8個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)的數(shù)據(jù)集介紹如下：

(1)線蟲的神經(jīng)網(wǎng)絡(luò)(CELegans，CEL)[22]是由297個(gè)節(jié)點(diǎn)和 2 148條鏈接構(gòu)成。節(jié)點(diǎn)表示線蟲神經(jīng)元，節(jié)點(diǎn)間鏈接表示神經(jīng)元突觸。

(2)蛋白質(zhì)相互作用網(wǎng)絡(luò)(YEAst，YEA)[22]是由2 361個(gè)節(jié)點(diǎn)和6 646條鏈接組成。節(jié)點(diǎn)表示蛋白質(zhì)，節(jié)點(diǎn)間鏈接表示相互作用關(guān)系。

(3)青少年健康網(wǎng)絡(luò)(ADOlescent，ADO)[22]是根據(jù)1994/1995年的一項(xiàng)調(diào)查創(chuàng)建的。一個(gè)節(jié)點(diǎn)代表一個(gè)學(xué)生，兩個(gè)學(xué)生之間的邊表明左學(xué)生選擇了右學(xué)生作為朋友。

(4)論文引用網(wǎng)絡(luò)(SciMet，SM)[23]是來(lái)自Garfield使用HistCite軟件生成的引用網(wǎng)絡(luò)數(shù)據(jù)集。節(jié)點(diǎn)表示論文，鏈接表示論文間引用關(guān)系。

(5)腦神經(jīng)網(wǎng)絡(luò)(NBFly,NBF)[23]是來(lái)源腦網(wǎng)絡(luò)，由1 781個(gè)節(jié)點(diǎn)和8 911條鏈接組成。節(jié)點(diǎn)表示纖維束，鏈接表示纖維束之間關(guān)系。

(6)國(guó)際電子公路網(wǎng)絡(luò)(ROAD)[22]，該網(wǎng)絡(luò)節(jié)點(diǎn)代表城市，兩個(gè)節(jié)點(diǎn)之間的邊表示它們由一條電子公路連接。

(7)朋友網(wǎng)絡(luò)(HAMster,HAM)[20]包含了hamster.com網(wǎng)站用戶之間的友誼和家庭聯(lián)系。

(8)電子郵件網(wǎng)絡(luò)(EMAil,EMA)[23]是Rovirai Virgili大學(xué)成員之間電子郵件交流網(wǎng)絡(luò)。節(jié)點(diǎn)表示成員，鏈接表示成員間電子郵件間次數(shù)。

2.3 基準(zhǔn)方法

為驗(yàn)證所提算法性能，啟用10個(gè)最近幾年的代表性方法與之比較。10個(gè)鏈路預(yù)測(cè)方法介紹如下：

(1)3個(gè)基于自包含協(xié)同過(guò)濾框架(Self-included Collaborative Filtering,SCF)融合(CN、AA和RA)的SCF-CN、SCF-AA和SCF-RA的指標(biāo)[8]，其框架定義如下：

SSCF=(A+I)S+[(A+I)S]T

(2)線性最優(yōu)化(Linear Optimization，LO)[15],該指標(biāo)假設(shè)兩個(gè)節(jié)點(diǎn)之間存在鏈接的可能性可以通過(guò)相鄰節(jié)點(diǎn)貢獻(xiàn)的線性求和來(lái)展開，其定義如下：

SL0=αA3-α2A5+α3A7-α4A9+…

(3)偏好連接指標(biāo)(Preferential Attachment ，PA)[24]，該指標(biāo)核心思想是節(jié)點(diǎn)度大的更容易產(chǎn)生鏈接，其定義如下：

(4)局部路徑指標(biāo) (Local Path，LP)[6]，該指標(biāo)擴(kuò)展CN指標(biāo),考慮三階路徑因素,其定義如下：

(5)節(jié)點(diǎn)聚類系數(shù)鏈路預(yù)測(cè)指標(biāo)(Clustering Coefficient for Link Prediction，CCLP)[9]，該方法利用節(jié)點(diǎn)共同鄰居聚類系數(shù)捕獲局部結(jié)構(gòu)信息，其定義如下：

其中，tz表示經(jīng)過(guò)z的三角形數(shù)。

(6)共同鄰居度懲罰指標(biāo)(Common Neighbors Degree Penalization，CNDP)[19]，該方法是在自適應(yīng)懲罰方法基礎(chǔ)上考慮共同鄰居數(shù)，任意節(jié)點(diǎn)相似度定義如下：

其中，|Cz|是共同鄰居數(shù)。

(7)Katz指標(biāo)[13]，該方法考慮整個(gè)網(wǎng)絡(luò)所有節(jié)點(diǎn)的路徑，其定義如下：

S=(I-α·A)-1-I

其中，I是單位矩陣，α是可調(diào)參數(shù)。

(8)矩陣森林指標(biāo)(Matrix-Forest Index，MFI)[25]，該指標(biāo)基于矩陣森林提出的全局指標(biāo)，其定義如下：

S=(I+αL)-1

其中，L是拉普拉斯矩陣，α是可調(diào)參數(shù)。

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

實(shí)驗(yàn)硬件平臺(tái)為Intel Core i5-7200U CPU筆記本，主頻2.71 GHz，內(nèi)存4 GB，操作系統(tǒng)為Windows 10，所有方法使用Matlab R2016b實(shí)現(xiàn)。此外，所提方法含可調(diào)參數(shù)，為公平比較所有的方法，在所有數(shù)據(jù)集中設(shè)α=0.5。而其余指標(biāo)LO可調(diào)參數(shù)為0.1，LP可調(diào)參數(shù)為0.001,CNDP可調(diào)參數(shù)為1.5，Katz可調(diào)參數(shù)為0.01。

通過(guò)兩個(gè)實(shí)驗(yàn)評(píng)估所提方法的性能。首先，啟用AUC和AUPR度量全面評(píng)估所有12個(gè)指標(biāo)性能；然后，評(píng)估可調(diào)參數(shù)α對(duì)所提方法性能的影響。

對(duì)于第一實(shí)驗(yàn)，啟用AUC和AUPR度量評(píng)估所有12指標(biāo)性能，實(shí)驗(yàn)結(jié)果見表2，并觀察到以下四個(gè)現(xiàn)象：

(1)所提兩個(gè)指標(biāo)(NDHP_AD和NDHP_AC)在8個(gè)數(shù)據(jù)集中AUC和AUPR獲得最優(yōu)，表明充分利用網(wǎng)絡(luò)結(jié)構(gòu)信息可以有效改善稀疏網(wǎng)絡(luò)的性能。NDHP_AD性能略優(yōu)于NDHP_AC,其主要原因是聚類系數(shù)在8個(gè)稀疏網(wǎng)絡(luò)無(wú)法獲得更多節(jié)點(diǎn)鄰居信息而最短路徑獲得更多節(jié)點(diǎn)鄰域信息。通過(guò)表1可以觀察到數(shù)據(jù)集CEL、HAM、BNF、YEA和SM的同配系數(shù)為負(fù)數(shù)，表明以上網(wǎng)絡(luò)中存在大量度大的節(jié)點(diǎn)與度小的節(jié)點(diǎn)相鏈接，由此造成節(jié)點(diǎn)間度異質(zhì)性，所提方法采用懲罰機(jī)制，結(jié)果表明該機(jī)制有效可行。此外，除了CEL數(shù)據(jù)集外，其余數(shù)據(jù)集均為高度稀疏網(wǎng)絡(luò)，所提指標(biāo)在高度稀疏網(wǎng)絡(luò)中均獲得高性能。

(2)所提指標(biāo)與五個(gè)局部相似度方法(SCF-CN、SCF-AA、SCF-RA、PA和CCLP)相對(duì)比，性能獲得顯著的改善。在AUC度量，NDHP_AD和NDHP_AC指標(biāo)與五個(gè)指標(biāo)中最好第二指標(biāo)在數(shù)據(jù)集上CEL、HAM、BNF、ROAD、EMA、ADO、YEA和SM相比較，分別提升了10%、3.1%、9.2%、22%、13%、6.3%、7.2%和6.2%；同理，在AUPR度量，在數(shù)據(jù)集上CEL、HAM、BNF、ROAD、EMA、ADO、YEA和SM分別提高了7.9%、7.7%、10.3%、20%、26%、13%、27%和20%。上述五個(gè)指標(biāo)獲得低質(zhì)量性能的主要原因是稀疏網(wǎng)絡(luò)中無(wú)法獲得足夠的結(jié)構(gòu)信息，盡管基于協(xié)同過(guò)濾框架利用對(duì)稱性增強(qiáng)了獲取局部結(jié)構(gòu)信息能力，然而高度稀疏網(wǎng)絡(luò)中局部結(jié)構(gòu)信息是有限的。

(3)NDHP_AD和NDHP_AC與三個(gè)全局指標(biāo)(MFI、Katz和LO)相比較，所提指標(biāo)獲得最優(yōu)性能。三個(gè)全局指標(biāo)性能最接近所提指標(biāo)，主要原因是全局指標(biāo)獲得整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，如Katz可獲得整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)路徑信息，LO可獲得整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的鄰居貢獻(xiàn)值，因此全局指標(biāo)可以用全局結(jié)構(gòu)信息彌補(bǔ)稀疏性不足。MFI指標(biāo)優(yōu)于LO和Katz的原因是該方法核心任意一個(gè)為根節(jié)點(diǎn)生成森林再統(tǒng)計(jì)與此根節(jié)點(diǎn)相似的節(jié)點(diǎn)的比例。

(4)半局部相似度算法(LP和CNDP)的核心平衡時(shí)間復(fù)雜度和性能關(guān)系。該方法的缺點(diǎn)是無(wú)法完全捕獲整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)信息而導(dǎo)致敏感于稀疏網(wǎng)絡(luò)。通過(guò)表2可觀察到，以上兩種方法僅在數(shù)據(jù)集CEL中獲得相對(duì)較好的性能，而在其余數(shù)據(jù)集中與全局方法相比均獲得低質(zhì)量性能，主要原因是LP方法僅考慮三階路徑信息，而CNDP僅利用整個(gè)網(wǎng)絡(luò)平均節(jié)點(diǎn)聚類系數(shù)。此外，文中方法與LP和CNDP在高度稀疏網(wǎng)絡(luò)中相比性能顯著提升。在數(shù)據(jù)集YEA中，文中方法AUC和AUPR分別提高了14%和46%。

表2 8個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)上12個(gè)不同指標(biāo)對(duì)應(yīng)AUC和AUPR值

NDHP_AC和NDHP_AD帶有可調(diào)參數(shù)α，該參數(shù)的作用是平衡節(jié)點(diǎn)度異質(zhì)性和網(wǎng)絡(luò)結(jié)構(gòu)信息關(guān)聯(lián)程度。設(shè)可調(diào)參數(shù)α的范圍為[-1,-0.5,0,0.5,1,1.5]，實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

圖2 參數(shù)α變化對(duì)NDHP_AC性能影響

圖3 參數(shù)α變化對(duì)NDHP_AD性能影響

可觀察到當(dāng)α為負(fù)數(shù)時(shí)，AUC和AUPR值最低，主要原因是未調(diào)用懲罰機(jī)制去抑制度異質(zhì)性;當(dāng)α=0時(shí)，文中方法退化為節(jié)點(diǎn)度差異代表相似度分?jǐn)?shù)，此時(shí)AUC和AUPR值最低，主要原因是在無(wú)法啟用懲罰機(jī)制及利用網(wǎng)絡(luò)結(jié)構(gòu)信息；當(dāng)α為正數(shù)時(shí)，文中方法可以調(diào)用懲罰機(jī)制及充分利用網(wǎng)絡(luò)結(jié)構(gòu)信息獲得最優(yōu)的性能。因此，當(dāng)α=0.5時(shí)，NDHP_AC性能最優(yōu)。

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

探索和利用網(wǎng)絡(luò)結(jié)構(gòu)是鏈路預(yù)測(cè)的重要組成部分，如何將網(wǎng)絡(luò)結(jié)構(gòu)和度差異相結(jié)合適用于稀疏網(wǎng)絡(luò)是一個(gè)挑戰(zhàn)性問(wèn)題。該文提出節(jié)點(diǎn)度異質(zhì)性懲罰的鏈路預(yù)測(cè)指標(biāo)，該指標(biāo)利用節(jié)點(diǎn)度異質(zhì)性捕獲網(wǎng)路全局結(jié)構(gòu)，再利用節(jié)點(diǎn)聚類系數(shù)衡量節(jié)點(diǎn)間聚合能力，然后結(jié)合平均節(jié)點(diǎn)聚類系數(shù)保持網(wǎng)絡(luò)局部結(jié)構(gòu)。采用8個(gè)稀疏網(wǎng)絡(luò)與10個(gè)最近代表性方法測(cè)試所提方法的性能，結(jié)果表明該方法性能上遠(yuǎn)超其他基準(zhǔn)方法，同時(shí)健壯于高度稀疏網(wǎng)絡(luò)。

未來(lái)嘗試將網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)與節(jié)點(diǎn)屬性信息融入該方法，此外可以擴(kuò)展該方法到加權(quán)和有向網(wǎng)絡(luò)。