摘 要：現(xiàn)存有向網(wǎng)絡(luò)鏈路預(yù)測方法僅考慮單類型網(wǎng)絡(luò)結(jié)構(gòu)而忽略一些關(guān)鍵網(wǎng)絡(luò)結(jié)構(gòu)，導(dǎo)致預(yù)測準(zhǔn)確度下降。針對此問題，提出一個(gè)融合多類型有向網(wǎng)絡(luò)結(jié)構(gòu)和非負(fù)矩陣分解的鏈路預(yù)測框架去保持局部和全局結(jié)構(gòu)信息。首先，將有向網(wǎng)絡(luò)的鄰接矩陣映射到低維潛在空間保持原始網(wǎng)絡(luò)的方向鏈接；其次，通過2-范數(shù)和規(guī)范化拉普拉斯融合四個(gè)關(guān)鍵有向結(jié)構(gòu)相似度包括有向共同鄰居（DCN）、有向Adamic-Adar（DAA）、有向資源分配（DRA）和勢理論（BF）去保持多類型網(wǎng)絡(luò)結(jié)構(gòu)信息，分別提出四個(gè)有向網(wǎng)絡(luò)的鏈路預(yù)測模型NMF-DNS-DCN、NMF-DNS-DAA、NMF-DNS-DRA和NMF-DNS-BF；最后，啟用乘法更新規(guī)則去學(xué)習(xí)四個(gè)模型參數(shù)并證明所提算法的收斂性。在八個(gè)真實(shí)世界有向網(wǎng)絡(luò)上與現(xiàn)存的代表性方法相比較，該模型的AUC、recall 和F1分別最大提高5.3%、7.8%和6%。

關(guān)鍵詞：鏈路預(yù)測；非負(fù)矩陣分解；有向網(wǎng)絡(luò)結(jié)構(gòu)；規(guī)范化拉普拉斯

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）07-033-2124-08

doi：10.19734/j.issn.1001-3695.2021.12.0656

基金項(xiàng)目：福建省自然科學(xué)基金資助項(xiàng)目（2021J011146，2021J011144）；武夷學(xué)院引進(jìn)人才科研啟動(dòng)基金資助項(xiàng)目（YJ202017）

作者簡介：陳廣福（1979-），男（通信作者），講師，博士，主要研究方向?yàn)殒溌奉A(yù)測和網(wǎng)絡(luò)表示等（cgf21st@163.com）；郭磊（1979-），男，副教授，碩士，主要研究方向?yàn)橥扑]系統(tǒng)；連雁平（1981-），男，副教授，碩士，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)和大數(shù)據(jù).

Link prediction combing nonnegative matrix factorization and directed structure

Chen Guangfu^1，2?，Guo Lei^1，2，Lian Yanping¹

（1.College of Mathematics amp; Computer Science，Wuyi University，Wuyishan Fujian 354399，China；2.Fujian Key Laboratory of Big Data Application amp; Intellectualization for Tea Industry，Wuyishan Fujian 354399，China）

Abstract：The existing link prediction methods for directed networks only consider single-type network structures but ignore some key network structures，which leads to the decrease of prediction accuracy.To solve this problem，this paper proposed a link prediction framework which combined multi-type directed network structure and non-negative matrix factorization to preserve local and global structure information.Firstly，it mapped the adjacency matrix of directed network to the low-dimensional latent space to preserve the directional link of the original network.Secondly，it fused four key directed structural similarities including DCN，DAA，DRA and potential theory （BF） by 2-norm and normalised Laplacian to maintain information on the structure of multi-type networks.Then，it proposed four link prediction models NMF-DNS-DCN，NMF-DNS-DAA，NMF-DNS-DRA and NMF-DNS-BF respectively.Finally，this paper enabled multiplicative update rules to learn the parameters of the four models and proved the convergence of the proposed algorithms.Compared with the existing representative methods on 8 real-world directed networks，the AUC，recall and F1 of the proposed model is increased by 5.3%，7.8% and 6%，respectively.

Key words：link prediction；non-negative matrix factorization；directed network structure；normalized Laplacian

0 引言

真實(shí)世界中大量的復(fù)雜系統(tǒng)可以通過復(fù)雜網(wǎng)絡(luò)來描述，網(wǎng)絡(luò)中節(jié)點(diǎn)表示實(shí)體，鏈接表示實(shí)體之間的交互。最近十年，復(fù)雜網(wǎng)絡(luò)得到各領(lǐng)域持續(xù)的關(guān)注，它的研究主要對象包括社區(qū)檢測^［1］ 、推薦系統(tǒng)^［2］和鏈路預(yù)測^［3］等，其中，鏈路預(yù)測是復(fù)雜網(wǎng)絡(luò)相關(guān)研究中最具有挑戰(zhàn)的一個(gè)問題。鏈路預(yù)測目標(biāo)是根據(jù)已知網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)屬性和聚類等信息去預(yù)測尚未連接節(jié)點(diǎn)間形成鏈接的可能性^［4］。因此，鏈路預(yù)測具有重大理論和應(yīng)用價(jià)值，其理論價(jià)值主要體現(xiàn)在根據(jù)當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)去推演將來網(wǎng)絡(luò)演化進(jìn)程。此外，鏈路預(yù)測廣泛應(yīng)用于不同領(lǐng)域。例如，在疾病—基因網(wǎng)絡(luò)中尋找兩個(gè)新基因或新疾病的關(guān)系，為診斷疾病提供新的技術(shù)^［5］；在蛋白質(zhì)—蛋白質(zhì)交互網(wǎng)絡(luò)中，可預(yù)測蛋白質(zhì)之間先前未知的相互作用關(guān)系，從而降低實(shí)驗(yàn)的成本^［6］；在軍事網(wǎng)絡(luò)中，可消除隨機(jī)噪聲和鑒定虛假鏈接的信息，可優(yōu)化軍事組織結(jié)構(gòu)，提高軍事決策的準(zhǔn)確性^［7］；在社交網(wǎng)絡(luò)中，可保護(hù)用戶隱私不受攻擊，激勵(lì)用戶提供更多可用的數(shù)據(jù)^［8］等。

當(dāng)前，現(xiàn)存無向無權(quán)的鏈路預(yù)測方法是將有向網(wǎng)絡(luò)看做無向網(wǎng)絡(luò)，忽略有向鏈接的貢獻(xiàn)，導(dǎo)致預(yù)測準(zhǔn)確度降低及得到不合理的預(yù)測結(jié)果。最近幾年，有向網(wǎng)絡(luò)的鏈路預(yù)測問題得到了廣泛關(guān)注。例如，柳娟等人^［9］基于貝葉斯模型和機(jī)器學(xué)習(xí)解決有向科學(xué)合作網(wǎng)絡(luò)缺失方向問題，并提出單模體和多模體的鏈路預(yù)測算法；Bütün等人^［10］提出基于有監(jiān)督的基模式的有向網(wǎng)絡(luò)鏈路預(yù)測算法；Zhang等人^［11］將無向局部相似度擴(kuò)展到有向網(wǎng)絡(luò)，提出有向局部指標(biāo)DCN（directed common neighbor）、DAA（directed Adamic-Adar）和DRA（directed resource allocation）。此外，李治成等人^［12］提出基于拓?fù)溆行нB通路徑的鏈路預(yù)測方法，該方法主要考慮不同路徑長度在節(jié)點(diǎn)度、半局部中心性和H-指數(shù)這三種不同衡量節(jié)點(diǎn)影響力指標(biāo)下對節(jié)點(diǎn)相似性的貢獻(xiàn)。以上方向僅考慮鏈接方向信息獲得局部結(jié)構(gòu)信息，無法處理稀疏有向網(wǎng)絡(luò)。另外，有向網(wǎng)絡(luò)中存在大量的互惠鏈接，研究表明互惠鏈接更容易使節(jié)點(diǎn)間形成連接。Shang等人^［13］提出節(jié)點(diǎn)的相動(dòng)態(tài)算法來分析鏈接方向的作用，結(jié)果表明互惠鏈接對鏈路預(yù)測和網(wǎng)絡(luò)結(jié)構(gòu)的形成具有更大的貢獻(xiàn)；Li等人^［14］使用零模型驗(yàn)證互惠鏈接在有向網(wǎng)絡(luò)作用，再將互惠鏈接作為附加信息提出間接互惠感知和直接互惠感知加權(quán)機(jī)制有向網(wǎng)絡(luò)鏈路預(yù)測指標(biāo)。上述方法在基于假設(shè)網(wǎng)絡(luò)是稠密且存在大量的互惠鏈接情況下可取得較高預(yù)測準(zhǔn)確度，然而真實(shí)網(wǎng)絡(luò)大部分都是稀疏的。為克服以上不足，一些考慮網(wǎng)絡(luò)三階路徑方法被提出。Pech等人^［15］提出線性最優(yōu)化（linear optimization，LO）方法，該方法將節(jié)點(diǎn)的鄰居用線性和表示獲得網(wǎng)絡(luò)高階路徑信息去保持網(wǎng)絡(luò)全局結(jié)構(gòu)信息；李勁松等人^［16］在文獻(xiàn)［15］基礎(chǔ)上提出線性規(guī)劃方法，與LO有相似作用；Zhang等人^［17］提出基于勢理論的最佳模體Bi-Fan（BF）算法，該方法考慮節(jié)點(diǎn)鄰居的三階路徑信息。

最近，非負(fù)矩陣分解技術(shù)具有減維以及較高預(yù)測準(zhǔn)確度等特性廣泛應(yīng)用于鏈路預(yù)測，該方法主要思想是將網(wǎng)絡(luò)鄰接矩陣分解為兩個(gè)低秩因子矩陣再附加一些重要信息，如拓?fù)浣Y(jié)構(gòu)及聚類信息等，然后重構(gòu)網(wǎng)絡(luò)獲得預(yù)測分?jǐn)?shù)矩陣。代表性算法包括擾動(dòng)方法^［18］、稀疏學(xué)習(xí)^［19］和圖可達(dá)性^［20］等。然而，基于非負(fù)矩陣分解方法鏈路預(yù)測存在以下兩方面不足：a）大部分現(xiàn)存方法僅考慮無向無權(quán)網(wǎng)絡(luò)；b）非負(fù)矩陣分解融合圖正則化方法去保持網(wǎng)絡(luò)結(jié)構(gòu)信息，然而該方法不能更全面地衡量整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)差異。針對第一個(gè)不足，有少量現(xiàn)存文獻(xiàn)將非負(fù)矩陣分解擴(kuò)展到有向網(wǎng)絡(luò)鏈路預(yù)測中。例如，Chen等人^［21］融合不對稱聚類信息與非負(fù)矩陣分解相融合去保持網(wǎng)絡(luò)結(jié)構(gòu)信息，然而，該方法僅考慮單類型網(wǎng)絡(luò)結(jié)構(gòu)信息。此外，基于流形假設(shè)的前提下非負(fù)矩陣分解融合圖正則化方法才可保持局部結(jié)構(gòu)信息^［22］，但無法利用更多類型結(jié)構(gòu)信息。因此，圖正則化方法不適用于捕獲全局結(jié)構(gòu)信息。

基于上述分析，本文將解決以下兩個(gè)問題：a）非負(fù)矩陣分解模型如何融合一些重要的有向網(wǎng)絡(luò)結(jié)構(gòu)信息；b）如何使用2-范數(shù)和拉普拉斯相結(jié)合去保持網(wǎng)絡(luò)的一些重要的結(jié)構(gòu)信息。為解決以上兩個(gè)問題，本文提出融合有向網(wǎng)絡(luò)結(jié)構(gòu)和非負(fù)矩陣分解的有向網(wǎng)絡(luò)鏈路預(yù)測框架（nonnegative matrix factorization via directed network structure，NMF-DNS）。首先，將有向網(wǎng)絡(luò)的鄰接矩陣映射到低維潛在空間；其次，2-范數(shù)和規(guī)范化拉普拉斯將相結(jié)合融合一些重要的有向結(jié)構(gòu)相似度（DCN，DAA，DRA和BF）去保持多類型結(jié)構(gòu)信息；最后，提出本文四個(gè)有向網(wǎng)絡(luò)的鏈路預(yù)測模型NMF-DNS-DCN、NMF-DNS-DAA、NMF-DNS-DRA和NMF-DNS-BF。

本文的貢獻(xiàn)總結(jié)如下：

a）提出四個(gè)融合有向網(wǎng)絡(luò)結(jié)構(gòu)與非負(fù)矩陣分解的鏈路預(yù)測模型，該類模型可同時(shí)保持一階、二階和高階路徑信息；

b）啟用2-范數(shù)衡量整個(gè)網(wǎng)絡(luò)總分歧程度并結(jié)合規(guī)范化拉普拉斯去保持網(wǎng)絡(luò)結(jié)構(gòu)信息；

c）在8個(gè)真實(shí)世界有向網(wǎng)絡(luò)上與現(xiàn)存代表性方法比較，結(jié)果表明本文所提四個(gè)模型顯著優(yōu)于基準(zhǔn)方法。

1 本文方法

1.1 相關(guān)概念

考慮一個(gè)無向網(wǎng)絡(luò)G（V，E），其中V={vi}Ni=1是節(jié)點(diǎn)集合，E表示鏈接集。本文不允許多個(gè)鏈接和自循環(huán)存在。本文用A=［aij］n×n來表示G的鄰接矩陣，若G是有向無權(quán)網(wǎng)絡(luò)，且節(jié)點(diǎn)vi→vj之間存在鏈接，則aij=1，否則aij=0。顯然，A是不對稱矩陣，即aij≠aji。

接下來進(jìn)一步表示所有可能的|V|（|V|-1）2鏈接為U，并且U-E是不存在的鏈接集。鏈路預(yù)測的目標(biāo)是從集合U-E中查找缺失鏈接。為了驗(yàn)證算法的性能，將觀測到的鏈接集隨機(jī)分成訓(xùn)練集ET和測試集EP兩部分，前者是已知的信息，后者僅用于測試。顯然，ET∩EP=?和ET∪EP=E。 接下來介紹一些基本的矩陣運(yùn)算定義：運(yùn)算符〈·〉表示內(nèi)積，‖·‖2表示2-范數(shù)，AT表示矩陣A的轉(zhuǎn)置，Tr（A）表示矩陣A的跡，‖A‖F(xiàn)表示Frobenius 范數(shù)，I表示單位矩陣。

1.2 融合有向結(jié)構(gòu)信息

非負(fù)矩陣分解具有維數(shù)約減及預(yù)測準(zhǔn)確性好等特點(diǎn)，廣泛應(yīng)用于鏈路預(yù)測。本文利用非負(fù)矩陣分解技術(shù)去捕獲網(wǎng)絡(luò)的鏈接、鏈接權(quán)重以及鏈接方向等信息。非負(fù)矩陣分解（nonne-gative matrix factorization，NMF）^［23］目標(biāo)是尋找兩個(gè)低秩的非負(fù)因子矩陣去近似原始網(wǎng)絡(luò)。因此，NMF分解目的是解決以下F-范數(shù)優(yōu)化問題：

網(wǎng)絡(luò)結(jié)構(gòu)是網(wǎng)絡(luò)重要組成部分，為鏈路預(yù)測提供最原始節(jié)點(diǎn)和鏈接信息。然而，非負(fù)矩陣分解技術(shù)最大的瓶頸是無法保持網(wǎng)絡(luò)結(jié)構(gòu)信息。盡管圖正則化方法可捕獲網(wǎng)絡(luò)局部結(jié)構(gòu)，但無法衡量整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)間總分歧。因此，本文啟用2-范數(shù)與規(guī)范化拉普拉斯相結(jié)合去保持有向網(wǎng)絡(luò)結(jié)構(gòu)信息，增強(qiáng)所提模型預(yù)測準(zhǔn)確度。真實(shí)世界網(wǎng)絡(luò)中，兩個(gè)節(jié)點(diǎn)具有類似的屬性或結(jié)構(gòu)，那么該類節(jié)點(diǎn)就容易形成鏈接。以圖1為例，節(jié)點(diǎn)x和y共享節(jié)點(diǎn)a和b，與它們具有相同結(jié)構(gòu)或?qū)傩裕虼?，?jié)點(diǎn)x和y產(chǎn)生鏈接的可能性就大。假設(shè)節(jié)點(diǎn)vi與vj要相似，那么就盡可能距離近，節(jié)點(diǎn)vi與vj間最短距離表示如下：

現(xiàn)存典型的有向網(wǎng)絡(luò)結(jié)構(gòu)相似度算法有DCN、DAA、DRA和BF四個(gè)，其中，前三個(gè)考慮二階路徑信息而BF是基于三階路徑方法，具體的描述如表1所示。為使節(jié)點(diǎn)間更容易產(chǎn)生鏈接，在式（2）中融合表1中的四個(gè)有向網(wǎng)絡(luò)結(jié)構(gòu)相似度，其定義如下：

其中：Sij可由S^DCN、S^DAA、S^DRA和S^BF替換。式（2）反映了Sij越大，那么節(jié)點(diǎn)vi與vj產(chǎn)生鏈接可能性越大。

為衡量整個(gè)網(wǎng)絡(luò)上所有節(jié)點(diǎn)對相似度，將式（3）擴(kuò)展到整個(gè)網(wǎng)絡(luò)中。因此，得到整個(gè)網(wǎng)絡(luò)的總分歧程度為

其中：di和dj是A的第i行和第j行的總和。

由于式（4）中存在2-范數(shù)，對式（3）最小優(yōu)化是非常困難的。又由于2-范數(shù)計(jì)算核心是取矩陣共軛轉(zhuǎn)置與矩陣乘積的最大特征值作為解，所以本文啟用歸一化拉普拉斯將式（4）轉(zhuǎn)換為求矩陣跡的最大值，定義如下：

1.3 統(tǒng)一鏈路預(yù)測模型

式（1）的作用是將鄰接矩陣A映射到低維空間中保持原始網(wǎng)絡(luò)的方向鏈接信息，而式（4）的功能是利用2-范數(shù)和拉普拉斯保持有向多類型結(jié)構(gòu)信息。式（4）是最大化而所提模型是最小化求解目標(biāo)函數(shù)，因此需要將式（4）轉(zhuǎn)換為最小化只需在式（4）中添加負(fù)號(hào)即可，其所提四個(gè)模型的目標(biāo)函數(shù)如下：

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

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

為了驗(yàn)證所提出算法的性能，本文使用AUC、recall和F1作為度量評(píng)價(jià)所有方法性能。

a）AUC^［24］（area under the receiver operating characteristic curve），可以理解為在測試集Ep中的鏈接分?jǐn)?shù)大于隨機(jī)選擇的一個(gè)不存在集U-E中的鏈接分?jǐn)?shù)的概率。獨(dú)立地比較n次，若有n1 次測試集中鏈接的分?jǐn)?shù)值大于不存在集中鏈接的分?jǐn)?shù)，有n2次兩分?jǐn)?shù)值相等，AUC定義如下：

b）召回率（recall）^［25］定義為所有鏈接M中m個(gè)現(xiàn)存鏈接的比率，即

c）F1度量^［25］是召回率和準(zhǔn)確率的綜合性度量，可更全面和有效地評(píng)價(jià)算法性能，其定義如下：

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

本文使用八個(gè)真實(shí)世界有向網(wǎng)絡(luò)來評(píng)價(jià)所有方法性能，其拓?fù)浣Y(jié)構(gòu)特征統(tǒng)計(jì)如表2所示。

其中：|V|是節(jié)點(diǎn)數(shù)，|E|是鏈接數(shù)，〈k〉表示平均度，〈d〉表示平均最短距離，kⁱⁿmax和k^outmax分別表示節(jié)點(diǎn)最大入度和出度。八個(gè)有向網(wǎng)絡(luò)的數(shù)據(jù)集介紹如下：

a）朋友網(wǎng)絡(luò)（HAMster，HAM）^［26］，該網(wǎng)絡(luò)是由1 858個(gè)節(jié)點(diǎn)和12 534條鏈接構(gòu)成。

b）論文引用網(wǎng)絡(luò)（SMAgri，SMA）^［27］是關(guān)于網(wǎng)絡(luò)理論與實(shí)驗(yàn)的引用網(wǎng)絡(luò)，它由1 024個(gè)節(jié)點(diǎn)和4 916條鏈接組成。鏈接方向表示引用關(guān)系。

c）論文引用網(wǎng)絡(luò)（KOHene，KOH）^［27］是有關(guān)“自組織映射”主題的論文引用網(wǎng)絡(luò)。

d）維基百科（WikiTalk，WT）^［26］，該網(wǎng)絡(luò)是歐西坦語維基百科的通信網(wǎng)絡(luò)。節(jié)點(diǎn)表示用戶，從用戶A到B的一條邊表示用戶A在某個(gè)時(shí)間戳在用戶B的對話頁面上寫了一條消息。

e）EPA^［26］，該網(wǎng)絡(luò)是搜索引擎查詢數(shù)據(jù)集，它由4 771個(gè)節(jié)點(diǎn)和8 940條鏈接組成。

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

g）圖書館與信息科學(xué)在線詞典（ODLIS，ODL）^［26］是各類圖書館和信息專業(yè)的超文本參考資源。

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

2.3 基準(zhǔn)方法

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

a）3個(gè)基于有向局部相似度（DCN、DAA、DRA）^［11］和基于勢能理論的最佳模體（BF）方法^［17］。

b）線性最優(yōu)化（linear optimization，LO）^［15］，該指標(biāo)假設(shè)兩個(gè)節(jié)點(diǎn)之間存在鏈接的可能性可以通過相鄰節(jié)點(diǎn)貢獻(xiàn)的線性求和來展開。

c）大度節(jié)點(diǎn)有利指標(biāo)（hub promoted index，HPI）^［11］，該指標(biāo)表示代謝網(wǎng)絡(luò)中兩節(jié)點(diǎn)端點(diǎn)的相似程度，其定義如下：

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

e）間接互惠感知加權(quán)指標(biāo)（indirect reciprocity-aware weighting，IRW）與有向網(wǎng)絡(luò)DCN、DAA和DRA構(gòu)建新的指標(biāo)，其定義如下^［14］：

g）有向網(wǎng)絡(luò)線性規(guī)劃（linear programming index for directed network，LPD）指標(biāo)^［16］，該方法考慮三種有向鄰居的信息貢獻(xiàn)并結(jié)合結(jié)構(gòu)特點(diǎn)建立線性規(guī)劃模型，進(jìn)而通過求解貢獻(xiàn)矩陣的最優(yōu)解構(gòu)建相似性指標(biāo)。

S^LPD=R（RTR+λ·I）^-1RTA

其中：R=A+αAT。

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è)模型均含4個(gè)重要的參數(shù)，分別為α、β、潛在空間維數(shù)K和迭代次數(shù)maxiter。為公平比較所有的方法，在8個(gè)數(shù)據(jù)集上統(tǒng)一設(shè)置：α=0.5、β=5、K=70和maxiter=70。此外，LO指標(biāo)可調(diào)參數(shù)α=0.1；LPD指標(biāo)可調(diào)參數(shù)α=0.1及λ=1 和FPMF-CN方法默認(rèn)原文設(shè)置。

本文從以下四個(gè)方面測試所提4個(gè)模型性能：首先，啟用AUC、recall和F1三個(gè)度量評(píng)估所有16個(gè)方法性能；其次，測試所提模型考慮方向鏈接后性能是否獲得顯著改善；另外，測試所提模型融合多類型有向后是否改善性能；最后，測試所有16個(gè)方法的魯棒性。

第一個(gè)實(shí)驗(yàn)利用AUC、recall和F1評(píng)價(jià)4個(gè)所提模型及12個(gè)基準(zhǔn)指標(biāo)性能，其實(shí)驗(yàn)結(jié)果如表3所示。

根據(jù)表3可以觀察到以下四個(gè)現(xiàn)象：

a）AUC度量，所提4個(gè)模型在7個(gè)（除SOC）數(shù)據(jù)集中獲得優(yōu)秀性能，recall和F1度量，所提模型在8個(gè)數(shù)據(jù)集均獲得最優(yōu)性能，表明所提4個(gè)模型通過2-范數(shù)和規(guī)范化拉普拉斯相結(jié)合可有效保持及充分利用網(wǎng)絡(luò)結(jié)構(gòu)信息。所提模型在SOC數(shù)據(jù)集獲得低質(zhì)量的原因是從表1觀察到SOC的平均最短距離為3.138 2，由于所提模型啟用2-范數(shù)衡量節(jié)點(diǎn)間產(chǎn)生鏈接的可能性，所以節(jié)點(diǎn)間距離直接影響是否充分保持網(wǎng)絡(luò)結(jié)構(gòu)信息。此外，表2可觀察到節(jié)點(diǎn)平均最短距離較短，如EPA，均獲得優(yōu)異預(yù)測準(zhǔn)確度。

b）DCN、DAA、DRA和BF是有向網(wǎng)絡(luò)4個(gè)基準(zhǔn)指標(biāo)，DCN、DAA、DRA獲得較差預(yù)測準(zhǔn)確度的原因是三個(gè)指標(biāo)僅考慮節(jié)點(diǎn)共同鄰居數(shù)量保持局部結(jié)構(gòu)信息，而BF指標(biāo)與以上三個(gè)指標(biāo)相比預(yù)測精度顯著提升，主要原因是該方法考慮三階路徑信息。所提4個(gè)方法融合以上四類結(jié)構(gòu)同時(shí)保持原始網(wǎng)絡(luò)方向鏈接信息獲得顯著改善。例如，在EPA數(shù)據(jù)集中，所提模型最優(yōu)性能與DCN、DAA、DRA和BF相比AUC值分別提高了18.1%、18.6%、19.2%和12%。在recall和F1度量，所提模型與DCN、DAA、DRA和BF相比較有顯著提升，例如ODL數(shù)據(jù)中recall最大提高了50.2%。此外，Jaccard和HPI僅考慮節(jié)點(diǎn)鄰居數(shù)，同樣獲得了低質(zhì)量性能。

c）基于感知加權(quán)機(jī)制的三個(gè)指標(biāo)考慮有向網(wǎng)絡(luò)的互惠鏈接信息作為權(quán)重平衡方向鏈接和局部結(jié)構(gòu)信息。該類方法與DCN、DAA、DRA三種方法比較，性能明顯得到改進(jìn)，表明互惠鏈接有助于改善預(yù)測精度，與所提模型比較，后者預(yù)測準(zhǔn)確度更高。例如在FIG數(shù)據(jù)集中，所提方法最優(yōu)性能與DCN、DAA、DRA相比，AUC值分別提高了28.1%、26.9%和26%。同理在recall和F1度量也獲得了顯著改善。

d）LO和LPD兩個(gè)指標(biāo)具有類似的機(jī)制，LO是通過分解節(jié)點(diǎn)鄰居信息去保持全局節(jié)點(diǎn)路徑。同理LPD采用線性規(guī)劃方法去保持網(wǎng)絡(luò)全局結(jié)構(gòu)，兩者都屬于全局指標(biāo)。然而，兩者在所有數(shù)據(jù)集均獲得較低預(yù)測準(zhǔn)確度。PFMF-CN與所提模型同樣機(jī)制，采用分解鄰接矩陣到低維潛在空間再融合局部結(jié)構(gòu)信息。該方法性能與所提模型比較接近，然而該指標(biāo)僅考慮共同鄰居方法，無法充分開采網(wǎng)絡(luò)結(jié)構(gòu)全局信息。

第二個(gè)實(shí)驗(yàn)主要評(píng)估考慮方向鏈接后所提模型是否可改善預(yù)測準(zhǔn)確度。本實(shí)驗(yàn)啟用三個(gè)所提方法NMF-DNS-DCN、NMF-DNS-DAA和NMF-DNS-DRA融合有向結(jié)構(gòu)，而NMF-DNS-CN、NMF-DNS-AA和NMF-DNS-RA融合無向結(jié)構(gòu)信息，其實(shí)驗(yàn)結(jié)果如表4所示。從表4可以看出，在AUC和F1度量下，考慮有向結(jié)構(gòu)信息預(yù)測準(zhǔn)確度有顯著提高。例如，NMF-DNS-DCN與NMF-DNS-CN在所有的數(shù)據(jù)集上相比，AUC的值分別提高了5.2%、 3.1%、1.4%、0.2%、 3.8% 、7%、3.5%和2.2%，同理F1值分別提高了30.5%、32.9%、64.5%、34.4%、31.6%、31%、25.8%和36.3%，其余兩個(gè)指標(biāo)同樣有顯著改善。因此，考慮方向鏈接信息有顯著提升。

第三個(gè)實(shí)驗(yàn)評(píng)估基礎(chǔ)NMF融合有向結(jié)構(gòu)是否可以改善性能，其結(jié)果如表5所示。當(dāng)α=0和β=0時(shí)，本文所提模型退化為基礎(chǔ)NM模型；當(dāng)α≠0和β≠0，表示融合有向結(jié)構(gòu)信息的模型。表5可觀察到NMF的AUC、recall和F1值明顯低于融合有向結(jié)構(gòu)的4個(gè)模型。具體地，基礎(chǔ)NMF與NMF-DNS-DCN相比較，AUC值在數(shù)據(jù)集KON、HAM、ODL、SOC、EPA、SMA、FIG和WT上分別提高1.8%、1.1%、3.6%、2.2%、1.6%、3.8%、1.4%和0.6%；recall值在數(shù)據(jù)集KON、HAM、ODL、SOC、EPA、SMA、FIG和WT上分別提高10.7%、9%、10%、8.4%、3.6%、8.2%、10.1%和2.5%；F1值在數(shù)據(jù)集KON、HAM、ODL、SOC、EPA、SMA、FIG和WT上分別提高9.3%、6.3%、7.1%、6.6%、2.9%、6.7%、9.9%和1.1%。同理，NMF-DNS-DAA、NMF-DNS-DRA和NMF-DNS-BF性能優(yōu)于NMF。通過上述分析，表明在基礎(chǔ)NMF上融合有向結(jié)構(gòu)信息可以明顯改善性能。

最后一個(gè)實(shí)驗(yàn)測試所有方法的魯棒性。通過不同比率訓(xùn)練集改變初始網(wǎng)絡(luò)稀疏性，本實(shí)驗(yàn)設(shè)訓(xùn)練集大小為30%和70%，實(shí)驗(yàn)結(jié)果如圖2所示。

a）在不同比率下所提4個(gè)方法的AUC值都顯著優(yōu)于其他基準(zhǔn)算法，除了SOC數(shù)據(jù)集。此外，所提4個(gè)模型在不同比率下AUC值波動(dòng)并不顯著，而基于局部相似度的DCN、DAA和DRA出現(xiàn)明顯波動(dòng)，主要原因是可觀察的方向鏈接減少而無法獲得足夠的網(wǎng)絡(luò)結(jié)構(gòu)信息。

b） 當(dāng)訓(xùn)練集在30%時(shí)，網(wǎng)絡(luò)處于高度稀疏狀態(tài)。所提4個(gè)模型依然獲得較高的預(yù)測準(zhǔn)確度，表明所提4個(gè)方法魯棒于稀疏網(wǎng)絡(luò)。

3 參數(shù)敏感性

本章討論所提方法主要參數(shù)對性能的影響。所提模型包含4個(gè)重要參數(shù)，分別為α、β、潛在空間K和迭代次數(shù)。設(shè)α變化為{5×10^-3，5×10^-2，5×10^-1，5×10⁰，5×10¹，5×10²}，潛在空間K的變化為{10，20，30，…，100}，迭代次數(shù)變化為{10，20，30，…，100}和β變化為{5×10^-2，5×10^-1，5×10⁰，5×10¹，25×10²}。本文研究一個(gè)參數(shù)對性能影響，需固定其他三個(gè)參數(shù)，由于空間有限，僅對AUC度量進(jìn)行分析。

3.1 參數(shù)α對性能影響

參數(shù)α的作用是控制不同類型的結(jié)構(gòu)信息的貢獻(xiàn)，其實(shí)驗(yàn)結(jié)果如圖3所示。當(dāng)αlt;0.05時(shí)，AUC值逐漸下降，表明α增大時(shí)目標(biāo)損失函數(shù)誤差增加，導(dǎo)致鏈路預(yù)測準(zhǔn)確度下降；當(dāng)α≥0.05時(shí)，所提4個(gè)模型的AUC值達(dá)到最優(yōu)且保持穩(wěn)定。因此，當(dāng)α=0.05時(shí)，性能最佳。

3.2 參數(shù)β對性能影響

參數(shù)β是防止正則項(xiàng)過度擬合，其實(shí)驗(yàn)結(jié)果如圖4所示。當(dāng)βlt;5時(shí)，AUC值開始快速下降，表明β不宜過大；當(dāng)βgt;5時(shí)，AUC略有下降，表明β不宜過??；當(dāng)β=5時(shí)，性能最優(yōu)。

3.3 參數(shù)K對性能影響

參數(shù)K是平衡預(yù)測準(zhǔn)確度與時(shí)間復(fù)雜度。若K值過小，低維潛在空間無法獲得足夠網(wǎng)絡(luò)結(jié)構(gòu)信息導(dǎo)致預(yù)測準(zhǔn)確度下降；若K值過大，會(huì)增加所提方法的時(shí)間復(fù)雜度。因此，設(shè)參數(shù)K值為10～100，其實(shí)驗(yàn)如圖5所示。當(dāng)K值小于30時(shí)在所有網(wǎng)絡(luò)中均獲得低質(zhì)量性能，當(dāng)K值開始逐漸增加且到70時(shí)，AUC值也逐漸增大且達(dá)到穩(wěn)定。因此，K=70時(shí)，AUC值達(dá)到最優(yōu)。

3.4 迭代次數(shù)對性能影響

迭代次數(shù)大小直接影響所提算法的收斂性快慢，其實(shí)驗(yàn)結(jié)果如圖6所示。當(dāng)?shù)螖?shù)為10時(shí)，所提方法在所有數(shù)據(jù)集上AUC值最小。當(dāng)?shù)螖?shù)開始逐漸增加，AUC的值也開始增大然后達(dá)到穩(wěn)定。當(dāng)?shù)螖?shù)達(dá)到50時(shí)，AUC的曲線略有波動(dòng)，但波動(dòng)值相差甚微。當(dāng)?shù)螖?shù)大于等于70時(shí)，所提4個(gè)模型在所有數(shù)據(jù)集上AUC值保持恒定。

4 結(jié)束語

大部分現(xiàn)存的有向網(wǎng)絡(luò)鏈路預(yù)測僅考慮單類型網(wǎng)絡(luò)結(jié)構(gòu)，如何在非負(fù)矩陣分解的框架下融合多種類型結(jié)構(gòu)信息的挑戰(zhàn)，本文提出一種新穎的融合有向結(jié)構(gòu)和非負(fù)矩陣分解的有向網(wǎng)絡(luò)的鏈路預(yù)測模型。首先，將任意有向網(wǎng)絡(luò)鄰接矩陣映射到低維潛在空間；其次通過2-范數(shù)融合有向網(wǎng)絡(luò)4個(gè)結(jié)構(gòu)信息（DCN、DAA、DRA和BF）提出4個(gè)預(yù)測模型；最后，通過更新規(guī)則學(xué)習(xí)模型參數(shù)獲得最優(yōu)局部解。在8個(gè)有向網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，4個(gè)所提模型在預(yù)測方向鏈接及魯棒性上顯著優(yōu)于基準(zhǔn)方法。

在將來的工作中，對所提模型考慮有向社區(qū)結(jié)構(gòu)及節(jié)點(diǎn)屬性等信息。

參考文獻(xiàn)：

［1］Li Ye，Sha Chaofeng，Huang Xin，et al.Community detection in attri-buted graphs：an embedding approach［C］//Proc of the 32nd AAAI Conference on Artificial Intelligence.2018：338-345.

［2］Aghdam M H，Analoui M，Kabiri P.A novel non-negative matrix factorization method for recommender systems［J］.Applied Mathema-tics amp; Information Sciences，2015，9（5）：2721.

［3］Lyu Linyuan，Jin Cihang，Zhou Tao.Similarity index based on local paths for link prediction of complex networks［J］.Physical Review E，2009，80（4）：046122.

［4］Lyu Linyuan，Zhou Tao.Link prediction in complex networks：a survey［J］.Physica A：Statistical Mechanics and Its Applications，2011，390（6）：1150-1170.

［5］Dong Yuxiao，Zhang Jing，Tang Jie，et al.CoupledLP：link prediction in coupled networks［C］//Proc of the 21st ACM SIGKDD Internatio-nal Conference on Knowledge Discovery and Data Mining.2015：199-208.

［6］Cannistraci C V，Alanis-Lobato G，Ravasi T.From link-prediction in brain con-nectomes and protein interactomes to the local-community-paradigm in complex networks［J］.Scientific Reports，2013，3：1613.

［7］Fan Changjun，Liu Zhong，Lu Xin，et al.An efficient link prediction index for complex military organization［J］.Physica A：Statistical Mechanics and Its Applications，2017，469：572-587.

［8］Yu Shanqing，Zhao Minghao，F(xiàn)u Chenbo，et al.Target defense against link-prediction-based attacks via evolutionary perturbations［J］.IEEE Trans on Knowledge and Data Engineering，2021，33（2）：754-767.

［9］柳娟，劉亞芳，許爽，等.基于多模體邊度的科學(xué)家合作關(guān)系預(yù)測［J］.計(jì)算機(jī)學(xué)報(bào)，2020，43（12）：2372-2384.（Liu Juan，Liu Yafang，Xu Shuang，et al.Predicting scientific collaboration by edge degree of multiple motifs［J］.Chinese Journal of Computers，2020，43（12）：2372-2384.）

［10］Bütün E，Kaya M.A pattern based supervised link prediction in directed complex networks［J］.Physica A：Statistical Mechanics and Its Applications，2019，525：1136-1145.

［11］Zhang Xue，Zhao Chengli，Wang Xiaojie，et al.Identifying missing and spurious interactions in directed networks［J］.International Journal of Distributed Sensor Networks，2015，11（9）：507386.

［12］李治成，吉立新，劉樹新，等.基于拓?fù)溆行нB通路徑的有向網(wǎng)絡(luò)鏈路預(yù)測方法［J］.電子科技大學(xué)學(xué)報(bào)，2021，50（1）：127-137.（Li Zhicheng，Ji Lixin，Liu Shuxin，et al.A method of link prediction in directed network based on effective connectivity path［J］.Journal of University of Electronic Science and Technology of China，2021，50（1）：127-137.）

［13］Shang Keke，Small M，Yan Weisheng.Link direction for link prediction［J］.Physica A：Statistical Mechanics and Its Applications，2017，469：767-776.

［14］Li Jinsong，Peng Jianhua，Liu Shuxin.et al.Link prediction in directed networks utilizing the role of reciprocal links［J］.IEEE Access，2020，8：28668-28680.

［15］Pech R，Hao Dong，Lee Y L，et al.Link prediction via linear optimization［J］.Physica A：Statistical Mechanics and Its Applications，2019，528：121319.

［16］李勁松，彭建華，劉樹新，等.一種基于線性規(guī)劃的有向網(wǎng)絡(luò)鏈路預(yù)測方法［J］.電子與信息學(xué)報(bào)，2020，42（10）：2394-2402.（Li Jinsong，Peng Jianhua，Liu Shuxin，et al.A link prediction method in directed networks via linear programming［J］.Journal of Electronics and Information Technology，2020，42（10）：2394-2402.）

［17］Zhang Qianming，Lyu Linyuan，Wang Wenqiang，et al.Potential theory for directed networks［J］.PLoS One，2013，8（2）：e55437.

［18］Dai Caiyan，Chen Ling，Li Bin，et al.Link prediction in multi-relatio-nal networks based on relational similarity［J］.Information Sciences，2017，394：198-216.

［19］Chen Guangfu，Xu Chen，Wang Jingyi，et al.Robust non-negative matrix factorization for link prediction in complex networks using manifold regularization and sparse learning［J］.Physica A：Statistical Mechanics and Its Applications，2020，539：122882.

［20］Ma Xiaoke，Sun Penggang，Qin Guimin.Nonnegative matrix factoriza-tion algorithms for link prediction in temporal networks using graph communicability［J］.Pattern Recognition，2017，71：361-374.

［21］Chen Guangfu，Xu Chen，Wang Jingyi，et al.Nonnegative matrix factorization for link prediction in directed complex networks using Page-Rank and asymmetric link clustering information［J］.Expert Systems with Applications，2020，148：113290.

［22］Cai Deng，He Xiaofei，Han Jiawei，et al.Graph regularized nonnegative matrix factorization for data representation［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2010，33（8）：1548-1560.

［23］Lee D D，Seung H S.Algorithms for non-negative matrix factorization［C］//Proc of the 13th International Conference on Neural Information Processing Systems.2000：535-541.

［24］Hanley J A，McNeil B J.The meaning and use of the area under a receiver operating characteristic （ROC） curve［J］.Radiology，1982，143（1）：29-36.

［25］Yang Yang，Lichtenwalter R N，Chawla N V.Evaluating link prediction methods［J］.Knowledge and Information System，2015，45（3）：751-782.

［26］Kunegis J.The Koblenz network collection［EB/OL］.（2015）.http：//konect.uni-koblenz.de/.

［27］Bataglj V，Mrva A.Pajek datasets［EB/OL］.（2006）.hup：//vladojmJuni-lj.si/pub/networks/data.

［28］Rossir A，Ahmed N K.Network repository datasets［EB/OL］.（2015）.http：//networkrepository.com/index.php.

［29］Wang Zhiqiang，Liang Jiye，Li Ru.A fusion probability matrix factorization framework for link prediction［J］.Knowledge-Based Systems，2018，159：72-85.