融合權(quán)重和結(jié)構(gòu)的加權(quán)非負(fù)矩陣分解的鏈路預(yù)測

陳廣福，劉奇，李曉飛

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

當(dāng)前，復(fù)雜網(wǎng)絡(luò)已是在日常生產(chǎn)生活中無處不在，如交通運(yùn)輸網(wǎng)絡(luò)、在線社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和電力網(wǎng)絡(luò)等。復(fù)雜網(wǎng)絡(luò)的分析和挖掘變得非常重要和有價值。作為復(fù)雜網(wǎng)絡(luò)分析的研究熱點(diǎn)之一，鏈路預(yù)測越來越受到研究者的關(guān)注。鏈路預(yù)測的目標(biāo)是根據(jù)網(wǎng)絡(luò)可觀測結(jié)構(gòu)信息來推斷網(wǎng)絡(luò)中缺失的或新的鏈接[1]。鏈路預(yù)測在現(xiàn)實(shí)世界中有著廣泛的應(yīng)用，例如：識別生物網(wǎng)絡(luò)中潛在的蛋白質(zhì)—蛋白質(zhì)相互作用[2]、在在線商業(yè)系統(tǒng)中推薦商品[3]、預(yù)測書目網(wǎng)絡(luò)中的引用關(guān)系[4]等。

真實(shí)世界網(wǎng)絡(luò)存在大量加權(quán)網(wǎng)絡(luò)，例如科學(xué)家合作網(wǎng)、生物網(wǎng)和交通運(yùn)輸網(wǎng)等。不同加權(quán)網(wǎng)絡(luò)鏈接權(quán)重蘊(yùn)含著不同含義，例如：科學(xué)家合作網(wǎng)中鏈接權(quán)重表示引用次數(shù)；食物網(wǎng)中鏈接權(quán)重代表物種之間的碳流量。鏈接權(quán)重是加權(quán)網(wǎng)絡(luò)最原始結(jié)構(gòu)信息。目前，加權(quán)網(wǎng)絡(luò)的鏈路預(yù)測可歸納為2類：基于結(jié)構(gòu)相似度和非負(fù)矩陣分解。其中基于結(jié)構(gòu)相似度的主要思想是利用鏈接權(quán)重信息去計(jì)算節(jié)點(diǎn)相似度。例如：文獻(xiàn)[5]將共同鄰居(common neighbors，CN)、資源分配(resource allocation，RA)和Adamic-Adar(AA)指標(biāo)擴(kuò)展到加權(quán)網(wǎng)絡(luò)中構(gòu)成加權(quán)局部相似度方法，分別是加權(quán)共同鄰居（weightedcommon neighbors，WCN）、加權(quán)Adamic-Adar（weighted Adamic-Adar，WAA）和加權(quán)資源分配（weighted resource allocation，WRA），其結(jié)果表明考慮自然權(quán)重可顯著改善預(yù)測準(zhǔn)確度；文獻(xiàn)[6]提出基于信息論的加權(quán)局部相似度方法，同理也證實(shí)弱鏈接理論作用；袁榕等[7]同時考慮網(wǎng)絡(luò)中鏈接的聚類和擴(kuò)散性信息與WCN、WAA和WRA相融合，以改善加權(quán)網(wǎng)絡(luò)預(yù)測精度；王曦等[8]將網(wǎng)絡(luò)結(jié)構(gòu)相似度與節(jié)點(diǎn)行為同步指數(shù)相融合，提出用戶行為同步的加權(quán)網(wǎng)絡(luò)鏈路預(yù)測算法。以上方法盡管改善了算法性能，然而僅考慮自然權(quán)重或拓?fù)錂?quán)重，卻無法同時保持自然權(quán)重和拓?fù)錂?quán)重信息。

基于非負(fù)矩陣分解[9]方法是將鄰接矩陣映射到低維潛在空間，保持結(jié)構(gòu)信息，再重構(gòu)原始網(wǎng)絡(luò)獲得最小誤差預(yù)測分?jǐn)?shù)矩陣。當(dāng)前，現(xiàn)有大部分基于非負(fù)矩陣分解的鏈路預(yù)測算法僅適用于無向無權(quán)網(wǎng)絡(luò)，例如：Chen等[10]提出在非負(fù)矩陣分解框架中融合圖則化和稀疏學(xué)習(xí)，保持網(wǎng)絡(luò)局部和全局結(jié)構(gòu)；Ma等[11]提出在非負(fù)矩陣分解框架中融合多標(biāo)簽信息提取網(wǎng)絡(luò)特征。上述算法忽略了網(wǎng)絡(luò)鏈接權(quán)重?zé)o法處理加權(quán)網(wǎng)絡(luò)鏈路問題。隨著非負(fù)矩陣分解在鏈路預(yù)測研究深入，一些研究者將非負(fù)矩陣分解方法擴(kuò)展到加權(quán)網(wǎng)絡(luò)，例如：文獻(xiàn)[12]首次利用非負(fù)矩陣分解技術(shù)處理加權(quán)網(wǎng)絡(luò)鏈路預(yù)測問題，該方法假設(shè)所有鏈接權(quán)重服從泊松分布，其結(jié)果表明該方法考慮鏈接權(quán)重后性能有所提高；Chen等[13]提出在非負(fù)矩陣分解框架中融合聚類與自然權(quán)重，保持加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)。上述方法缺點(diǎn)是僅考慮自然權(quán)重鏈接及局部結(jié)構(gòu)。

針對以上方法的不足，本文提出了一種融合自然權(quán)重鏈接和多類型局部結(jié)構(gòu)的加權(quán)非負(fù)矩陣分解(weight nonnegative matrix factorization，WNMF)模型。它保持多類型局部結(jié)構(gòu)。首先將加權(quán)網(wǎng)絡(luò)鄰接矩陣映射到低維潛在空間，去保持網(wǎng)絡(luò)鏈接權(quán)重信息；然后，將加權(quán)網(wǎng)絡(luò)3個經(jīng)典基于局部結(jié)構(gòu)相似度作為指示矩陣指派到低維潛在空間，保持多類型局部結(jié)構(gòu)；接著，融合上述信息提出3個鏈路預(yù)測模型，分別是WNMF-WCN、WNMF-WAA和WNMF-WRA，再利用更新法則去學(xué)習(xí)所提模型的參數(shù)并從理論上證明所提算法收斂性；最后，在6個加權(quán)網(wǎng)絡(luò)上將現(xiàn)有加權(quán)網(wǎng)絡(luò)方法與本文模型相比較，驗(yàn)證本文所提模型的性能。

1 融合自然權(quán)重和結(jié)構(gòu)的加權(quán)非負(fù)矩陣分解的鏈路預(yù)測模型

1.1 相關(guān)概念

考慮一個無向加權(quán)網(wǎng)絡(luò)G(V,E,W)，其中V=是節(jié)點(diǎn)集，E表示鏈接集，W表示自然權(quán)重。每條邊e∈E是一個有序?qū)=(υi,υj)，并與權(quán)重Wυiυj>0相關(guān)聯(lián)。本文不考慮多個鏈接和自循環(huán)存在，利用X=[xij]N×N來表示G的鄰接矩陣。若G是無向加權(quán)網(wǎng)絡(luò)，如果節(jié)點(diǎn)υi和υj之間存在鏈接，則否則xij=0。

U表示所有可能的鏈接，并且U?E是不存在的鏈接集。鏈路預(yù)測的目標(biāo)是從集合U?E中尋找缺失鏈接。為評估所提模型性能，將可觀察鏈接集E隨機(jī)劃分為2部分：訓(xùn)練集ET和測試集EP。顯然,ET∩EP=φ和ET∪EP=E。本文中：運(yùn)算符〈·〉表示內(nèi)積；AT表示矩陣A的轉(zhuǎn)置；Tr(A)表示矩陣A的跡；‖A‖F(xiàn)表示F范數(shù)；I表示單位矩陣。

1.2 融合自然權(quán)重和結(jié)構(gòu)的加權(quán)非負(fù)矩陣分解的預(yù)測模型

加權(quán)非負(fù)矩陣分解（weighted non-negative matrix factorization，WNMF）[14]是非負(fù)矩陣分解變形。它的優(yōu)點(diǎn)是引入指示矩陣改善預(yù)測缺失鏈接能力。具體地，設(shè)任意網(wǎng)絡(luò)的鄰接矩陣A，將A映射到低維潛在空間，其損失函數(shù)為

式（1）僅適用無向無權(quán)網(wǎng)絡(luò)無法處理加權(quán)網(wǎng)絡(luò)。本文擴(kuò)展式（1）到加權(quán)網(wǎng)絡(luò)，需要修改S。權(quán)重拓?fù)涫羌訖?quán)網(wǎng)絡(luò)重要組成部分?，F(xiàn)有的加權(quán)網(wǎng)絡(luò)3個經(jīng)典局部結(jié)構(gòu)相似度是加權(quán)共同鄰居（weighted common neighbors，WCN）、加權(quán)Adamic-Adar（weighted Adamic-Adar，WAA）和加權(quán)資源分配（weighted resource allocation，WRA），它們的定義如表1所示。

表13 個加權(quán)網(wǎng)絡(luò)局部相似度

將式（2）—（4）替換式（1）中S，則其表達(dá)式分別為：

將加權(quán)網(wǎng)絡(luò)局部結(jié)構(gòu)相似度替換原有的指示矩陣S有2方面的優(yōu)點(diǎn)：1）適用于加權(quán)網(wǎng)絡(luò)并預(yù)測缺失權(quán)重鏈接；2）同時保持局部結(jié)構(gòu)和自然權(quán)重鏈接適用于不同類型加權(quán)網(wǎng)絡(luò)。為防止目標(biāo)函數(shù)過度擬合化，將式（5）—（7）中因子矩陣W和H正則化約束，目標(biāo)函數(shù)為：

式中：⊙為哈達(dá)瑪積（Hadamard Product）；α是防止過度擬合化。將上述3個損失函數(shù)歸納為一個統(tǒng)一的目標(biāo)損失函數(shù)，為

采用拉格朗日乘法規(guī)則學(xué)習(xí)所提模型參數(shù)。根據(jù)矩陣跡性質(zhì)有：Tr(A+B)=Tr(B+A)和Tr(AB)=Tr(BA)。再重寫式（11），為

引入拉格朗日乘子矩陣Φ=[φ]nk和Ψ=[ψnk]，有

1）固定W，更新H。

刪除式（13）中與H無關(guān)項(xiàng)，有

對J(H)求H的偏導(dǎo)，有

由 KKT（Karush-Kuhn-Tucker）條件且φnkhnk=0，有

因此，得到更新規(guī)則為

2）固定H，更新W。

刪除式（13）中與W無關(guān)項(xiàng)，有

對J(W)求W的偏導(dǎo)，有

由 KKT（Karush-Kuhn-Tucker）條件且ψnkwnk=0，有

因此，得到更新規(guī)則，為

目標(biāo)函數(shù)中所有的變量因子矩陣都獲得更新，然后以最小誤差重構(gòu)原始加權(quán)網(wǎng)絡(luò)獲得鏈路預(yù)測概率矩陣，再將預(yù)測概率矩陣按降序排列構(gòu)成有序列表，并將有序列表的分?jǐn)?shù)插入訓(xùn)練集中，計(jì)算評價度量PCC和Precision值。

1.3 本文算法流程

本文算法的具體執(zhí)行過程如下。

輸入：A為加權(quán)網(wǎng)絡(luò)的鄰接矩陣；α為超級參數(shù)；K為潛在空間；最大迭代次數(shù)為maxiter。

輸出：平均PCC和Precision。

步驟1，加權(quán)網(wǎng)絡(luò)鄰接矩陣劃分為：訓(xùn)練集ET和測試集EP。

步驟2，初始化W和H。

步驟3，式（5）—（7）保持自然權(quán)重和局部結(jié)構(gòu)。

步驟4，F(xiàn)ort=1:maxiterdo

步驟5，根據(jù)式(14)，更新H//更新因子矩陣H。

步驟6，根據(jù)式(15)，更新W//更新因子矩陣W。

步驟7，|Jt+1?Jt|<10?6直到收斂為止//收斂終止條件。

步驟8，Endfor。

步驟9，計(jì)算鏈路預(yù)測概率矩陣：S=WHT//預(yù)測分?jǐn)?shù)矩陣。

步驟10，將S按降序排序構(gòu)成有序表。

步驟11，將有序表分?jǐn)?shù)插入訓(xùn)練集ET。

步驟12，計(jì)算PCC和Precision。

步驟13，獲得最終平均預(yù)測準(zhǔn)確度，即平均PCC和Precision值。

2 算法的收斂性

本章通過理論方法證明所提算法收斂性。具體證明過程如下。

定理目標(biāo)函數(shù)J在更新規(guī)則式(14)下是非單調(diào)遞增的。

證明定理成立，需要以下輔助定理。

定義對任意的x和x′，若M(x,x′)是F(x)的輔助函數(shù)，那么必須滿足條件：M(x,x′)≥F(x),M(x,x)=F(x)。

引理1若M(x,x′)是F(x)的輔助函數(shù)，F(xiàn)(x)在更新規(guī)則下單調(diào)遞減。

首先，刪除式（12）中與H無關(guān)項(xiàng)，有

求F(H)對H的一次和二次偏導(dǎo)數(shù)，為：

證明Fnk(Hnk)泰勒展開式為

定理得證。同理可證目標(biāo)函數(shù)J在更新規(guī)則式(15)下是非單調(diào)遞增的，本文省略。

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

3.1 評價度量

采用PCC和Precision 2個指標(biāo)[15]評價所提模型性能。

1）PCC(pearson correlation coefficient)是衡量預(yù)測向量與實(shí)際向量的線性關(guān)系。其定義為

2）Precision是預(yù)測排名靠前鏈接的能力。若按分?jǐn)?shù)排序的前L個鏈接中，有m個鏈接屬于測試集，則Precision計(jì)算公式為

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

6個真實(shí)世界加權(quán)網(wǎng)絡(luò)作為測試所提性能數(shù)據(jù)集。其拓?fù)浣Y(jié)構(gòu)如表1所示。表中：|V|是節(jié)點(diǎn)數(shù)；|E|是鏈接數(shù)；Cw表示節(jié)點(diǎn)平均聚類系數(shù)；Density代表網(wǎng)絡(luò)稀疏程度。

表16 個真實(shí)世界加權(quán)網(wǎng)拓?fù)浣Y(jié)構(gòu)

1)神經(jīng)元網(wǎng)絡(luò)（CELegans，CEL）[16]是由306個節(jié)點(diǎn)和4296個鏈接構(gòu)成秀麗隱桿線蟲的神經(jīng)網(wǎng)絡(luò)。節(jié)點(diǎn)表示神經(jīng)元，鏈接權(quán)重表示2個神經(jīng)元之間的突觸數(shù)量。

2)期刊和雜志網(wǎng)（JOUrnals，JOU）[16]是由124個節(jié)點(diǎn)和11944條鏈接構(gòu)成期刊和雜志網(wǎng)絡(luò)。節(jié)點(diǎn)表示期刊和雜志，鏈接權(quán)重表示讀者數(shù)量。

3)USA1[16]是美國的航空運(yùn)輸網(wǎng)絡(luò)。該網(wǎng)絡(luò)由332個節(jié)點(diǎn)和2126條鏈路組成。節(jié)點(diǎn)表示機(jī)場，鏈接表示路線。鏈接的權(quán)重是2個機(jī)場之間的航班數(shù)量的頻率。

4）USA2[17]是美國500個最繁忙的商業(yè)機(jī)場網(wǎng)絡(luò)。該網(wǎng)絡(luò)由500個節(jié)點(diǎn)和5960條鏈路組成。

5）信息交換論壇網(wǎng)（MESsage，MES）[17]是由899個節(jié)點(diǎn)和11萬2168鏈接構(gòu)成的在線信息交換網(wǎng)。節(jié)點(diǎn)表示用戶，鏈接權(quán)重表示用戶發(fā)布到主題的消息或字符數(shù)關(guān)系。

6）CEGT[18]是由923個節(jié)點(diǎn)和6470鏈接構(gòu)成的生物網(wǎng)。節(jié)點(diǎn)表示基因，鏈接權(quán)重表示基因相互作用。

3.3 基準(zhǔn)算法

為評估所提3個模型的預(yù)測準(zhǔn)確度，選擇10個現(xiàn)有的加權(quán)網(wǎng)絡(luò)鏈路預(yù)測方法與本文模型進(jìn)行對比。10個現(xiàn)有的加權(quán)網(wǎng)絡(luò)鏈路預(yù)測方法說明如下。

1)加權(quán)共同鄰居(WCN)[5]、加權(quán)AA((WAA)[5]、加權(quán)資源分配指標(biāo)RA(WRA)[5]。3個指標(biāo)是在基于局部相似度基礎(chǔ)上考慮鏈接權(quán)重信息，其定義為：

式中z∈Oxy表示節(jié)點(diǎn)x和y的共同鄰居。

2)WMI-WCN[6]、WMI-WAA[6]和WMI-WRA[6]。基于信息論框架下融合網(wǎng)絡(luò)局部結(jié)構(gòu)信息。

3)rWCN、rWAA和rWRA[15]是局部權(quán)重拓?fù)浣Y(jié)構(gòu)與可靠路徑相融合的加權(quán)網(wǎng)絡(luò)預(yù)測指標(biāo)。

式中z∈Oxy表示節(jié)點(diǎn)x和y的共同鄰居。

4）線性最優(yōu)化(linear optimization，LO)[19]。該指標(biāo)假設(shè)2個節(jié)點(diǎn)之間存在鏈接的可能性，可以通過相鄰節(jié)點(diǎn)貢獻(xiàn)的線性求和來展開，其定義為

式中 α為超級參數(shù)。

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

本文采用PCC和Precision度量指標(biāo)去評估所提模型性能。由于所提模型中包含有3個重要的參數(shù)α、潛在空間維數(shù)K和迭代次數(shù)需要進(jìn)行預(yù)設(shè)，因此對所有數(shù)據(jù)集設(shè)置參數(shù)α=3，潛在空間維數(shù)K=60，最大迭代次數(shù)為60。在6個加權(quán)網(wǎng)絡(luò)上實(shí)驗(yàn)結(jié)果如表2所示。

1）所提模型WNMF-WCN、WNMF-WAA和WNMF-WRA在6個加權(quán)網(wǎng)絡(luò)上，PCC和Precision值均獲得最優(yōu)，表明所提模型獲得高質(zhì)量性能。所提模型獲得高預(yù)測準(zhǔn)確度的主要原因是可同時保持自然權(quán)重和多類型局部結(jié)構(gòu)，獲得了更多結(jié)構(gòu)信息。具體地，所提模型與第二優(yōu)秀方法相比，在CEL、JOU、MES和CEGT加權(quán)網(wǎng)絡(luò)上PCC分別提高了4.9%、0.4%、22.8%和3.1%，在CEL、JOU、USA1、USA2、MES和CEGT網(wǎng)絡(luò)上Precision分別提高了4.3%、6%、0.7%、7%、23.5%和5%。在PCC度量方面，第二優(yōu)秀方法分別指：在CEL數(shù)據(jù)集中是LO；在JOU數(shù)據(jù)集中是WMI-WAA；在MES數(shù)據(jù)集中是WRA；在CEGT數(shù)據(jù)集中是WRA。在Preecision度量方面，第二優(yōu)秀方法分別指：在CEL數(shù)據(jù)集中是LO；在JOU數(shù)據(jù)集中是WRA；在USA1數(shù)據(jù)集中是WAA；在USA2數(shù)據(jù)集中是rWRA；在MES數(shù)據(jù)集中是LO；在CEGT數(shù)據(jù)集中是WAA。

2)3個基于局部結(jié)構(gòu)相似度指標(biāo)WCN、WAA和WRA，以及基于可靠路徑rWCN、rWAA和rWRA在6個加權(quán)網(wǎng)絡(luò)上均獲得較差預(yù)測準(zhǔn)確度。主要原因是該類指標(biāo)僅考慮自然權(quán)重鏈接，無法捕獲更多結(jié)構(gòu)信息?；谛畔⒄摰?個預(yù)測指標(biāo)WMI-WCN、WMI-WAA和WMI-WRA啟用互信息捕獲網(wǎng)絡(luò)結(jié)構(gòu)在6個加權(quán)網(wǎng)絡(luò)上預(yù)測，其準(zhǔn)確度與上述方法有提高。

3）LO在本質(zhì)上與非負(fù)矩陣分解類似，采用節(jié)點(diǎn)鄰居貢獻(xiàn)線性和分解獲得最優(yōu)解，在6個加權(quán)網(wǎng)絡(luò)上獲得較優(yōu)性能。然而，與所提模型相比較，LO獲得較低預(yù)測準(zhǔn)確度的原因是該指標(biāo)僅捕獲節(jié)點(diǎn)三階路徑信息。所提模型最優(yōu)預(yù)測者與LO相比較，在CEL、JOU、USA1、USA2、MES和CEGT網(wǎng)絡(luò)上Precision分別提高了4.3%、7.8%、15.2%、18.5%、23.5%和5%。

4）所提模型WNMF-WCN、WNMF-WAA和WNMF-WRA本質(zhì)上都是在WNMF框架融合加權(quán)網(wǎng)絡(luò)局部結(jié)構(gòu)。然而它們最大區(qū)別是從不同角度捕獲加權(quán)網(wǎng)絡(luò)局部結(jié)構(gòu)。例如：WNMF-WCN是統(tǒng)計(jì)節(jié)點(diǎn)間共同鄰居數(shù)量方式獲得加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)，與WCN相比較預(yù)測準(zhǔn)確度顯著提高；WNMF-WAA是以懲罰節(jié)點(diǎn)共同鄰居權(quán)重較大節(jié)點(diǎn)形式捕獲加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)；WNMF-WRA是通過共同鄰居間資源分配去捕獲網(wǎng)絡(luò)結(jié)構(gòu)。由表2可知：WNMF-WCN性能最優(yōu)的主要原因是6個加權(quán)網(wǎng)絡(luò)的聚類系數(shù)都較高，表明WNMF-WCN捕獲更多節(jié)點(diǎn)間共同鄰居數(shù)量；WNMF-WAA在JOU網(wǎng)絡(luò)上獲得最優(yōu)預(yù)測準(zhǔn)確度，其原因是JOU聚類系數(shù)最大，表明存在權(quán)重較大節(jié)點(diǎn)，通過懲罰機(jī)制獲得最優(yōu)性能；WNMF-WRA在CEGT網(wǎng)絡(luò)（稀疏率0.0076）獲得最優(yōu)性能，其主要原因是通過資源分配改善了稀疏性。因此，3個模型適用不同類型加權(quán)網(wǎng)絡(luò)。

本文還通過設(shè)置不同比率改變網(wǎng)絡(luò)稀疏性，以測試所提模型魯棒性。設(shè)訓(xùn)練集比率范圍為40%、50%、···、90%。由于空間有限，本實(shí)驗(yàn)僅選取WCN、rWCN、WMI-WCN、NMF和WNMFWCN 5個模型，其實(shí)驗(yàn)結(jié)果如圖1所示。由圖可知，在不同比率下本文所提模型獲得最優(yōu)性能，當(dāng)訓(xùn)練集40%時，意味著網(wǎng)絡(luò)稀疏率達(dá)到60%，在6個加權(quán)網(wǎng)絡(luò)上所提模型均獲得最優(yōu)性能，表明所提模型魯棒于稀疏網(wǎng)絡(luò)。

圖1 不同訓(xùn)練集下對應(yīng)Precision值

4 參數(shù)敏感性分析

本章討論所提模型主要參數(shù)對性能的影響。所提模型包含3個重要參數(shù)：α、潛在空間K和最大迭代次數(shù)。設(shè) α變化范圍為{0，0.03，0.3，3，30}，潛在空間K變化范圍為{10，20，30，···，100}以及最大迭代次數(shù)變化范圍為{10，20，30，···，100}。研究一個參數(shù)對性能影響，固定其他2個參數(shù)。由于空間有限，本文僅討論WNMF-WCN模型與3個參數(shù)的變化關(guān)系，WNMF-WAA和WNMF-WRA類似WNMF-WCN。

4.1 參數(shù)α變化

參數(shù) α約束因子矩陣預(yù)防模型過度擬合，其結(jié)果如圖2所示。當(dāng)α=0時，所提模型退化為融合多類局部結(jié)構(gòu)的加權(quán)非負(fù)矩陣分解模型，PCC和Precision值較高，表明該模型以最小誤差重構(gòu)原始網(wǎng)絡(luò)。隨著 α增加，直到α=3時，PCC和Precision值最優(yōu)，而當(dāng)α>3時，PCC和Precision值顯著下降，表明 α取較大值時影響算法收斂速度。因此，α=3時，所提模型獲得最優(yōu)預(yù)測準(zhǔn)確度。

圖2 參數(shù)α變化對應(yīng)PCC和Precision值

4.2 參數(shù)K變化

所提模型性能直接受參數(shù)K影響：K過小導(dǎo)致預(yù)測準(zhǔn)確度下降；K太大導(dǎo)致時間復(fù)雜度增加。其實(shí)驗(yàn)結(jié)果如圖3所示。當(dāng)K=10時，PCC和Precision值最小，表明潛在空間無法捕獲更多加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)和自然權(quán)重鏈接。當(dāng)K值逐漸增加，PCC和Precision值隨之改善，直到K=60，PCC和Precision獲得最優(yōu)預(yù)測準(zhǔn)確度，表明所提模型的潛在空間獲得足夠網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)K>60時，PCC和Precision值開始穩(wěn)定。因此K=60時，所提模型性能最優(yōu)。

圖3 參數(shù)K變化對應(yīng)PCC和Precision值

4.3 最大迭代次數(shù)變化

最大迭代次數(shù)直接影響所提模型的收斂速度，其實(shí)驗(yàn)結(jié)果如圖4所示。僅MES網(wǎng)絡(luò)在開始時處于波動而其他5個加權(quán)網(wǎng)絡(luò)波動不明顯，當(dāng)?shù)螖?shù)為60時，在6個加權(quán)網(wǎng)絡(luò)上的PCC和Precision值基本保持穩(wěn)定。

圖4 最大迭代次數(shù)變化對應(yīng)PCC和Precision值

5 結(jié)束語

現(xiàn)有大量的鏈路預(yù)測算法僅考慮無向無權(quán)網(wǎng)絡(luò)而忽略權(quán)重貢獻(xiàn)。如何將非負(fù)矩陣分解模型擴(kuò)展到加權(quán)網(wǎng)絡(luò)的鏈路預(yù)測方法中是一種挑戰(zhàn)。針對現(xiàn)有大部分非負(fù)矩陣分解算法僅適用于無向無權(quán)網(wǎng)絡(luò)，本文提出一個融合自然權(quán)重和多類結(jié)構(gòu)的加權(quán)非負(fù)矩陣分解的鏈路預(yù)測模型。該模型將3個經(jīng)典加權(quán)局部相似度作為指示矩陣分配給非負(fù)矩陣分解模型，構(gòu)建加權(quán)非負(fù)矩陣分解的鏈路預(yù)測模型。此外，提供拉格朗日乘法法則優(yōu)化模型和學(xué)習(xí)模型的參數(shù)，并重構(gòu)原始網(wǎng)絡(luò)獲得鏈路預(yù)測分?jǐn)?shù)矩陣。在6個真實(shí)加權(quán)網(wǎng)絡(luò)上，將該模型與現(xiàn)有代表性加權(quán)網(wǎng)絡(luò)方法比較，其實(shí)驗(yàn)結(jié)果表明該模型的預(yù)測性能獲得明顯改善。