基于高階自包含協(xié)同過濾的有向網(wǎng)絡(luò)鏈路預(yù)測

陳廣福，王海波，連雁平

（1.武夷學院 數(shù)學與計算機學院，福建 武夷山 354300；2.認知計算與智能信息處理福建省高校重點實驗室（武夷學院），福建 武夷山 354300；3.湖南科技學院 信息工程學院，湖南 永州 425199）

0 引言

真實世界大量的復(fù)雜系統(tǒng)可使用復(fù)雜網(wǎng)絡(luò)來描述和表示。在復(fù)雜網(wǎng)絡(luò)中節(jié)點代表實體而鏈接表示實體間關(guān)系。然而，由于構(gòu)建真實復(fù)雜網(wǎng)絡(luò)時受復(fù)雜系統(tǒng)復(fù)雜性、噪聲及實驗條件等影響，所構(gòu)建復(fù)雜網(wǎng)絡(luò)容易出現(xiàn)缺失鏈接及冗余鏈接。因此，如何尋找缺失鏈接是復(fù)雜網(wǎng)絡(luò)研究最有挑戰(zhàn)的問題。鏈路預(yù)測目標是根據(jù)已知網(wǎng)絡(luò)結(jié)構(gòu)及其節(jié)點屬性等去推斷節(jié)點對形成鏈接的可能性［1］。此外，鏈路預(yù)測還具有以下兩個功能：1）它可以預(yù)測缺失鏈接包括無向、加權(quán)和方向鏈接以及識別虛假鏈接；2）根據(jù)當前網(wǎng)絡(luò)結(jié)構(gòu)信息去演繹網(wǎng)絡(luò)演化過程。因此，鏈路預(yù)測廣泛應(yīng)用于不同領(lǐng)域。例如在電子郵件系統(tǒng)，鏈路預(yù)測可阻止和過濾不相關(guān)及廣告郵件［2］；在社交網(wǎng)絡(luò)，鏈路預(yù)測啟用信任度量保護用戶隱私信息［3］；在生物網(wǎng)絡(luò)中，可用于預(yù)測蛋白質(zhì)間先前未知相互作用，從而顯著降低經(jīng)驗方法的成本等［4］。

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

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

1 本文方法

1.1 問題描述

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

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

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

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

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

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

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

其中：I是單位矩陣。

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

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

1.4 所提指標

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

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

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

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

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

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

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

本文所提HSCF-DCN、HSCF-DAA、HSCF-DRA 和HSCFBifan 指標計算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)練集和測試集；

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

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

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

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

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

步驟8 計算平均AUC和F-score。

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

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

2 實驗與結(jié)果分析

2.1 評價度量

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

1）AUC可以理解為在測試集EP中的鏈接分數(shù)大于隨機選擇一個不存在集U-E中鏈接分數(shù)概率。獨立比較n次，若有n1次測試集中鏈接的分數(shù)值大于不存在集中的鏈接分數(shù)，有n2次兩分數(shù)值相等，定義如下：

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

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

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

表1 10個真實世界有向網(wǎng)絡(luò)的拓撲結(jié)構(gòu)特征統(tǒng)計Tab.1 Topological feature statistics of 10 real directed networks

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

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

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

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

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

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

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

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

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

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

2.3 基準指標

為驗證所提指標性能，本文啟用12 個基準指標與之比較。12 個基準指標介紹如下：

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

2）線性最優(yōu)化（LO）［13］。該指標假設(shè)兩個節(jié)點之間存在鏈接可能性可以通過相鄰節(jié)點線性求和來展開。

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

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

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

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

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

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

2.4 實驗結(jié)果分析

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

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

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

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

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

表2 不同指標下的AUC對比Tab.2 Comparison of AUC under difference indices

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

表3 不同指標下的F-score對比Tab.3 Comparison of F-score under difference indices

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

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

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

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

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

續(xù)表

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

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

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

3 結(jié)語

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

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