融合節(jié)點(diǎn)中心性和度相關(guān)聚類的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)

陳廣福,連雁平

(1.武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院,福建 武夷山 354399; 2.福建省茶產(chǎn)業(yè)大數(shù)據(jù)應(yīng)用與智能化重點(diǎn)實(shí)驗(yàn)室,福建 武夷山 354399)

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è)算法被提出來(lái)，其中拓?fù)浣Y(jié)構(gòu)的鏈路預(yù)測(cè)方法設(shè)計(jì)簡(jiǎn)潔，具有良好的可擴(kuò)展性以及高預(yù)測(cè)準(zhǔn)確度。基于拓?fù)浣Y(jié)構(gòu)方法又可劃分為局部、半局部和全局方法。局部方法核心是利用網(wǎng)絡(luò)節(jié)點(diǎn)間共同鄰居數(shù)量、聚類系數(shù)和度相關(guān)的聚類系數(shù)計(jì)算節(jié)點(diǎn)分?jǐn)?shù),其中共同鄰居(Common Neighbors， CN)[5]、資源分配(Resource Allocation, RA)[6]、(Adamic-Adar， AA)[7]指標(biāo)和聚類系數(shù)鏈路預(yù)測(cè)(Clustering Coefficient for Link Prediction, CCLP)[8]等是典型方法。此外，文獻(xiàn)[9]提出了一種基于二級(jí)節(jié)點(diǎn)聚類系數(shù)的鏈路預(yù)測(cè)方法，該方法提取種子節(jié)點(diǎn)對(duì)的二級(jí)共同近鄰的聚類信息，并根據(jù)該信息計(jì)算相似度評(píng)分;郁湧等人[10]將節(jié)點(diǎn)中心性與節(jié)點(diǎn)共同鄰居的聚類系數(shù)和度相融合提出聚類系數(shù)和節(jié)點(diǎn)中心性鏈路預(yù)測(cè)方法；文獻(xiàn)[11]提出了一種融合度相關(guān)聚類系數(shù)和結(jié)構(gòu)一致性的鏈路預(yù)測(cè)方法捕獲網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。全局方法利用整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)計(jì)算節(jié)點(diǎn)對(duì)相似度分?jǐn)?shù)，例如Katz指標(biāo)[12]。半局部方法平衡局部和全局性能與復(fù)雜度，其中局部路徑(LP)指標(biāo)[13]是典型代表。然而，以上現(xiàn)存算法不足是僅適用無(wú)向無(wú)權(quán)網(wǎng)絡(luò)。

真實(shí)世界網(wǎng)絡(luò)存在著大量的有向網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)對(duì)間的鏈接方向代表著不同意義[14]。例如，在交通運(yùn)輸網(wǎng)中，鏈接方向表示站點(diǎn)間不對(duì)稱距離;在引用網(wǎng)絡(luò)中，鏈接方向代表引文間單向引用關(guān)系;在食物網(wǎng)中，鏈接方向描述不同種群捕食關(guān)系。因此，節(jié)點(diǎn)間鏈接方向信息是不可忽略的。當(dāng)前，大部分鏈路預(yù)測(cè)算法將有向網(wǎng)絡(luò)看作無(wú)向網(wǎng)絡(luò)，忽略有向鏈接信息。最近幾年，一些研究人員已關(guān)注有向網(wǎng)絡(luò)的鏈路預(yù)測(cè)問(wèn)題。文獻(xiàn)[15]首次將CN、AA和RA擴(kuò)展到有向網(wǎng)絡(luò)考慮鏈接方向信息構(gòu)建(Directed Common Neighbor， DCN)、(Directed Adamic-Adar， DAA)和(Directed Resource Allocation, DRA);Bütün等人[16]在基于有向局部相似度基礎(chǔ)上進(jìn)一步考慮權(quán)重和時(shí)序信息去改善算法性能。文獻(xiàn)[17]考慮互惠鏈接信息提出互惠意識(shí)權(quán)重機(jī)制的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)算法。文獻(xiàn)[18]提出了一種基于勢(shì)能理論的Bifan的方法，該方法考慮節(jié)點(diǎn)的鄰居的節(jié)點(diǎn)信息。此外，Ghorbanzadeh等人[19]提出無(wú)監(jiān)督和監(jiān)督學(xué)習(xí)預(yù)測(cè)有向網(wǎng)絡(luò)節(jié)點(diǎn)間無(wú)共同鄰居形成概率；Yi等人[20]提出有向網(wǎng)絡(luò)高階結(jié)構(gòu)的自動(dòng)編碼器模型，該模型包含有向網(wǎng)絡(luò)高階路徑信息和多個(gè)有向模體的鄰接矩陣信息。

有向網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性是由節(jié)點(diǎn)中心性、介數(shù)中心性和接近中心性來(lái)衡量。度中心性最直接反映節(jié)點(diǎn)的影響力。例如在線社交網(wǎng)絡(luò)的大V節(jié)點(diǎn)和WWW網(wǎng)絡(luò)中的中心節(jié)點(diǎn)。節(jié)點(diǎn)聚類系數(shù)反映節(jié)點(diǎn)聚集能力，然而該方法敏感于稀疏網(wǎng)絡(luò)。本文將節(jié)點(diǎn)中心性和度相關(guān)聚類系數(shù)方法推廣到有向網(wǎng)絡(luò)，并提出節(jié)點(diǎn)中心性和度相關(guān)聚類的鏈路預(yù)測(cè)方法(Node Centrality and Degree-related Clustering for Link Prediction, NCDCLP)。首先，計(jì)算有向網(wǎng)絡(luò)中任意節(jié)點(diǎn)的出度和入度的和，將節(jié)點(diǎn)中心性與Bifan模體相融合獲得更多節(jié)點(diǎn)鄰居信息；其次，定義有向網(wǎng)絡(luò)度相關(guān)聚類系數(shù)方法并計(jì)算出同配系數(shù)，再依據(jù)同配系數(shù)與其節(jié)點(diǎn)度值增減趨勢(shì)一致性，融合度相關(guān)聚類系數(shù)與同配系數(shù)衡量節(jié)點(diǎn)聚類能力。最后，實(shí)驗(yàn)結(jié)果表明NCDCLP指標(biāo)性能獲得顯著的提高。

1 方 法

1.1 問(wèn)題描述

1.2 節(jié)點(diǎn)中心性和度相關(guān)聚類系數(shù)

節(jié)點(diǎn)中心性是衡量節(jié)點(diǎn)重要性的指標(biāo)之一，本文將該指標(biāo)擴(kuò)展到有向網(wǎng)絡(luò)中去評(píng)價(jià)有向網(wǎng)絡(luò)節(jié)點(diǎn)的影響力。節(jié)點(diǎn)影響力越大，與其他節(jié)點(diǎn)就越容易產(chǎn)生鏈接。在有向網(wǎng)絡(luò)中任意vi節(jié)點(diǎn)中心性定義如下:

(1)

在有向網(wǎng)絡(luò)中具有Bifan模體結(jié)構(gòu)性能最優(yōu)，因此將節(jié)點(diǎn)中心性與Bifan模體結(jié)構(gòu)相融合捕獲更多節(jié)點(diǎn)鄰居信息。如圖1所示，根據(jù)勢(shì)能理論節(jié)點(diǎn)vy和vj處于最高層次，而節(jié)點(diǎn)vx和vi處于最低層次，顯然節(jié)點(diǎn)vy的影響力小于節(jié)點(diǎn)vj。節(jié)點(diǎn)vi是節(jié)點(diǎn)vj與節(jié)點(diǎn)vy的共同鄰居，節(jié)點(diǎn)vj與節(jié)點(diǎn)vx產(chǎn)生鏈接，受節(jié)點(diǎn)vj的影響，根據(jù)勢(shì)能理論節(jié)點(diǎn)vy與節(jié)點(diǎn)vx間形成鏈接的可能性高。

圖1 用Bifan模體描述節(jié)點(diǎn)影響力

因此，節(jié)點(diǎn)中心性與Bifan模體融合定義如下：

(2)

(3)

由于真實(shí)世界網(wǎng)絡(luò)是不完整的存在大量缺失鏈接，因此節(jié)點(diǎn)聚類系數(shù)方法無(wú)法有效衡量節(jié)點(diǎn)聚類能力。度相關(guān)聚類方法通過(guò)節(jié)點(diǎn)鄰居信息可更有效評(píng)估節(jié)點(diǎn)聚類能力。本方將該方法擴(kuò)展到有向網(wǎng)絡(luò)中，評(píng)估通過(guò)節(jié)點(diǎn)出度信息來(lái)衡量有向網(wǎng)絡(luò)節(jié)點(diǎn)聚類能力。有向網(wǎng)絡(luò)聚類系數(shù)定義如下[21]：

(4)

由式(4)可得節(jié)點(diǎn)平均聚類系數(shù)，定義如下：

(5)

(6)

(7)

其中，l是網(wǎng)絡(luò)總鏈接數(shù)。

式(7)的作用是通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)信息-同配系數(shù)與平均節(jié)點(diǎn)聚類系數(shù)相結(jié)合去改善節(jié)點(diǎn)聚類能力。為更效衡量有向網(wǎng)絡(luò)局部節(jié)點(diǎn)聚類能力，重寫等式(7)，得：

(8)

1.3 所提方法的NCDCLP指標(biāo)

通過(guò)融合式(3)和式(8)并引可調(diào)參數(shù)α共同構(gòu)建統(tǒng)一的鏈路預(yù)測(cè)指標(biāo)NCDCLP,得：

SNCDCLP=SDC+αSDCC

(9)

其中，α是可調(diào)參數(shù)，其作用是控制度相關(guān)聚類系數(shù)的貢獻(xiàn)。所提方法NCDCLP執(zhí)行過(guò)程如算法1所示。

算法1 NCDCLP算法

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

輸出：AUC和AUPR值

1．將A按9∶1的比例劃分為訓(xùn)練集和測(cè)試集。

2．根據(jù)式(3)計(jì)算有向網(wǎng)絡(luò)節(jié)點(diǎn)中心性。

3．根據(jù)式(8)計(jì)算有向網(wǎng)絡(luò)度相關(guān)性聚類系數(shù)。

4．根據(jù)式(9)計(jì)算任意節(jié)點(diǎn)對(duì)相似度分?jǐn)?shù)。

5．對(duì)相似度分?jǐn)?shù)按降序進(jìn)行排列。

6．計(jì)算AUC和AUPR值。

7．計(jì)算平均AUC和AUPR值。

急性心肌梗死在臨床上較為常見(jiàn)，指的是冠狀動(dòng)脈急性、持續(xù)性缺血缺氧造成的心肌壞死，癥狀為胸骨后疼痛。該病具有較高的發(fā)病率，其危險(xiǎn)因素包括有抽煙酗酒、過(guò)度勞累、暴飲暴食、寒冷刺激以及情緒激動(dòng)等，還有心肌內(nèi)耗氧量的增加、冠狀動(dòng)脈痙攣等[1] 。需要及時(shí)進(jìn)行有效的治療，挽救患者的生命安全。本次主要采用氯吡格雷聯(lián)合阿司匹林對(duì)我院診斷為急性心肌梗死的70例患者進(jìn)行治療，以下是詳細(xì)報(bào)告。

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

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

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

本文啟用AUC[22]和AUPR[23]這2個(gè)度量去衡量所有方法的性能，2個(gè)度量具體定義如下：

1)AUC可以理解為在測(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ù)集

本文采用6個(gè)真實(shí)世界有向網(wǎng)絡(luò)評(píng)價(jià)所有方法的性能,其拓?fù)浣Y(jié)構(gòu)特征統(tǒng)計(jì)見(jiàn)表1。

表1 6個(gè)真實(shí)世界有向網(wǎng)絡(luò)拓?fù)涮卣鹘y(tǒng)計(jì)

1)論文引用網(wǎng)絡(luò)(SmaGr,SG)[24]。該網(wǎng)絡(luò)是關(guān)于網(wǎng)絡(luò)理論與實(shí)驗(yàn)的引用網(wǎng)絡(luò),它由1024個(gè)節(jié)點(diǎn)和4916條鏈接組成。鏈接方向表示引用關(guān)系。

2)歐洲電子郵件核心子集網(wǎng)(EMAil,EMA)[25]。該網(wǎng)絡(luò)是使用來(lái)自大型歐洲研究機(jī)構(gòu)的電子郵件數(shù)據(jù)生成的。一個(gè)節(jié)點(diǎn)表示研究機(jī)構(gòu)成員,一個(gè)鏈接表示研究機(jī)構(gòu)成員之間的所有傳入和傳出電子郵件。

4)蛋白質(zhì)交互網(wǎng)絡(luò)(FIgeY,FIY)[26]。該網(wǎng)絡(luò)是人類蛋白質(zhì)之間相互作用的網(wǎng)絡(luò)，節(jié)點(diǎn)表示蛋白質(zhì)，方向鏈接表示蛋白質(zhì)間交互關(guān)系。

5)維基百科(Wikipedia Talk, WT)[26]。該數(shù)據(jù)集是威爾士維基百科的通訊網(wǎng)絡(luò)。節(jié)點(diǎn)表示用戶，邊表示用戶在某個(gè)時(shí)間戳在另外用戶的對(duì)話頁(yè)面上寫了一條消息。

6)美國(guó)航空網(wǎng)(USAir,USA)[26]。該網(wǎng)絡(luò)是由332個(gè)節(jié)點(diǎn)和1063條鏈接構(gòu)成，其節(jié)點(diǎn)表示機(jī)場(chǎng)且節(jié)點(diǎn)間鏈接表示航線。

2.3 基準(zhǔn)方法

為驗(yàn)證所提有向鏈路預(yù)測(cè)算法性能，本文啟用11個(gè)最近幾年的代表性方法與之比較。11個(gè)有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法介紹如下：

1)3個(gè)基于有向局部相似度(DCN,DAA,DRA)[15]是擴(kuò)展無(wú)向無(wú)權(quán)局部CN、AA和RA指標(biāo)以及基于勢(shì)能理論的最佳模體(Bifan)[18]方法，具體定義如下：

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

SLO=αA(αATA+I)-1ATA

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

3)大度節(jié)點(diǎn)有利指標(biāo)(Hub Promoted Index, HPI)[28],該指標(biāo)表示代謝網(wǎng)絡(luò)中兩節(jié)點(diǎn)端點(diǎn)的相似程度，其定義如下：

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

5)間接互惠感知加權(quán)指標(biāo)(Indirect Reciprocity-aware Weighting, IRW)與有向網(wǎng)絡(luò)DCN、DAA、DRA構(gòu)建新的指標(biāo)，其定義如下：

以上3個(gè)指標(biāo)詳細(xì)的介紹請(qǐng)參閱文獻(xiàn)[17]。

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)。此外，本文所提4個(gè)方法均含可調(diào)參數(shù)α，為公平比較所有的方法，在數(shù)據(jù)中設(shè)α=0.01。其他指標(biāo)LO中可調(diào)參數(shù)設(shè)為0.1，LP指標(biāo)參數(shù)設(shè)為0.01。

本文做3個(gè)實(shí)驗(yàn)評(píng)估所提方法的性能。首先，啟用AUC和AUPR度量全面評(píng)估所有11個(gè)指標(biāo)性能;其次，測(cè)試11個(gè)指標(biāo)的健壯性;最后，檢驗(yàn)可調(diào)參數(shù)對(duì)所提方法性能的影響。

第1個(gè)實(shí)驗(yàn)啟用AUC和AUPR這2個(gè)度量在6個(gè)數(shù)據(jù)集上全面評(píng)估11個(gè)指標(biāo)性能，其實(shí)驗(yàn)結(jié)果報(bào)告在表2中，并觀察到以下一些現(xiàn)象：

表2 6個(gè)有向網(wǎng)絡(luò)上11個(gè)不同方法對(duì)應(yīng)AUC和AUPR值

1)在AUC度量，除EMA數(shù)據(jù)集以外，所提指標(biāo)在其他數(shù)據(jù)集上的預(yù)測(cè)準(zhǔn)確度最優(yōu);在AUPR度量，本文方法在所有的數(shù)據(jù)集上均獲得高質(zhì)量性能。

2)本文方法與4個(gè)有向局部指標(biāo)(DCN、DAA、DRA和HPI)相比較，前者性能獲得顯著提高。4個(gè)局部方法獲得低質(zhì)量性能主要原因是依賴節(jié)點(diǎn)對(duì)共同鄰居數(shù)量計(jì)算節(jié)點(diǎn)對(duì)相似度分?jǐn)?shù)。

3)Bifan和LP是三階路徑的半局部方法，考慮鄰居節(jié)點(diǎn)信息，因此該類方法與局部方法有顯著的改善。從表2可觀察到Bifan和LP在所有數(shù)據(jù)集均好于局部方法。而LO是全局方法在AUPR上顯著優(yōu)于Bifan和LP，表明利用整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)信息可有效提高性能。以上3個(gè)方法性能最接近本文方法，而本文方法在所有數(shù)據(jù)集上性能明顯高于上述3個(gè)方法，其主要原因該方法捕獲影響力大節(jié)點(diǎn)獲得更多鄰居信息。例如在數(shù)據(jù)集WT,從表1知該數(shù)據(jù)集中節(jié)點(diǎn)最大出度及入度和為2663，盡管在AUC度量上Bifan與本文方法比較接近，但在綜合性度量AUPR上NCDCLP性能明顯優(yōu)于Bifan指標(biāo)。

4)間接互惠感知加權(quán)3個(gè)指標(biāo)啟用互惠鏈接信息作為權(quán)重并結(jié)合有向網(wǎng)絡(luò)一階相似度，該類方法只有充分捕獲互惠鏈接信息情況下才能獲得預(yù)測(cè)準(zhǔn)確度。若是稀疏網(wǎng)絡(luò)導(dǎo)致該類方法性能不足，例如在數(shù)據(jù)集FIY中，互惠鏈接比率為0.0031，以上3個(gè)指標(biāo)預(yù)測(cè)準(zhǔn)確度不高;而在數(shù)據(jù)集EMA，互惠鏈接比率為0.3356時(shí)，預(yù)測(cè)準(zhǔn)確度顯著提高。本文方法通過(guò)捕獲節(jié)點(diǎn)鄰居信息與節(jié)點(diǎn)聚類能力來(lái)彌補(bǔ)網(wǎng)絡(luò)稀疏性。因此，NCDCLP獲得優(yōu)異性能。

對(duì)于第2個(gè)實(shí)驗(yàn)，測(cè)試11個(gè)預(yù)測(cè)者的健壯性。通過(guò)改變訓(xùn)練集大小來(lái)改變?cè)季W(wǎng)絡(luò)的稀疏性。本實(shí)驗(yàn)設(shè)訓(xùn)練集大小范圍為[40%,50%,…,90%],若訓(xùn)練集比例太小會(huì)破壞網(wǎng)絡(luò)結(jié)構(gòu)導(dǎo)致預(yù)測(cè)準(zhǔn)確度不準(zhǔn)確，其實(shí)驗(yàn)結(jié)果報(bào)告在圖2和圖3中并得到以下一些觀察：

圖2 不同比例訓(xùn)練集下11個(gè)指標(biāo)對(duì)應(yīng)不同AUC值

圖3 不同比例訓(xùn)練集下11個(gè)指標(biāo)對(duì)應(yīng)不同AUPR值

1)在AUC和AUPR度量，大部分?jǐn)?shù)據(jù)集中本文方法均優(yōu)于在其它指標(biāo)。DCN、DAA、DRA和HPI這4個(gè)指標(biāo)在不同訓(xùn)練集大小波動(dòng)明顯，主要原因是隨著網(wǎng)絡(luò)稀疏性增加，以上4個(gè)指標(biāo)無(wú)法獲取更多節(jié)點(diǎn)對(duì)共同鄰居信息。而LO、LP和Bifan指標(biāo)可獲得三階以上路徑信息來(lái)彌補(bǔ)網(wǎng)絡(luò)稀疏性，在不同訓(xùn)練集下獲得較好的性能。NCDCLP指標(biāo)在不同比例訓(xùn)練集下僅有略微波動(dòng)，尤其在數(shù)據(jù)集WT,FIY和SG中，本文方法表現(xiàn)出優(yōu)秀魯棒性。

2)當(dāng)訓(xùn)練集大小為40%時(shí)，網(wǎng)絡(luò)處于十分稀疏性情況下，NCDCLP指標(biāo)在大部分?jǐn)?shù)據(jù)集中AUC和AUPR最佳，表明該方法適用于稀疏性。

第3個(gè)實(shí)驗(yàn)測(cè)試可調(diào)參數(shù)α的敏感性，設(shè)可調(diào)參數(shù)α的范圍為[0,0.01,0.1,0.5,1,1.5]，其實(shí)驗(yàn)結(jié)果報(bào)告如圖4所示。當(dāng)α=0時(shí)，NCDCLP方法在所有數(shù)據(jù)集中均獲得低質(zhì)量性能，尤其在WT、SM和FIY中，AUPR值較小，其主要原因是本文方法僅依靠節(jié)點(diǎn)鄰居信息無(wú)法獲得足夠的網(wǎng)絡(luò)結(jié)構(gòu)信息。隨著α值增加，AUC和AUPR值開(kāi)始逐漸增大。直到當(dāng)α=0.01時(shí)，AUC和AUPR值達(dá)到最優(yōu)，其主要原因是本文方法獲得足夠節(jié)點(diǎn)鄰居信息以及網(wǎng)絡(luò)結(jié)構(gòu)信息來(lái)提高節(jié)點(diǎn)聚類能力。隨著α值繼續(xù)增加，AUC和AUPR值開(kāi)始保持恒定，但在EMA、SM和USA中有逐漸下降的趨勢(shì)，表明α值過(guò)大反而影響算法的節(jié)點(diǎn)聚類能力。因此，當(dāng)α=0.01時(shí)本文算法在所有數(shù)據(jù)集中均獲得最優(yōu)性能。

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

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

針對(duì)大部分現(xiàn)存鏈路預(yù)測(cè)方法將有向網(wǎng)絡(luò)看作無(wú)向網(wǎng)絡(luò)而忽略連接方向的問(wèn)題，本文提出了一個(gè)新穎的節(jié)點(diǎn)中心性和度相關(guān)聚類系數(shù)的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)指標(biāo)。該方法將節(jié)點(diǎn)中心性和度相關(guān)聚類系數(shù)推廣到有向網(wǎng)絡(luò)中，通過(guò)捕獲節(jié)點(diǎn)鄰居信息提高節(jié)點(diǎn)間產(chǎn)生鏈接可能性。此外，利用節(jié)點(diǎn)度與同配網(wǎng)絡(luò)系數(shù)增減趨勢(shì)一致性去提高節(jié)點(diǎn)聚類能力。在6個(gè)真實(shí)有向網(wǎng)絡(luò)上，本文方法在預(yù)測(cè)缺失鏈接方向和魯棒性上優(yōu)于當(dāng)前代表性有向網(wǎng)絡(luò)鏈路預(yù)測(cè)指標(biāo)。

本文是從節(jié)點(diǎn)角度出發(fā)解決有向網(wǎng)絡(luò)鏈路預(yù)測(cè)問(wèn)題，在將來(lái)工作中可以從鏈接角度如鏈接聚類系數(shù)和鏈接介數(shù)等去捕獲網(wǎng)絡(luò)結(jié)構(gòu)信息。