利用矩陣補全優(yōu)化模型進行動態(tài)網(wǎng)絡鏈接預測

宋光鑫，王麗平

南京航空航天大學 理學院，南京 211106

1 引言

在計算機科學中，網(wǎng)絡通常是指一幅節(jié)點或連邊具有語義的圖，它可以挖掘社交網(wǎng)絡上的人際關系[1]，電商網(wǎng)站中用戶對商品的偏好或生物化學領域蛋白質之間的相互作用。對這樣的數(shù)據(jù)結構進行數(shù)據(jù)挖掘時，傳統(tǒng)的數(shù)據(jù)挖掘算法通常只考慮網(wǎng)絡的節(jié)點屬性，并將數(shù)據(jù)中的每個節(jié)點視為從某個分布中采樣得到的獨立同分布個體。這樣簡單的假設通常會對算法結果造成誤導，因此研究節(jié)點之間的連邊模式變得尤為必要。

在大多數(shù)情況下，被觀測到的網(wǎng)絡結構信息是不完整的，預測網(wǎng)絡中兩個節(jié)點之間是否存在連邊將是一個令人感興趣的問題。另一方面，某些網(wǎng)絡中的連邊隨著時間表現(xiàn)出動態(tài)的特性，這樣的網(wǎng)絡中人們可能會關心某條連邊在未來是否會出現(xiàn)。由已觀測到的網(wǎng)絡結構推測未觀測到的網(wǎng)絡結構通常被稱為靜態(tài)鏈接預測，而由過去時刻的網(wǎng)絡結構推測未來時刻的網(wǎng)絡結構被稱為動態(tài)鏈接預測。目前針對靜態(tài)鏈接預測提出的預測算法主要包括基于節(jié)點相似度[2]、基于最大似然估計[3]和基于概率模型[4]的三大類別。其中最常見的是基于相似度的算法，例如Preferential Attachment Index（PA）、Common Neighbours（CN）、Adamic-Adar（AA）、Katz 等算法[5-6]，這些算法在靜態(tài)鏈接預測中顯示出了強大的效果，常被用于基準算法。對于靜態(tài)鏈接預測的研究還在持續(xù)，如伍杰華[7]引入樹狀數(shù)據(jù)結構來計算合著者網(wǎng)絡結構，并聯(lián)合樸素貝葉斯算法和節(jié)點相似度實現(xiàn)鏈接預測；張昱等人[8]提出了一種融合網(wǎng)絡結構和節(jié)點屬性的鏈接預測方法；程華等人[9]關注節(jié)點的鄰域相似性和依賴關系，提出了基于Attention機制的靜態(tài)鏈接預測算法；Pech 等人[10]建立了基于魯棒PCA（principal component analysis）的矩陣補全模型并應用于靜態(tài)鏈接預測；Mohtashemi 等人[11]提出了對數(shù)正態(tài)矩陣補全模型來求解鏈接預測問題。相較之下，動態(tài)鏈接預測加入了時間維度，考慮網(wǎng)絡結構隨著時間的演變，它的預測難度更大。早期的動態(tài)鏈接預測方法主要是將靜態(tài)問題的算法進行一定的推廣。近年來，隨著人工智能的興起，許多機器學習的方法被應用于動態(tài)網(wǎng)絡鏈接預測[12-14]。安琛等人[15]將主動學習應用于動態(tài)網(wǎng)絡鏈接預測，充分利用了網(wǎng)絡中未鏈接節(jié)點的信息。Chen 等人[16]提出監(jiān)督學習對網(wǎng)絡中節(jié)點對的結構進行建模以預測未來時刻可能出現(xiàn)的鏈接。陳陽等人[17]將集成學習引入動態(tài)鏈接，把鏈接預測看作一個分類問題，通過訓練多個分類器來提高類別預測效果，使得網(wǎng)絡演變的動態(tài)信息得到充分的利用。Xu等人[18]利用監(jiān)督學習和特征工程的方法關注動態(tài)圖變化的特征信息，有效提高了預測準確度。Li 等人[19]利用深度學習的方法以及梯度提升樹模型挖掘動態(tài)鏈接中隱藏的模式關系。目前，絕大多數(shù)動態(tài)鏈接預測論文中提出的動態(tài)鏈接預測方法主要關注網(wǎng)絡圖隨時間演化的特征信息和節(jié)點相似性，很少考慮網(wǎng)絡結構的稀疏性和在原始空間中難以學習到的非線性鏈接關系。近年來，稀疏學習和壓縮感知得到了深入的研究和應用，Liu等人將其應用到協(xié)同過濾當中，并加入核方法來獲得在原始空間中不能夠學習到的非線性關系[20]。受此啟發(fā)，本文將矩陣補全方法應用于動態(tài)鏈接預測，并借鑒Liu等人為協(xié)同過濾構造核矩陣分解模型的方法，為動態(tài)鏈接預測構造了核矩陣補全模型，通過將原始數(shù)據(jù)映射到高維Hilbert空間，再應用矩陣補全模型來學習到更多的鏈接信息，提高模型的預測效果。

2 鏈接預測問題

2.1 靜態(tài)鏈接預測

靜態(tài)鏈接預測問題是在已知網(wǎng)絡的節(jié)點和連邊的條件下預測未觀測到的連邊。設已觀測網(wǎng)絡G=(V,E)，其中V代表所有節(jié)點的集合，E代表已觀測到的連邊的集合，用N和M分別代表網(wǎng)絡中節(jié)點和連邊的數(shù)目。網(wǎng)絡的鄰接矩陣用A∈{0,1}N×N表示，Aij=1代表節(jié)點對(i,j)上存在一條連邊（從i指向j），即(i,j)∈E。記所有的節(jié)點對構成的集合為U=V×V，鏈接預測問題就是要對一開始未觀測到連邊的節(jié)點對(i,j)∈UE，給出其實際存在鏈接的可能性。靜態(tài)鏈接預測的算法為每一個節(jié)點對(i,j)∈UE給出一個存在鏈接的得分值score(i,j)，然后對每一個得分值進行排序，得分越高的節(jié)點處越有可能存在鏈接。常用的靜態(tài)鏈接預測算法大多根據(jù)節(jié)點之間的相似度來排序得到最可能存在鏈接的節(jié)點對，具有代表性的算法如引言中所述，有CN、AA、PA 等。其中，CN 算法統(tǒng)計網(wǎng)絡圖中每個節(jié)點的鄰接節(jié)點，并計算每對節(jié)點的公共鄰接節(jié)點的數(shù)量作為它們可能產(chǎn)生鏈接的分數(shù)。AA 算法則在CN算法的基礎上添加了節(jié)點權重系數(shù)。PA算法認為節(jié)點x產(chǎn)生新的節(jié)點的概率與它的鄰接節(jié)點數(shù)量| |Γ(x) 成正比，那么節(jié)點x與節(jié)點y存在鏈接的概率則正比于。

2.2 動態(tài)鏈接預測

對于動態(tài)鏈接預測問題，已觀測數(shù)據(jù)通常是網(wǎng)絡在一段時間T內的演變序列{G1,G2,…,GT}。其中Gt=(V,Et)是網(wǎng)絡在t時刻的鏈接狀態(tài)，V是前T個時間序列中出現(xiàn)過的節(jié)點集合，Et則是t時刻網(wǎng)絡中連邊的集合。網(wǎng)絡序列的鄰接矩陣A∈{0,1}N×N×T是單幅網(wǎng)絡鄰接矩陣在第三個維度上疊加得到的。即Aijt=1表示節(jié)點對(i,j)在t時刻具有鏈接。動態(tài)鏈接預測問題需要根據(jù)前T個時刻的網(wǎng)絡序列Gt(t=1,2,…,T)的鄰接矩陣At來預測T+1 時刻的鄰接矩陣At+1，從而得到Gt+1。許多如CN、PA、AA等基于鄰域的算法可以簡單地推廣到動態(tài)鏈接預測問題上。推廣方法為視AT為一個靜態(tài)鄰接矩陣而直接對AT應用相應的算法，更常用的方法是定義網(wǎng)絡Gtotal的鄰接矩陣Atotal，Atotal在任意時刻出現(xiàn)過的連邊均視為在Atotal上存在，再對Atotal應用靜態(tài)鏈接預測算法得到At+1。這種直接將靜態(tài)鏈接算法推廣到動態(tài)中的方法雖然簡單，但實驗表明，往往具有很好的效果[1]。此外，Chakrabarti等人建立了一種根據(jù)鄰域相似性的非參數(shù)估計模型[21]來求解動態(tài)鏈接預測。該方法對某個節(jié)點和其他節(jié)點產(chǎn)生連邊的概率展開研究，并認為具有相似鄰域的節(jié)點產(chǎn)生連邊的概率相等，通過同時利用時間和空間上的拓撲結構對鏈接出現(xiàn)的可能性進行預測。出于相同的目的，Hisano提出了半監(jiān)督圖嵌入的方法[14]，通過定義在時間序列上的監(jiān)督損失和網(wǎng)絡狀態(tài)上的無監(jiān)督損失，來獲得時間和空間上的信息，以達到動態(tài)鏈接預測的目的。

3 矩陣補全與核化矩陣補全

3.1 標準矩陣補全算法

2.2節(jié)所述的動態(tài)鏈接預測算法雖然考慮了時間維度的變化信息，但卻忽略了鄰接矩陣的結構特征。一般地，真實世界中的一幅大規(guī)模的網(wǎng)絡鄰接矩陣，在某個時間段內節(jié)點與節(jié)點之間的互動是非常有限的，而節(jié)點與節(jié)點之間產(chǎn)生鏈接又具有較強的相關性，因此網(wǎng)絡圖的鄰接矩陣具有低秩性和稀疏性。矩陣補全是指，對一個大小為n1×n2的矩陣，在采樣得到矩陣中m個元素的情況下，根據(jù)一定的假設條件和優(yōu)化方法來計算出其他未觀測到的元素的數(shù)值。近年來，有部分學者將矩陣補全應用于靜態(tài)鏈接預測問題，如Pech等人將魯棒PCA的矩陣補全求解方法用于靜態(tài)鏈接預測[10]，Gao 等人則提出交替迭代的矩陣補全模型求解靜態(tài)鏈接預測[22]。動態(tài)鏈接預測是根據(jù)圖Gt預測圖Gt+1，一個自然的想法是把Gt和Gt+1疊加看作一張完整的圖G，而Gt作為已觀測到的網(wǎng)絡結構，定義增加矩陣Ft+1=Mt+1-Mt,M表示網(wǎng)絡鏈接預測中的鄰接矩陣，那么Mt表示t時刻網(wǎng)絡的鄰接矩陣。在已知矩陣Mt時對Gt+1的預測就是對Ft+1的預測，即根據(jù)已觀測到的元素來預測G中隱藏的鏈接，這等價于靜態(tài)鏈接預測。靜態(tài)鏈接預測與動態(tài)鏈接預測的這種相似關系啟發(fā)本文將矩陣補全應用于動態(tài)鏈接預測問題。

定義某個網(wǎng)絡結構在時刻t的鄰接矩陣為Mt，為了預測下一時刻的鄰接矩陣，建立動態(tài)網(wǎng)絡鏈接預測的矩陣補全模型：

式中，PΩ(·)是采樣算子，將不在采樣集Ω中的矩陣元素置為0，其他元素不變。在鏈接預測問題中，令采樣集為鄰接矩陣中已存在鏈接的位置集合，這里不考慮鏈接權重，則設Mij=1,(i,j)∈Ω,PΩ(Mt)視為在時刻t的鄰接矩陣，動態(tài)鏈接預測問題往往關注新產(chǎn)生的鏈接位置，那么不妨認為從時刻t到時刻t+1 在觀測集內的鏈接依然存在，并根據(jù)t時刻鏈接結構推測t+1 時刻在觀測集Ω外哪些位置會發(fā)生鏈接。由（1）求出的矩陣X就是對采樣集外所有位置產(chǎn)生鏈接可能性的打分，數(shù)值越大代表越有可能產(chǎn)生鏈接。λ是需要手動設置的參數(shù)，λ越大代表越重視矩陣的低秩約束[23]。

模型（1）是一個關于X的矩陣LASSO 問題，目前求解無約束最優(yōu)化模型的優(yōu)化算法已非常豐富，本文使用加速近端梯度下降法[24]求解矩陣補全模型。另外，為了更多地利用以往時刻網(wǎng)絡的結構信息，不妨將以往多個時間片段的鄰接矩陣進行疊加來作為待補全矩陣，則（1）可以寫為如下形式：

式中，T表示要使用的過去的歷史時刻數(shù)量，用T個鄰接矩陣來預測下一時刻的鄰接矩陣。這里將T個鄰接矩陣相加，因為本文不考慮鏈接權重，所以將鏈接產(chǎn)生的位置數(shù)值設為1，使用符號函數(shù)sign(·)對做相應處理。為了符號表述的整潔，將（2）改寫為更一般的形式：

式中，A(·)：Rm×n→Rp是將所有在采樣集Ω中的矩陣元素按列展開拉成一個列向量的算子，Ω={(i,j)|加速近端梯度下降算法的工作原理已得到充分的研究[24]，調用相應的優(yōu)化算法包即可完成運算。在此簡單列出它的迭代公式：

將模型（3）代入框架（4）中，則框架中會出現(xiàn)如下子問題：

子問題（5）存在閉式解[25]，該解可以通過奇異值分解求得。若A的奇異值分解為A=UΣVT,Σ=diag(σi),則其閉式解為X=U[diag(σi-λ)+]VT，即將所有奇異值都減去λ，被減后小于0 的置為0。這相當于給奇異值設定了一個閾值，所有小于這個閾值的奇異值被消減為0，這樣就使得矩陣中的非零奇異值數(shù)量減少，從而得到降低矩陣的秩的目的。以下給出了求解的完整步驟。由于使用加速近端梯度下降法求解網(wǎng)絡鏈接預測的矩陣補全模型，本文將該算法稱為APG（Accelerated Proximal Gradient）算法。

算法1 APG 算法：用加速近端梯度下降算法求解矩陣LASSO問題（3）

輸入：采樣算子A(·)、采樣集b、系數(shù)λ、步長μ、最大迭代次數(shù)k_max。

輸出：Xopt。

初始化：X0=X-1=0m×n,t0=t-1=1,k=0,1,2,…,k_max

1.

2.Ak=Yk-μkA*(A(Yk)-b),其中A*是A的逆算子

3.A奇異值分解，得到U,diag(σ),V

4.Xk+1=U[diag(σi-μkλ)+]VT

5.

6.k=k+1,若滿足收斂條件則輸出Xk,否則回到步驟1。

由APG算法得到的X是對增加矩陣FT+1的預測，由MT+1=MT+FT+1，就得到了對下一時刻鄰接矩陣的預測。

3.2 核化矩陣補全

網(wǎng)絡鏈接預測關注節(jié)點之間的相似性，而真實世界的網(wǎng)絡鏈接具有稀疏性和相關性，由矩陣分解的知識可以將網(wǎng)絡的一個鄰接矩陣看作兩個低秩矩陣內積的形式，即X≈UTV，這種分解需要保證在已觀測位置(i,j)∈Ω上信息相似，則（2）可轉化為如下形式：

式中，U,V∈Rk×n為分解得到的兩個低秩矩陣，M表示上一時刻的鄰接矩陣。則模型（6）表示用兩個低秩矩陣來補全矩陣M。傳統(tǒng)的矩陣分解方法通常假設相關鏈接數(shù)據(jù)分布在一個線性超平面上。然而，隨著真實世界中網(wǎng)絡結構愈發(fā)復雜，許多網(wǎng)絡鄰接矩陣不滿足低秩性要求，很難通過線性矩陣分解的模型來預測未來的鏈接結構。為了克服這一困難，本文將核方法引入矩陣補全模型中。核方法考慮把鏈接數(shù)據(jù)嵌入一個更高維的特征空間，在這個空間中鏈接數(shù)據(jù)可以分布在一個線性超平面上，這使得鄰接矩陣可以被表示為兩個特征矩陣內積的形式。為了引入核方法，首先令φ(x)為將某個向量x映射到高維特征空間后對應的特征向量，內積＜x,y ＞相應地變?yōu)椋鸡?x),φ(y)＞，進一步引入核函數(shù)：

核方法將鏈接數(shù)據(jù)嵌入到高維特征空間H 中，這個嵌入映射是隱式的，但可以由核函數(shù)定義。假設某個核函數(shù)對應的特征空間映射為φ:X→H，其中X 是原始空間，H 是Hilbert空間，則特征空間中的特征矩陣內積可以通過核函數(shù)，利用原空間中的向量計算。引入核技巧后，使用Hilbert 空間中向量構成的矩陣φ(U) 和φ(V)代替原特征空間中的U、V，將問題（6）改寫為：

矩陣U、V是需要求解的目標，而非觀測到的數(shù)據(jù)，無法通過核函數(shù)直接求解φ(U)Tφ(V)。為此本文通過引入字典向量來代替直接求解U、V。因為在無限維Hilbert 空間中，特征矩陣被映射到線性超平面中，鏈接數(shù)據(jù)之間的非線性關系被轉化為線性關系，根據(jù)泛函分析的知識可知，任何一個Hilbert空間都有一族標準正交基，則特征矩陣可以由一組基線性表示[26]。受字典學習相關理論的啟發(fā)[27]，本文使用φ(di)的線性組合來逼近矩陣φ(U)，通過建立形如的帶正則化項的字典學習模型來求得最優(yōu)的φ(di)，從而求得φ(U)Tφ(V)。具體地，給定k個d維字典向量d={d1,d2,…,dk}，di∈Rd，那么可以假設低秩矩陣U的每一列uj對應的特征向量φ(uj)均可被字典向量d在特征空間中線性表示為如下形式：

其中，aij為每個字典向量的權重系數(shù)，φ(di)為字典向量d的第i個分量di在特征空間中對應的特征向量，ai=(ai1,ai2,…,aik)T,Φ=(φ(d1),φ(d2),…,φ(dk)) 。同樣，將矩陣V的每一列vj表示為：

同樣，bij為每個特征向量的權重系數(shù)，bi=(bi1,bi2,…,bik)T。將權重向量a和b按行疊成矩陣A、B，記：

由于無法直接求解φ(U)Tφ(V) ，通過引入字典向量，將特征矩陣φ(U)、φ(V)轉化為字典矩陣Φ的表達式，這樣可以得到ΦTΦ，也就構造出了核矩陣。

同時注意到：

根據(jù)式（9）～式（12），可以將模型（8）重寫為：

其中，K=ΦTΦ是字典向量導出的核矩陣。為了求解模型（13），本文采用交替最小二乘法，其收斂性可以參考文獻[28]。算法的具體步驟是，首先固定U，即保持矩陣A不變，可以將（13）按列分解為n個子問題：

其中，Ωj={i|(i,j)∈Ω}表示原矩陣M在第j列上觀測到的行i元素組成的集合。約定算子PΩj僅對行進行操作，即PΩj(X)將保留X的所有i∈Ωj行整行，其余元素設為0。類似的用Ωi={j|(i,j)∈Ω}表示在矩陣R第i行上觀測到的列j元素組成的集合，PΩi(X)將保留X的所有j∈Ωi行整行。m:,j、vj分別表示矩陣M、V的第j列。

問題（14）是一個類似嶺回歸的問題，其閉式解為：

其中，A:,Ωj為保留矩陣A的i∈Ωj列得到的子矩陣，m:.Ωj表示由原矩陣M的Ωj個元素構成的列向量。將n個按列的方向組成矩陣對應地可以獲得，其中為：

其中，B:,Ωi=PΩi(BT)T為矩陣B的j∈Ωi列構成的子矩陣。m:.Ωj表示由M的Ωi個元素構成的列向量。

交替使用式（15）、（16）迭代更新B、A直至收斂，最終得到A*、B*后，即可通過X*=A*TKB*得到X*作為矩陣補全的結果。以下給出了算法流程，為了敘述方便，將該算法命名為KMC（Kernelized Matrix Completion）算法。

算法2 KMC算法：求解模型（13）

輸入：待補全矩陣M，字典向量d，核函數(shù)κ。

輸出：M≈X=ATKB。

隨機初始化A、B

計算核矩陣Kij=κ(di,dj)

Repeat

根據(jù)（15）更新B

根據(jù)（16）更新A

Until收斂條件滿足或達到最大迭代次數(shù)

ReturnX=ATKB

許多研究常使用奇異值閾值法求解矩陣補全問題，如將問題（1）中的矩陣X寫為奇異值分解的形式：

其中，σi是矩陣X的按降序排列的奇異值，Σ為其構成的奇異值矩陣。奇異值閾值法通過近端梯度下降法，在使得X能近似M的前提下，不斷通過奇異值閾值算子將X較小的奇異值置為0 來保證X的低秩性[25]。將式（17）的核范數(shù)進行變形得：

省略系數(shù)整理得：

不難看出，KMC 模型（13）與（19）具有一定的相似性。事實上，若設問題（19）的最優(yōu)解為U*、Σ*、V*，對模型（13），若核矩陣K恰為Σ*時，則可表示為：

這說明KMC模型符合一般的矩陣補全模型。對于矩陣分解模型（6），若取矩陣-Σ∈Rk×n，令：

4 實驗

4.1 實驗環(huán)境和數(shù)據(jù)信息

為了檢測本文提出的算法的效果，挑選了三個真實世界的動態(tài)網(wǎng)絡鏈接數(shù)據(jù)進行實驗。實驗中使用PA、CN 兩種靜態(tài)鏈接算法和Pech 等人提出的魯棒PCA 的矩陣補全模型法做對比。本文實驗代碼由作者使用Matlab2018a 編寫。運行環(huán)境為Win10，Intel?Core? i7-4510U CPU@2.0 GHz，8 GB內存。

表1給出了實驗數(shù)據(jù)集的特征信息。WorldTrade記錄了58 個國家的國際貿易情況的數(shù)據(jù)，記錄時間為1981—2000年，若對每年所有國家之間的貿易額度進行排序，取貿易額前10%國家，視為兩國之間存在鏈接，這樣可以通過數(shù)據(jù)集建立20 個58×58 的鄰接矩陣。表中總鏈接數(shù)是20 個鄰接矩陣所有產(chǎn)生鏈接的個數(shù)總和，時期平均鏈接數(shù)是單位時間矩陣中存在鏈接數(shù)的平均值。EmailEu-core 是歐洲某個大型研究會的郵件系統(tǒng)，記錄了研究會1 005名成員的郵件往來。本文選取研究會中兩個部門的核心成員在550 天內的郵件往來記錄進行實驗，其中每50天作為一個時間單位，則可得到11個n×n的動態(tài)網(wǎng)絡（n為部門核心成員數(shù)量）。

表1 數(shù)據(jù)集信息

本文采用AUC（Area Under ROC Curve）作為評價指標。假設正類樣本數(shù)量和負類樣本數(shù)量分別為M和N，首先按照輸出值對所有樣本從低到高排序并對每個樣本賦予一個排名rank，輸出值最低的元素rank為1，輸出值最高的元素rank為M+N，然后AUC可以通過以下公式計算：

4.2 實驗參數(shù)設置

對于APG和KMC算法，二者都用到了平衡低秩約束與采樣約束的正則項系數(shù)，即目標函數(shù)（3）和（13）中的λ，這類參數(shù)的選取已得到較詳細的研究，本文按文獻[24]所得出的結論將其設置為。

4.2.1 使用到的歷史時刻長度T

首先可能會對算法產(chǎn)生影響的參數(shù)是算法所使用的時間序列長度T。直觀上，利用越多的歷史時刻可以獲得越多的網(wǎng)絡結構變化的信息，數(shù)值實驗也基本符合這一推斷，圖1展示了本文提出的核矩陣補全算法分別在三個數(shù)據(jù)集上的實驗效果。三條折線的整體趨勢是上升的，標準矩陣補全算法（APG）的實驗結果與圖1類似。因為數(shù)據(jù)集能提供的網(wǎng)絡隨時間的變化信息總是有限的，所以當選取過多的歷史時刻進行訓練時可能會造成信息的冗余而產(chǎn)生過擬合，AUC 分數(shù)并不會隨著時刻數(shù)量線性增長。為了盡量少地使用歷史時刻長度以節(jié)省計算開銷，KMC算法建議采用3～5個歷史時刻。

圖1 時間序列T 對結果的影響

4.2.2 字典向量維度d

圖2 字典向量維度d 對結果的影響

字典向量的維度d是本文提出的KMC算法需要用到的超參數(shù)之一。圖2展示了KMC算法在三組數(shù)據(jù)集上AUC 隨d的變化情況。一般認為，字典向量的維度越高，越能得到更多的鏈接信息，但是圖2 在三組數(shù)據(jù)集上的實驗結果，AUC分數(shù)在小范圍內波動，算法對參數(shù)的選取不敏感。這是由于字典向量被嵌入到高維Hilbert空間當中，算法總是能捕捉到高維空間中的鏈接信息，使得對d的選取不敏感。最終在三組數(shù)據(jù)集上選取d=200 來進行數(shù)值實驗。

4.2.3 矩陣A、B 的秩k

對于KMC 算法在初始化時設置低秩矩陣A、B的秩k。由圖3結果可知，對于WorldTrade和EmailEu_Dep2的實驗，結果基本穩(wěn)定在一個較高的得分，在k值選取很小時，符合矩陣的低秩假設和矩陣補全的要求，當k增大時，低秩矩陣A、B的秩并不會隨著k的增加而線性增長，這是因為正則化項的約束作用，所以預測結果仍然維持在最優(yōu)的水平。對于EmailEu_Dep1出現(xiàn)了在k=2～6 時分數(shù)較低的現(xiàn)象，可能是因為網(wǎng)絡結構存在低秩特征矩陣難以捕捉的信息。

圖3 參數(shù)k 對結果的影響

4.2.4 核函數(shù)的選取

KMC 算法中將數(shù)據(jù)嵌入更高維度的空間，而高維空間由核函數(shù)隱式地確定，因此選取不同的核函數(shù)就確定了鏈接數(shù)據(jù)不同的嵌入方式，即從不同的角度體現(xiàn)數(shù)據(jù)的分布規(guī)律。表2中MC算法是不使用任何核函數(shù)的矩陣補全算法，其余為使用線性核、高斯核、拉普拉斯核的矩陣補全算法。

表2 不同核函數(shù)在數(shù)據(jù)集上的AUC分數(shù)

從表2可知，拉普拉斯核的算法在所有實驗中分數(shù)均高于不使用核函數(shù)的MC算法，這驗證了使用核技巧的有效性。部分實驗中也出現(xiàn)了高斯核與線性核算法的效果不如不使用核技巧算法的情況，這可能是由于不合適的核函數(shù)不能體現(xiàn)該數(shù)據(jù)集的分布規(guī)律，在映射到高維空間后損失了原始空間中的有效信息，使得核技巧的效果較差。由于每組數(shù)據(jù)上KMC（Laplacian）的分數(shù)均高于MC，這表明Laplacian 核函數(shù)能有效地刻畫數(shù)據(jù)的分布規(guī)律，確定的高維空間能夠更有效地將非線性鏈接關系轉化為線性關系。因此在對比實驗中選取Laplacian核作為默認參數(shù)。

4.3 實驗結果

綜合以上實驗參數(shù)的分析，將三組實驗的最優(yōu)參數(shù)的結果列入表3，作為比較實驗時的推薦參數(shù)。

表3 KMC算法的參數(shù)設置

在比較實驗結果時，本文使用靜態(tài)鏈接預測中常用作基準算法的PA、CN 作為參照，其中CN、PA 是指只使用前一時刻網(wǎng)絡結構的算法，CN-all、PA-all是指使用所有歷史時刻片段進行預測的算法，它們都是將靜態(tài)鏈接預測算法直接應用于動態(tài)鏈接預測。RPCA（Robust PCA）是由Pech提出的基于魯棒PCA的矩陣補全算法。APG 是指本文提出的利用加速近端梯度下降法求解矩陣補全的算法，KMC是本文提出的核矩陣補全算法（默認使用Laplacian核）。

表4表示所有算法在三組數(shù)據(jù)集上的AUC分數(shù)，本文提出的KMC算法在前兩組實驗中的AUC得分最高，APG也有較好的表現(xiàn)。在第三組實驗中CN_all的AUC得分最高，KMC略弱于基準算法，但CN_all需要使用以往所有歷史時刻的網(wǎng)絡鄰接矩陣，計算存儲要求較高，不適合處理大規(guī)模鏈接預測問題。RPCA 通過建立噪聲矩陣和原始矩陣求解鏈接預測，本質上屬于矩陣補全模型，因此預測效果與APG相差不大。但由于KMC在矩陣補全模型的基礎上加入核函數(shù)，能夠學習到鏈接之間的非線性關系，因此KMC效果略好于RPCA，實驗結果也驗證了使用核方法的有效性。

表4 多種算法在三組數(shù)據(jù)集上的實驗結果

5 結束語

針對傳統(tǒng)矩陣補全解決鏈接預測的局限性，本文提出了KMC 算法，以解決動態(tài)鏈接預測問題。詳細介紹了矩陣補全和核矩陣補全優(yōu)化模型，并推導了核矩陣補全方法與基于奇異值閾值的矩陣補全方法之間的關系。在三組公開的數(shù)據(jù)集上進行實驗，結果表明，KMC算法優(yōu)于傳統(tǒng)的鏈接預測算法和矩陣補全算法，通過與MC、RPCA算法進行對比，驗證了引入核函數(shù)的有效性。

本文將拉普拉斯核作為核矩陣補全模型中的核函數(shù)，優(yōu)于基于其他常用核函數(shù)的預測效果。未來考慮將如何自適應地選取核函數(shù)和提高核函數(shù)對非線性關系的刻畫能力作為下一步的工作。