陳廣福，王海波，連雁平

（1.武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 武夷山 354300；2.認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室（武夷學(xué)院），福建 武夷山 354300；3.湖南科技學(xué)院 信息工程學(xué)院，湖南 永州 425199）

0 引言

真實(shí)世界大量的復(fù)雜系統(tǒng)可使用復(fù)雜網(wǎng)絡(luò)來(lái)描述和表示。在復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)代表實(shí)體而鏈接表示實(shí)體間關(guān)系。然而，由于構(gòu)建真實(shí)復(fù)雜網(wǎng)絡(luò)時(shí)受復(fù)雜系統(tǒng)復(fù)雜性、噪聲及實(shí)驗(yàn)條件等影響，所構(gòu)建復(fù)雜網(wǎng)絡(luò)容易出現(xià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è)還具有以下兩個(gè)功能：1）它可以預(yù)測(cè)缺失鏈接包括無(wú)向、加權(quán)和方向鏈接以及識(shí)別虛假鏈接；2）根據(jù)當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)信息去演繹網(wǎng)絡(luò)演化過(guò)程。因此，鏈路預(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］。

現(xiàn)存大部分鏈接預(yù)測(cè)方法把有向網(wǎng)絡(luò)看作無(wú)向無(wú)權(quán)網(wǎng)絡(luò)而忽略鏈接方向，導(dǎo)致預(yù)測(cè)不準(zhǔn)確。然而，大部分真實(shí)世界網(wǎng)絡(luò)是有向網(wǎng)絡(luò)，例如交通運(yùn)輸網(wǎng)絡(luò)、食物網(wǎng)、生物網(wǎng)和在線社交網(wǎng)等。不同類型有向網(wǎng)絡(luò)中，鏈接方向表示不同含義。例如在食物網(wǎng)中，鏈接方向表示不同種群捕食關(guān)系；在線社交網(wǎng)絡(luò)中，鏈接方向代表不同用戶不對(duì)稱的關(guān)系；在交通運(yùn)輸網(wǎng)中，鏈接方向表示站點(diǎn)間運(yùn)輸頻率。因此，忽略鏈接方向信息會(huì)導(dǎo)致預(yù)測(cè)結(jié)果與實(shí)際結(jié)果存在著重大偏差［5］。現(xiàn)存大部分鏈路預(yù)測(cè)僅關(guān)注無(wú)向無(wú)權(quán)網(wǎng)絡(luò)，有向網(wǎng)絡(luò)的鏈接預(yù)測(cè)問(wèn)題處于起步階段，因此如何挖掘和利用鏈接方向及有向網(wǎng)絡(luò)結(jié)構(gòu)信息是個(gè)挑戰(zhàn)問(wèn)題。近10 年來(lái)，一些研究人員關(guān)注有向網(wǎng)絡(luò)鏈路預(yù)測(cè)并取得一定進(jìn)展。例如Schall等［6］提出基于閉合三元組比率的鏈路預(yù)測(cè)方法，結(jié)果表明該方法提高了有向網(wǎng)絡(luò)預(yù)測(cè)精度；Bütün等［7］擴(kuò)展文獻(xiàn)［6］中的閉合三元組，提出基于模式有監(jiān)督的閉合三元組方法；Zhang等［8］將無(wú)向無(wú)權(quán)局部相似度方法擴(kuò)展到有向網(wǎng)絡(luò)，構(gòu)建有向局部相似度方法，結(jié)果表明這些方法可有效預(yù)測(cè)缺失有向鏈接和鑒定虛假鏈接；Bütün等［9］在文獻(xiàn)［8］的基礎(chǔ)上進(jìn)一步考慮權(quán)重和時(shí)序信息，改善算法性能。盡管以上方法預(yù)測(cè)準(zhǔn)確度有明顯提高，但是這些方法僅直接利用鏈接方向或網(wǎng)絡(luò)局部結(jié)構(gòu)，無(wú)法適用于稀疏網(wǎng)絡(luò)。此外，Shang等［10］提出有向網(wǎng)絡(luò)節(jié)點(diǎn)的相位動(dòng)態(tài)算法來(lái)分析鏈接方向的作用，并證明雙向鏈接和單向鏈接在鏈路預(yù)測(cè)和網(wǎng)絡(luò)結(jié)構(gòu)形成方面具有不同的作用；Zhang等［11］提出基于勢(shì)能理論不同模體預(yù)測(cè)指標(biāo)，結(jié)果表明Bifan 預(yù)測(cè)準(zhǔn)確度最優(yōu)；Li等［12］在文獻(xiàn)［10-11］的基礎(chǔ)上利用零模型驗(yàn)證互惠連接作用并考慮權(quán)重信息提出間接互惠感知加權(quán)（Indirect Reciprocity-aware Weighting，IRW）框架和直接互惠感知加權(quán)（Direct Reciprocity-aware Weighting，DRW）。以上研究?jī)H討論互惠連接作用，然而當(dāng)有向網(wǎng)絡(luò)可觀察鏈接較少時(shí)，無(wú)法捕獲更多網(wǎng)絡(luò)結(jié)構(gòu)信息降低預(yù)測(cè)精度。此外，Pech等［13］提出線性最優(yōu)化（Linear Optimization，LO）方法，該方法將節(jié)點(diǎn)鄰居的鄰居用線性和表示獲取網(wǎng)絡(luò)高階路徑信息；李勁松等［14］在文獻(xiàn)［13］的基礎(chǔ)上提出線性規(guī)劃方法，與LO 有相似作用。盡管以上方法在一定程度提高了有向網(wǎng)絡(luò)預(yù)測(cè)準(zhǔn)確性，然而它們共同缺點(diǎn)是無(wú)法獲取有向網(wǎng)絡(luò)更多結(jié)構(gòu)信息而敏感于稀疏網(wǎng)絡(luò)。針對(duì)以上問(wèn)題，Chen等［15］提出聯(lián)合有向網(wǎng)絡(luò)局部和全局結(jié)構(gòu)的非負(fù)矩陣分解鏈路預(yù)測(cè)方法彌補(bǔ)網(wǎng)絡(luò)稀疏性，然而該方法附加額外信息增加算法復(fù)雜度。

協(xié)同過(guò)濾方法是推薦系統(tǒng)中經(jīng)典算法，Lee等［16］提出基于協(xié)同過(guò)濾和自包含協(xié)同過(guò)濾理論框架，再融合局部相似度方法構(gòu)建一系列新鏈路預(yù)測(cè)方法。然而，該方法有兩個(gè)不足：首先，以上兩個(gè)框架僅考慮無(wú)向無(wú)權(quán)網(wǎng)絡(luò)而無(wú)法處理有向網(wǎng)絡(luò)問(wèn)題；其次，該方法僅考慮一階相似度而無(wú)法捕獲更多網(wǎng)絡(luò)結(jié)構(gòu)信息去處理網(wǎng)絡(luò)稀疏性和冷啟動(dòng)問(wèn)題。鏈路預(yù)測(cè)中冷啟動(dòng)是指孤立節(jié)點(diǎn)及新節(jié)點(diǎn)缺乏足夠的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息而難以與其他節(jié)點(diǎn)形成鏈接。本文受文獻(xiàn)［16］的啟發(fā)，將解決以下兩個(gè)問(wèn)題：1）將協(xié)同過(guò)濾方法擴(kuò)展到有向網(wǎng)絡(luò)；2）獲得更多有向結(jié)構(gòu)信息去處理網(wǎng)絡(luò)稀疏性和冷啟動(dòng)問(wèn)題。具體地，首先采用隨機(jī)游走算法計(jì)算任意節(jié)點(diǎn)間的k步轉(zhuǎn)移概率矩陣去捕獲有向網(wǎng)絡(luò)全局結(jié)構(gòu)信息。此外，隨機(jī)游走算法的優(yōu)點(diǎn)是可捕獲有向網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)的信息及鄰居信息，從而有足夠網(wǎng)絡(luò)結(jié)構(gòu)信息彌補(bǔ)稀疏性和冷啟動(dòng)不足；再利用全局結(jié)構(gòu)信息來(lái)替代自包含協(xié)同過(guò)濾框架中的一階相似度，構(gòu)建高階自包含協(xié)同過(guò)濾（High-order Self-included Collaborative Filtering，HSCF）理論框架；再分別將三個(gè)有向局部相似度指標(biāo)，即有向共同鄰居（Directed Common Neighbor，DCN）、有 向Adamic-Adar（Directed Adamic-Adar，DAA）和有向資源分配（Directed Resource Allocation，DRA）和一個(gè)三階Bifan 指標(biāo)，與HSCF 框架相融合構(gòu)建4 個(gè)有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法，分別為：HSCF-DCN、HSCF-DAA、HSCF-DRA和HSCF-Bifan。為驗(yàn)證所提預(yù)測(cè)指標(biāo)性能，在10 個(gè)真實(shí)世界有向網(wǎng)絡(luò)上與基準(zhǔn)指標(biāo)進(jìn)行比較，結(jié)果表明所提指標(biāo)預(yù)測(cè)精度獲得顯著提升。

1 本文方法

1.1 問(wèn)題描述

給定一個(gè)有向無(wú)權(quán)網(wǎng)絡(luò)G(V，E)，其中V=是節(jié)點(diǎn)集和E表示鏈接集，每條邊e∈E表示一個(gè)有序?qū)=(νi，νj)，其中|V|是節(jié)點(diǎn)數(shù)，|E|是鏈接數(shù)。本文不允許多個(gè)鏈接和自循環(huán)存在。本文用X=[xij]N×N來(lái)表示G的鄰接矩陣，顯然xij≠xji。若G是有向無(wú)權(quán)網(wǎng)絡(luò)，如果節(jié)點(diǎn)νi→νj之間存在鏈接，則xij=1；否則xij=0。設(shè)表示任意節(jié)點(diǎn)i入度，則表示任意節(jié)點(diǎn)i出度以及Γout(i)和Γin(i)分別表示節(jié)點(diǎn)i的共同鄰居出度和入度。此外，本文用U=|V|(|V| -1) 2 表示任意有向網(wǎng)絡(luò)所有節(jié)點(diǎn)間的鏈接，顯然不存在鏈接集則為U-E。鏈路預(yù)測(cè)的目標(biāo)是從不存在集合U-E中查找缺失鏈接。為了驗(yàn)證算法性能，將觀測(cè)到的鏈路集E隨機(jī)分成訓(xùn)練集ET和測(cè)試集EP兩部分，前者是已知信息而后者僅用于測(cè)試，顯然，ET∩EP=?和ET∪EP=E。

1.2 高階轉(zhuǎn)移概率矩陣

大部分真實(shí)有向網(wǎng)絡(luò)具有稀疏性，僅考慮局部結(jié)構(gòu)是遠(yuǎn)遠(yuǎn)不夠的。本文啟用隨機(jī)游走算法［17］計(jì)算k步轉(zhuǎn)移概率矩陣來(lái)保持全局結(jié)構(gòu)。隨機(jī)游走方法［17］核心思想是從有向網(wǎng)絡(luò)任意節(jié)點(diǎn)出發(fā)經(jīng)過(guò)k步后到達(dá)另外一個(gè)節(jié)點(diǎn)概率。例如當(dāng)k=3 時(shí)可以計(jì)算出任意節(jié)點(diǎn)間三階路徑去保持節(jié)點(diǎn)鄰域信息。設(shè)任意有向網(wǎng)絡(luò)鄰接矩陣X，轉(zhuǎn)移矩陣為表示任意節(jié)點(diǎn)i隨機(jī)游走k到達(dá)節(jié)點(diǎn)j，k步轉(zhuǎn)移矩陣定義如下：

為減小算法時(shí)間復(fù)雜度，本文分別令k=3和k=4 可得到三階和四階轉(zhuǎn)移矩陣，分別如下：

為方便理解式（2），設(shè)任意8 個(gè)節(jié)點(diǎn)和13 條有向鏈接，采用隨機(jī)游走方法獲得三階轉(zhuǎn)移矩陣的過(guò)程。從圖1 可觀察到原始有向網(wǎng)絡(luò)中節(jié)點(diǎn)1 和8、節(jié)點(diǎn)1 和7、節(jié)點(diǎn)1 和6 不存在有向鏈接。啟用隨機(jī)游走方法計(jì)算三階轉(zhuǎn)移矩陣再還原初始有向網(wǎng)絡(luò)時(shí)，節(jié)點(diǎn)1 和8、節(jié)點(diǎn)1 和7、節(jié)點(diǎn)1 和6 均產(chǎn)生有向鏈接，具體原因是節(jié)點(diǎn)1→2→8、節(jié)點(diǎn)1→3→7 和節(jié)點(diǎn)1→3→6 存在著三階鏈接，因此，通過(guò)隨機(jī)游走算法均產(chǎn)生有向鏈接。而節(jié)點(diǎn)1 和5 沒(méi)有產(chǎn)生鏈接的原因是節(jié)點(diǎn)1 和5 間不存在三階連接關(guān)系。最后，通過(guò)三階轉(zhuǎn)移矩陣還原初始網(wǎng)絡(luò)可觀察到節(jié)點(diǎn)間存在著三階有向鏈接均產(chǎn)生鏈接，表明通過(guò)該方法可捕獲更多網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，提高預(yù)測(cè)有向鏈接準(zhǔn)確度。

1.3 高階自包含協(xié)同過(guò)濾預(yù)測(cè)框架

設(shè)任意無(wú)向無(wú)權(quán)網(wǎng)絡(luò)鄰接矩陣A∈Rn×n，自包含協(xié)同過(guò)濾（Self-included Collaborative Filtering，SCF）［16］理論框架定義如下：

其中：I是單位矩陣。

式（4）有以下兩個(gè)不足：1）該式僅適用于無(wú)向無(wú)權(quán)網(wǎng)絡(luò)，無(wú)法處理有向網(wǎng)絡(luò)鏈路預(yù)測(cè)問(wèn)題；2）該式直接啟用鄰接矩陣而無(wú)法捕獲更多網(wǎng)絡(luò)結(jié)構(gòu)信息。因此，本文將式（4）擴(kuò)展到有向網(wǎng)絡(luò)，只需將式（2）～（3）替換式（4）中初始鄰接矩陣A，重寫(xiě)式（4），有

其中：M3和M4分別是三階和四階相似度。

1.4 所提指標(biāo)

在式（5）的基礎(chǔ)上融合4 個(gè)經(jīng)典有向網(wǎng)絡(luò)鏈路預(yù)測(cè)指標(biāo)（DCN、DAA、DRA 和Bifan）分別構(gòu)成4 個(gè)不同半局部有向網(wǎng)絡(luò)鏈路預(yù)測(cè)指標(biāo)，以上指標(biāo)同時(shí)可保持有向網(wǎng)絡(luò)局部和全局網(wǎng)絡(luò)結(jié)構(gòu)信息。接下來(lái)介紹4 個(gè)經(jīng)典有向網(wǎng)絡(luò)鏈路預(yù)測(cè)指標(biāo)：

1）有向共同鄰居（DCN）指標(biāo)。將共同鄰居方法擴(kuò)展到有向網(wǎng)絡(luò)中，節(jié)點(diǎn)間共同鄰居越多相似的可能性就越高，定義如下：

2）有向Adamic-Adar（DAA）指 標(biāo)。擴(kuò) 展AA（Adamic-Adar）指標(biāo)到有向網(wǎng)，其核心是抑制共同鄰居中較大度的節(jié)點(diǎn)，定義如下：

3）有向資源分配（DRA）指標(biāo)。該指標(biāo)擴(kuò)展RA（Resource Allocation）到有向網(wǎng)，從資源分配角度出發(fā)，其核心思想是共同鄰居傳送資源數(shù)量與其出度成反比關(guān)系，定義如下：

4）勢(shì)能理論（Bifan）指標(biāo)。該指標(biāo)是基于勢(shì)能理論，聚類特性及同質(zhì)性假設(shè)，篩選出最優(yōu)模體Bifan，考慮節(jié)點(diǎn)三階路徑，定義如下：

將以上4 個(gè)指標(biāo)融入式（5）中，并用可調(diào)參數(shù)α∈[0.1，0.9]控制所提所有指標(biāo)三階和四階相似度在鏈路預(yù)測(cè)中所起的作用。所提4 個(gè)基于HSCF 鏈路預(yù)測(cè)指標(biāo)定義如下：

本文所提的4 個(gè)指標(biāo)具有平衡有向局部和全局結(jié)構(gòu)信息的作用，有利于探索更多網(wǎng)絡(luò)結(jié)構(gòu)信息提高預(yù)測(cè)精度。α用于平衡三階路徑和四階路徑所占比例：若α＞0.5 表明四階路徑信息比例高于三階路徑信息；若α＜0.5 表明三階路徑信息比例低于四階路徑信息。

本文所提HSCF-DCN、HSCF-DAA、HSCF-DRA 和HSCFBifan 指標(biāo)計(jì)算AUC和F-score的偽碼如下所示。

輸入 任意有向網(wǎng)絡(luò)G(V，E)，可調(diào)參數(shù)α。

輸出AUC和F-score。

步驟1 將任意有向網(wǎng)絡(luò)轉(zhuǎn)化為鄰接矩陣；

步驟2 按9∶1 的比例將原始網(wǎng)絡(luò)劃分為訓(xùn)練集和測(cè)試集；

步驟3在G中遍歷所有節(jié)點(diǎn)；

步驟4 根據(jù)式（4）計(jì)算高階相似度矩陣；

步驟5 式（2）～（3）和式（5）融合構(gòu)建高階自包含協(xié)同過(guò)濾框架；

步驟6 將式（6）～（9）替換式（5）中任意相似度S；

步驟7 式（10）～（13）是本文4 個(gè)指標(biāo)預(yù)測(cè)概率矩陣；

步驟8 計(jì)算平均AUC和F-score。

1.5 算法時(shí)間復(fù)雜度

所提4 個(gè)指標(biāo)耗時(shí)主要是集中使用隨機(jī)游走方法計(jì)算三階和四階轉(zhuǎn)移矩陣。如算法1 所示，所提指標(biāo)在步驟3～5耗時(shí)為O(Nl)，l是步長(zhǎng)。此外，在步驟7中，DCN、DAA、DRA和Bifan 耗時(shí)均為。因此，本文所提指標(biāo)的時(shí)間復(fù)雜度為大規(guī)模網(wǎng)絡(luò)和稀疏網(wǎng)絡(luò)中l(wèi)是有限長(zhǎng)度及?N，因此時(shí)間復(fù)雜度為O(n)。

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

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

本文使用受試者工作特征（Receiver Operating Characteristic，ROC）曲線下方面積AUC（Area Under Curve of ROC）［18］和F分?jǐn)?shù)（F-score）［19］兩個(gè)度量去衡量所有指標(biāo)性能。具體定義如下：

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ù)值相等，定義如下：

2）F-score度量是召回率（Recall）和精確率（Precision）綜合性度量，可更全面和有效評(píng)價(jià)算法性能，定義如下：

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

本文采用10 個(gè)真實(shí)世界有向網(wǎng)絡(luò)評(píng)價(jià)所有方法的性能，其拓?fù)浣Y(jié)構(gòu)特征統(tǒng)計(jì)在表1 中。其中，N=|V|是節(jié)點(diǎn)數(shù)，M=|E|是鏈接數(shù)，和分別表示節(jié)點(diǎn)最大入度和出度，平均度是網(wǎng)絡(luò)總邊數(shù)與節(jié)點(diǎn)數(shù)的比值，稀疏率表示有向網(wǎng)絡(luò)稀疏程度。10 個(gè)有向網(wǎng)絡(luò)的數(shù)據(jù)集介紹如下：

表1 10個(gè)真實(shí)世界有向網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征統(tǒng)計(jì)Tab.1 Topological feature statistics of 10 real directed networks

1）國(guó)際象棋網(wǎng)絡(luò)CHE（CHEss）［20］。該網(wǎng)絡(luò)是國(guó)際象棋比賽的結(jié)果，由7 301 節(jié)點(diǎn)和65 053 條鏈接構(gòu)成，節(jié)點(diǎn)表示一個(gè)棋手，有向邊表示一個(gè)游戲。

2）維基百科網(wǎng)絡(luò)WPL（Wiki Pedia Links）［20］。該網(wǎng)絡(luò)收集于低地撒克遜語(yǔ)維基百科，由10 453 節(jié)點(diǎn)和140 501 條鏈接構(gòu)成，節(jié)點(diǎn)表示維基百科文章，有向邊代表維基鏈接，即一個(gè)維基中的超鏈接。

3）搜索引擎網(wǎng)絡(luò)CAL（CALifornia）。該網(wǎng)絡(luò)通過(guò)hub/authority 算法去搜索引擎查詢“California”而構(gòu)建，由9 664 節(jié)點(diǎn)和16 150 條鏈接構(gòu)成。

4）信任網(wǎng)絡(luò)AG（AdvoGato）［21］。AG 是一個(gè)為自由軟件開(kāi)發(fā)者提供在線社區(qū)平臺(tái)的信任網(wǎng)絡(luò)，由6 541 節(jié)點(diǎn)和51 127 條鏈接構(gòu)成，節(jié)點(diǎn)表示用戶，有向邊表示節(jié)點(diǎn)間的信任關(guān)系。

5）論文引用網(wǎng)絡(luò)SM（SciMet）［22］。該網(wǎng)絡(luò)是關(guān)于網(wǎng)絡(luò)理論與實(shí)驗(yàn)引用網(wǎng)絡(luò)，它由3 084 個(gè)節(jié)點(diǎn)和10 412 條鏈接組成。

6）航空網(wǎng)絡(luò)OPE（OPEnflights）［20］。該網(wǎng)絡(luò)是世界各機(jī)場(chǎng)之間的航班數(shù)據(jù)集，節(jié)點(diǎn)表示機(jī)場(chǎng)，有向鏈接表示從一個(gè)機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)航班。

7）蛋白質(zhì)交互網(wǎng)絡(luò)FIG（FIGeys）［20］。該網(wǎng)絡(luò)是人類蛋白質(zhì)之間相互作用的網(wǎng)絡(luò)，節(jié)點(diǎn)表示蛋白質(zhì)，方向鏈接表示蛋白質(zhì)間交互關(guān)系。

8）圖書(shū)館與信息科學(xué)在線詞典ODL（ODLis）［22］。它是各類圖書(shū)館和信息專業(yè)超文本參考資源。

9）信任網(wǎng)絡(luò)BA（Bitcoin Alpha）［22］。它是在Bitcoin Alpha平臺(tái)上人與人信任關(guān)系，節(jié)點(diǎn)表示匿名用戶，方向鏈接表示匿名用戶間信任關(guān)系。

10）英語(yǔ)維基百科WV（Wiki Vote）［20］。該網(wǎng)絡(luò)收集于英語(yǔ)維基百科用戶網(wǎng)絡(luò)，在管理員選舉中相互投了贊成票和反對(duì)票，節(jié)點(diǎn)表示單個(gè)用戶，有向邊表示投票。

2.3 基準(zhǔn)指標(biāo)

為驗(yàn)證所提指標(biāo)性能，本文啟用12 個(gè)基準(zhǔn)指標(biāo)與之比較。12 個(gè)基準(zhǔn)指標(biāo)介紹如下：

1）基于有向局部相似度（DCN、DAA 和DRA）［8］和基于勢(shì)能理論Bifan，已在1.4 節(jié)作了詳細(xì)說(shuō)明。

2）線性最優(yōu)化（LO）［13］。該指標(biāo)假設(shè)兩個(gè)節(jié)點(diǎn)之間存在鏈接可能性可以通過(guò)相鄰節(jié)點(diǎn)線性求和來(lái)展開(kāi)。

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

3）大度節(jié)點(diǎn)有利指標(biāo)（Hub Promoted Index，HPI）［23］。該指標(biāo)表示代謝網(wǎng)絡(luò)中兩節(jié)點(diǎn)端點(diǎn)的相似程度。

4）Jaccard 指標(biāo)［23］。該指標(biāo)表示是兩個(gè)頂點(diǎn)共同鄰居數(shù)比上兩節(jié)點(diǎn)所有鄰居數(shù)之和，其定義如下：

5）局部路徑（Local Path，LP）指標(biāo)［23］。該指標(biāo)擴(kuò)展共同鄰居指標(biāo)，該指標(biāo)考慮三階路徑因素捕獲高階和二階路徑。

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

6）間接互惠感知加權(quán)（Indirect Reciprocity-aware Weighting，IRW）指標(biāo)與經(jīng)典有向網(wǎng)絡(luò)指標(biāo)（DCN、DAA、DRA和Bifan）構(gòu)建的新指標(biāo)，分別為IRW-DCN、IRW-DAA、IRWDRA 和IRW-Bifan。

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

本文實(shí)驗(yàn)硬件平臺(tái)為Intel Core i5-6500 CPU 臺(tái)式電腦，主頻3.20 GHz、內(nèi)存8 GB 和操作系統(tǒng)Windows 10，所有方法使用Matlab R2016b 實(shí)現(xiàn)。

本文通過(guò)4 個(gè)實(shí)驗(yàn)評(píng)估所提指標(biāo)性能：1）啟用AUC 和F-score度量全面評(píng)估基準(zhǔn)指標(biāo)和本文所提指標(biāo)性能；2）基準(zhǔn)指標(biāo)和本文所提指標(biāo)魯棒性對(duì)比；3）對(duì)可調(diào)參數(shù)敏感性分析；4）所提指標(biāo)在10 個(gè)真實(shí)有向網(wǎng)絡(luò)上運(yùn)行時(shí)間對(duì)比。

對(duì)于實(shí)驗(yàn)一，將原始有向網(wǎng)絡(luò)按9∶1 的比例隨機(jī)劃分為訓(xùn)練集和測(cè)試集，再使用AUC和F-score度量評(píng)估所有指標(biāo)性能，其實(shí)驗(yàn)結(jié)果記錄在表2～3中，并觀察到以下幾個(gè)現(xiàn)象：

1）所提指標(biāo)在所有有向網(wǎng)絡(luò)上表現(xiàn)出良好預(yù)測(cè)準(zhǔn)確度。由表2 可知，在絕大部分有向網(wǎng)絡(luò)上，本文4 個(gè)指標(biāo)均獲得最優(yōu)性能，且相較于基準(zhǔn)指標(biāo)，HSCF-DCN、HSCF-DAA、HSCFDRA 和HSCF-Bifan的AUC分別平均提高了8.16%、8.85%、9.64%和10.33%；由表3 可知，所提指標(biāo)在所有數(shù)據(jù)集上均獲得高質(zhì)量性能，且相較于基準(zhǔn)指標(biāo)，HSCF-DCN、HSCFDAA、HSCF-DRA 和HSCF-Bifan的F-score分別平均提高了66.62%、68.32%、68.95%和76.18%。以上表明捕獲更高階路徑信息有助于改善有向網(wǎng)絡(luò)預(yù)測(cè)精度。

2）表2中，與經(jīng)典有向局部相似度（DCN、DAA、DRA、Jaccard 和HPI）相比，所提指標(biāo)的預(yù)測(cè)精確有顯著提高。例如在數(shù)據(jù)集SM、OPE、CHE 和WPL中，所提最優(yōu)指標(biāo)HSCFDRA 與基準(zhǔn)最優(yōu)指標(biāo)DRA 相比，AUC分別提升了10.71%、2.47%、21.80%和6.77%。經(jīng)典方法獲得低質(zhì)量性能主要原因是它們考慮有向網(wǎng)絡(luò)局部結(jié)構(gòu)信息而敏感于稀疏性。此外，與半局部指標(biāo)LP 和Bifan 相比，所提指標(biāo)依然勝過(guò)LP和Bifan。例如在數(shù)據(jù)集BA 和ODL中，所提最優(yōu)指標(biāo)HSCFDRA 與基準(zhǔn)最優(yōu)指標(biāo)Bifan 相比，AUC分別提高了4.83%和1.37%。它們獲得低預(yù)測(cè)精度是由于LP 和Bifan 僅考慮節(jié)點(diǎn)三階路徑或節(jié)點(diǎn)鄰居的節(jié)點(diǎn)信息。與全局指標(biāo)LO 相比，所提指標(biāo)全面勝出，尤其在數(shù)據(jù)集CHE、BA、ODL 和CAL 中表現(xiàn)特別突出。例如在CAL，所提最優(yōu)指標(biāo)HSCF-Bifan 與LO相比，AUC提升了13.96%。表明全局指標(biāo)在稀疏網(wǎng)絡(luò)采集不到更多有用結(jié)構(gòu)信息，而所提指標(biāo)采用局部加全局更有利于捕獲更多網(wǎng)絡(luò)結(jié)構(gòu)信息。所提指標(biāo)與基于互惠感知加權(quán)機(jī)制指標(biāo)相比，所提指標(biāo)依然優(yōu)于它們，然而在WV 數(shù)據(jù)集，Bifan 性能最佳，表明該指標(biāo)可有效利用三階路徑信息。

表2 不同指標(biāo)下的AUC對(duì)比Tab.2 Comparison of AUC under difference indices

3）F-score是召回率和精確率加權(quán)平均調(diào)和，因此該度量更能全面評(píng)價(jià)算法性能。由于數(shù)據(jù)不平衡導(dǎo)致召回率和精確率相互矛盾，啟用F-score可更客觀評(píng)估所有指標(biāo)性能。由表3 可觀察到所提指標(biāo)在10 個(gè)數(shù)據(jù)集中都獲得高質(zhì)量性能。與經(jīng)典有向局部相似度（DCN、DAA、DRA、Jaccard 和HPI）相比，所提指標(biāo)有顯著提升。例如在數(shù)據(jù)集SM 和FIG，所提最優(yōu)指標(biāo)HSCF-Bifan 與基準(zhǔn)最優(yōu)指標(biāo)HPI 相比，F(xiàn)-score分別提升了14.12%和89.65%?；诨セ莞兄訖?quán)機(jī)制方法比較接近本文指標(biāo)性能，主要原因是前者方法采用權(quán)重機(jī)制捕獲更多互惠鏈接信息，尤其IRW-Bifan 最接近本文4 個(gè)指標(biāo)的主要原因是該指標(biāo)利用權(quán)重機(jī)制捕獲更多互惠鏈接及融合三階路徑信息，例如在數(shù)據(jù)集BA 和ODL；而半全局指標(biāo)LP和Bifan 獲得較低綜合性能主要原因是僅考慮三階路徑信息；全局指標(biāo)LO 比較接近本文所提指標(biāo)性能，是由于LO 采集網(wǎng)絡(luò)所有節(jié)點(diǎn)路徑，有穩(wěn)定預(yù)測(cè)精度。

表3 不同指標(biāo)下的F-score對(duì)比Tab.3 Comparison of F-score under difference indices

4）所提指標(biāo)通過(guò)啟用隨機(jī)游走方法捕獲節(jié)點(diǎn)三階和四階路徑信息，捕獲更多網(wǎng)絡(luò)結(jié)構(gòu)信息應(yīng)對(duì)冷啟動(dòng)以及稀疏性問(wèn)題。例如在數(shù)據(jù)集CAL中，稀疏率達(dá)到0.000 2，意味著網(wǎng)絡(luò)中存在大量的孤立節(jié)點(diǎn)，從實(shí)驗(yàn)結(jié)果來(lái)看，所提指標(biāo)HSCF-Bifan的AUC達(dá)到0.996，綜合指標(biāo)F-score也達(dá)到最優(yōu)，表明該指標(biāo)可有效處理冷啟動(dòng)以及稀疏性問(wèn)題。

實(shí)驗(yàn)二測(cè)試基準(zhǔn)指標(biāo)和本文所提指標(biāo)魯棒性，按一定比例隨機(jī)劃分原始網(wǎng)絡(luò)，設(shè)訓(xùn)練集比率為0.3、0.5 和0.7。當(dāng)訓(xùn)練集比率為0.3 時(shí)意味著測(cè)試集比率高達(dá)0.7，網(wǎng)絡(luò)處于極度稀疏狀態(tài)。實(shí)驗(yàn)結(jié)果記錄在表4～5，可觀察到以下兩個(gè)現(xiàn)象：

1）從表4 可觀察到所提4 個(gè)指標(biāo)在所有數(shù)據(jù)集上在不同訓(xùn)練下性能優(yōu)于基準(zhǔn)指標(biāo)，表明所提指標(biāo)具有良好的魯棒性。當(dāng)訓(xùn)練集比率從0.7 降至0.3，各個(gè)指標(biāo)的AUC也隨之下降。尤其在數(shù)據(jù)集SM、PB、CAL 和WV中，所提指標(biāo)在不同訓(xùn)練集下AUC波動(dòng)不明顯，其他指標(biāo)如LO 和LP 出現(xiàn)顯著的波動(dòng)，表明所提指標(biāo)在以上數(shù)據(jù)集捕獲更多網(wǎng)絡(luò)結(jié)構(gòu)信息來(lái)彌補(bǔ)稀疏性不足。此外，當(dāng)可訓(xùn)練集比率為0.7時(shí)，10 個(gè)有向網(wǎng)絡(luò)處于極度稀疏狀態(tài)，然而所提指標(biāo)依然最優(yōu)，尤其在數(shù)據(jù)集SM、PB、CAL 和WV中AUC和F-score保持不變，表明所提方法魯棒于稀疏網(wǎng)絡(luò)。

表4 不同訓(xùn)練集比率對(duì)應(yīng)的AUCTab.4 AUC corresponding to different training dataset rate

2）從表5 可觀察到所提指標(biāo)在所有數(shù)據(jù)集上性能明顯優(yōu)于基準(zhǔn)方法，表明所提指標(biāo)同時(shí)保持局部和全局信息捕獲更多網(wǎng)絡(luò)結(jié)構(gòu)信息彌補(bǔ)稀疏性?；诰植肯嗨贫龋―CN、DAA 和DRA）性能最差，當(dāng)可訓(xùn)練集比率增加時(shí)，F(xiàn)-score波動(dòng)顯著主要原因是無(wú)法捕獲更多局部結(jié)構(gòu)信息。LO 和IRW-Bifan 最接近本文指標(biāo)，兩個(gè)指標(biāo)本質(zhì)是考慮三階路徑信息可獲得更多網(wǎng)絡(luò)結(jié)構(gòu)信息。半局部指標(biāo)LP 表現(xiàn)并不理想，原因是可觀察鏈接減少時(shí)該指標(biāo)無(wú)法捕獲更多二階和三階路徑信息。

續(xù)表

實(shí)驗(yàn)三測(cè)試所提指標(biāo)的運(yùn)行時(shí)間，運(yùn)行10 次的實(shí)驗(yàn)結(jié)果記錄在圖2 中。圖2（a）是節(jié)點(diǎn)小于5 000 的有向網(wǎng)絡(luò)，所提4 個(gè)指標(biāo)耗時(shí)均小于250 s，表明所提指標(biāo)適用于小型網(wǎng)絡(luò)。圖2（b）是節(jié)點(diǎn)數(shù)大于5 000，其中WPL 是大規(guī)模網(wǎng)絡(luò)，HSCF-DRA 運(yùn)行時(shí)間僅略高于500 s，HSCF-DCN 和HSCFDAA 略高于1 000 s，HSCF-Bifan 指標(biāo)最為耗時(shí)。然而在CAL數(shù)據(jù)集中（節(jié)點(diǎn)數(shù)為9 664），本文指標(biāo)均小于500 s。綜上所述，所提指標(biāo)可適用于大中規(guī)模網(wǎng)絡(luò)。

最后，進(jìn)行可調(diào)參數(shù)敏感性分析。由于0.1 ≤α≤0.9，實(shí)驗(yàn)中設(shè)α為0.1、0.3、0.5、0.7 和0.9，其實(shí)驗(yàn)結(jié)果 見(jiàn)圖3～4。α的作用是平衡三階和四階路徑信息的貢獻(xiàn)。圖3是不同α所對(duì)應(yīng)的AUC，可觀察到在數(shù)據(jù)集SM、ODL、WPL、AG、CAL 和WV中，α=0.1時(shí)AUC最優(yōu)即算法性能最佳，隨著α增加，AUC隨著下降，表明所提指標(biāo)在α=0.1 時(shí)可捕獲更多網(wǎng)絡(luò)結(jié)構(gòu)信息。而在數(shù)據(jù)集BA中，當(dāng)α=0.5時(shí)AUC獲得最優(yōu)。在數(shù)據(jù)集FIG中，觀察到當(dāng)α=0.3時(shí)，HSCF-DCN、HSCFDAA 和HSCF-DRA 三個(gè)指標(biāo)AUC最優(yōu)；而當(dāng)α=0.1 時(shí)HSCFBifan 指標(biāo)的AUC 值最佳。

圖4 中不同α對(duì)應(yīng)F-score值，F(xiàn)-score是綜合全面評(píng)估度量。同理與AUC一致，當(dāng)α=0.1時(shí)，數(shù)據(jù)集SM、FIG、ODL、WPL、CHE、AG、CAL 和WV 對(duì)應(yīng)的F-score值最優(yōu)；α=0.5時(shí)，數(shù)據(jù)集OPE 對(duì)應(yīng)的F-score值最優(yōu)，表明所提指標(biāo)具有良好的穩(wěn)定性。在數(shù)據(jù)集BA中，觀察到當(dāng)α=0.3時(shí)，HSCF-DAA、HSCF-DRA 和HSCF-BifanHSCF-Bifan 的性能最優(yōu)；當(dāng)α=0.1時(shí)，HSCF-DCN 指標(biāo)F-score值最優(yōu)。

3 結(jié)語(yǔ)

大部分現(xiàn)存的鏈路預(yù)測(cè)方法僅關(guān)注無(wú)向無(wú)權(quán)網(wǎng)絡(luò)忽略有向網(wǎng)絡(luò)方向鏈接和有向結(jié)構(gòu)，難以同時(shí)保持有向網(wǎng)絡(luò)局部和全局結(jié)構(gòu)信息是個(gè)挑戰(zhàn)問(wèn)題，為此，本文提出高階自包含協(xié)同過(guò)濾鏈路預(yù)測(cè)指標(biāo)，該指標(biāo)可以在保持局部結(jié)構(gòu)信息基礎(chǔ)上捕獲更多全局結(jié)構(gòu)信息。首先啟用隨機(jī)游走方法計(jì)算高階相似度，再將三階和四階相似度矩陣融合協(xié)同過(guò)濾框架構(gòu)建高階自包含協(xié)同過(guò)濾預(yù)測(cè)框架，并將DCN、DAA、DRA和Bifan 四個(gè)指標(biāo)融合以上框架構(gòu)建有向網(wǎng)絡(luò)鏈路預(yù)測(cè)指標(biāo)。在10 個(gè)真實(shí)世界有向網(wǎng)絡(luò)上與基準(zhǔn)指標(biāo)比較，結(jié)果表明所提指標(biāo)性能優(yōu)于基準(zhǔn)指標(biāo)。

在將來(lái)工作中，嘗試將有向網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)融合本文框架中，有助于理解有向網(wǎng)絡(luò)的演化規(guī)律。此外，進(jìn)一步優(yōu)化該框架處理加權(quán)網(wǎng)絡(luò)鏈路預(yù)測(cè)問(wèn)題。