基于預(yù)測誤差修正的時(shí)序鏈路預(yù)測方法

鄧志宏 老松楊 白 亮

?

基于預(yù)測誤差修正的時(shí)序鏈路預(yù)測方法

鄧志宏*老松楊 白 亮

(國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)與管理學(xué)院 長沙 410073)

論文主要針對時(shí)序鏈路預(yù)測方法進(jìn)行研究。分析了靜態(tài)鏈路預(yù)測方法的弊端，認(rèn)為忽視網(wǎng)絡(luò)演化趨勢信息會(huì)對鏈路預(yù)測產(chǎn)生負(fù)面影響；還提出了鏈路預(yù)測誤差的概念用于描述網(wǎng)絡(luò)趨勢信息，并以此為基礎(chǔ)提出一種基于預(yù)測誤差修正的時(shí)序鏈路預(yù)測方法。該方法首先對待預(yù)測時(shí)刻之前一個(gè)時(shí)間窗口內(nèi)的多幅網(wǎng)絡(luò)圖分別采用靜態(tài)鏈路預(yù)測方法進(jìn)行預(yù)測，記錄每次的預(yù)測誤差并計(jì)算其修正值，最后對待測時(shí)刻靜態(tài)預(yù)測結(jié)果進(jìn)行修正得到最終預(yù)測結(jié)果。通過在兩個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行系列實(shí)驗(yàn)表明，該方法較大提升了靜態(tài)鏈路預(yù)測方法的預(yù)測精確度，與另一種典型的時(shí)序鏈路預(yù)測方法相比其精度也有所提升，且算法時(shí)間復(fù)雜度較低。另外，實(shí)驗(yàn)中還發(fā)現(xiàn)鏈路預(yù)測誤差序列與網(wǎng)絡(luò)鏈路總數(shù)序列存在“鏡面對稱”關(guān)系，分析其內(nèi)在原因證明了所提方法的普適性。

復(fù)雜網(wǎng)絡(luò)；鏈路預(yù)測；預(yù)測誤差修正

1 引言

網(wǎng)絡(luò)中的鏈路預(yù)測(link prediction)問題是關(guān)于復(fù)雜網(wǎng)絡(luò)的演化特性研究中一個(gè)重要內(nèi)容，是指如何通過已知的網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生連接的可能性。網(wǎng)絡(luò)中的鏈路預(yù)測既包含了對未知鏈接(existent yet unknown links)的預(yù)測，也包含了對未來鏈接(future links)的預(yù)測。預(yù)測已經(jīng)存在但尚未被發(fā)現(xiàn)的連接實(shí)際上是一種數(shù)據(jù)挖掘的過程，而對于未來可能產(chǎn)生的連邊的預(yù)測則是對網(wǎng)絡(luò)演化規(guī)律的把握。

鏈路預(yù)測具有重要的應(yīng)用價(jià)值，如解決推薦系統(tǒng)中數(shù)據(jù)稀少的問題[1]；用于電子商務(wù)中向用戶推薦可能感興趣的商品，在線社交網(wǎng)絡(luò)好友推薦[2]；在揭示蛋白質(zhì)作用網(wǎng)絡(luò)中隱而未知的鏈接的實(shí)驗(yàn)中，事先通過鏈路預(yù)測縮小實(shí)驗(yàn)檢測范圍，可以大大減少實(shí)驗(yàn)所耗費(fèi)的成本[3,4]；在科學(xué)家合作網(wǎng)中利用鏈路預(yù)測方法識(shí)別潛在合作可能[5]；此外鏈路預(yù)測方法在識(shí)別犯罪網(wǎng)絡(luò)結(jié)構(gòu)，檢測和控制網(wǎng)絡(luò)攻擊等應(yīng)用中也能發(fā)揮重要作用。

已有的鏈路預(yù)測方法大多是以待預(yù)測時(shí)刻點(diǎn)之前的靜態(tài)網(wǎng)絡(luò)圖作為預(yù)測依據(jù)，沒有考慮網(wǎng)絡(luò)的歷史演化信息，這在許多具體應(yīng)用中是不合理的，因?yàn)閷?fù)雜網(wǎng)絡(luò)所描述的現(xiàn)實(shí)系統(tǒng)而言，其未來時(shí)刻的結(jié)構(gòu)狀態(tài)不是單純由前一時(shí)刻結(jié)構(gòu)狀態(tài)決定，而是在時(shí)間軸上統(tǒng)一于系統(tǒng)的整體變化趨勢，因此鏈路預(yù)測方法中選取多幅連續(xù)網(wǎng)絡(luò)圖作為預(yù)測依據(jù)更為合理。Huang等人[15]基于這種思想，依據(jù)是否考慮網(wǎng)絡(luò)時(shí)序演化信息將鏈路預(yù)測方法分為靜態(tài)鏈路預(yù)測方法(SLPM)和時(shí)序鏈路預(yù)測方法(TLPM)兩大類，關(guān)于時(shí)序鏈路預(yù)測方法的研究近年來逐漸被重視，文獻(xiàn)[15]將多幅連續(xù)網(wǎng)絡(luò)圖轉(zhuǎn)化為鏈路的出現(xiàn)序列數(shù)據(jù)，然后采用時(shí)間序列分析方法預(yù)測下一時(shí)刻指定鏈路是否會(huì)出現(xiàn)；文獻(xiàn)[16]首先用三階張量來描述時(shí)序網(wǎng)絡(luò)圖數(shù)據(jù)，然后采用矩陣和張量分解的方法進(jìn)行預(yù)測；文獻(xiàn)[17]提出一種頻繁子圖概念，將時(shí)序網(wǎng)絡(luò)圖轉(zhuǎn)換為頻繁子圖集合序列，然后對頻繁子圖的出現(xiàn)概率進(jìn)行估計(jì)，從而實(shí)現(xiàn)對鏈路的預(yù)測。這些方法的一個(gè)共同點(diǎn)在于放棄了時(shí)序網(wǎng)絡(luò)圖本身蘊(yùn)含的豐富的結(jié)構(gòu)演化信息，通過一些其它數(shù)學(xué)模型來描述時(shí)序網(wǎng)絡(luò)圖，進(jìn)而將鏈路預(yù)測問題轉(zhuǎn)化為對應(yīng)數(shù)學(xué)模型求解問題，這種方式雖然有可能獲得較高精度解，但都存在算法復(fù)雜度較高的問題，針對規(guī)模比較大的網(wǎng)絡(luò)難以滿足算法效率要求。

本文以基于結(jié)構(gòu)相似性的靜態(tài)鏈路預(yù)測方法為基礎(chǔ)，針對時(shí)序鏈路預(yù)測問題，提出一種基于預(yù)測誤差修正的時(shí)序鏈路預(yù)測方法，主要思想是改變以往只依據(jù)某一時(shí)刻網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息進(jìn)行預(yù)測的方式，通過觀察待預(yù)測點(diǎn)前一個(gè)時(shí)間段內(nèi)的預(yù)測結(jié)果與真實(shí)網(wǎng)絡(luò)的結(jié)構(gòu)差異，記錄這些差異作為下一時(shí)刻預(yù)測結(jié)果的修正值，從而使得最終預(yù)測結(jié)果向真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)逼近。

2 問題描述與符號注記

3 方法

SLPM僅僅依據(jù)前一個(gè)時(shí)刻網(wǎng)絡(luò)拓?fù)淇煺者M(jìn)行預(yù)測，這就類似于對移動(dòng)目標(biāo)進(jìn)行位置預(yù)測時(shí)，單純依靠前一時(shí)刻目標(biāo)快照信息對目標(biāo)下一時(shí)刻位置進(jìn)行預(yù)測。這類方法忽視了預(yù)測對象在過去一段時(shí)間內(nèi)的變化趨勢，必然會(huì)很大程度上受網(wǎng)絡(luò)演化在單一時(shí)刻表現(xiàn)出的隨機(jī)性以及噪聲的影響，因而采用SLPM方法預(yù)測得到的結(jié)果必然會(huì)和網(wǎng)絡(luò)真實(shí)結(jié)構(gòu)存在差異。這種結(jié)構(gòu)差異的現(xiàn)實(shí)含義可以很豐富，在不同類型的網(wǎng)絡(luò)中，產(chǎn)生這些結(jié)果差異的深層原因也是多種多樣的。

如圖1所示在線社會(huì)網(wǎng)絡(luò)中采用CN算法進(jìn)行朋友推薦，如果僅觀察t時(shí)刻網(wǎng)絡(luò)拓?fù)湫畔?，可以發(fā)現(xiàn),兩節(jié)點(diǎn)之間存在較多共同鄰居節(jié)點(diǎn)。依據(jù)CN算法，這兩個(gè)節(jié)點(diǎn)之間將會(huì)產(chǎn)生連邊(成為朋友)的可能性很大，但如果觀察前一段時(shí)間的網(wǎng)絡(luò)拓?fù)湫畔ⅲ瑢?huì)發(fā)現(xiàn)節(jié)點(diǎn)在較長一段時(shí)間內(nèi)連邊未發(fā)生任何變化，這可能是因?yàn)楣?jié)點(diǎn)已退出該網(wǎng)絡(luò)社區(qū)。這種情況下，采用靜態(tài)CN算法得出的結(jié)果必然和實(shí)際情況存在較大誤差，究其原因就是SLPM方法忽略了類似“節(jié)點(diǎn)可能已退出該網(wǎng)絡(luò)社區(qū)”這種蘊(yùn)含在網(wǎng)絡(luò)演化過程中的趨勢信息，而這種信息往往會(huì)對鏈路預(yù)測結(jié)果產(chǎn)生較大影響。對于不同類型的網(wǎng)絡(luò)，這種趨勢信息的表現(xiàn)不盡相同，難以用統(tǒng)一的指標(biāo)去度量，但不論這種趨勢信息是什么含義，對于鏈路預(yù)測而言，都會(huì)帶來相同的結(jié)果，即預(yù)測誤差。這種差異存在于每次獨(dú)立預(yù)測過程中，通過觀察每次預(yù)測誤差以及相鄰間隔預(yù)測誤差變化可以在一定程度上反應(yīng)出網(wǎng)絡(luò)的演化趨勢信息，充分利用這種演化趨勢信息能夠?qū)︽溌奉A(yù)測產(chǎn)生積極影響。本文基于上述思想提出基于預(yù)測誤差修正的時(shí)序鏈路預(yù)測方法，方法框架如圖2所示，其主要思想是通過觀察待預(yù)測時(shí)刻之前一個(gè)時(shí)間窗口內(nèi)的多幅網(wǎng)絡(luò)拓?fù)鋱D，采用SLPM方法分別進(jìn)行多次靜態(tài)預(yù)測，測量每次的鏈路預(yù)測誤差，以這些誤差值作為下一次預(yù)測的修正依據(jù)，通過這種方式盡量減小下一次預(yù)測的預(yù)測誤差。例如圖1所示示例網(wǎng)絡(luò)，在過去3個(gè)時(shí)刻內(nèi)，采用CN方法得到的節(jié)點(diǎn),間鏈路的生成概率均較高，但在實(shí)際網(wǎng)絡(luò)演化中，,間一直未出現(xiàn)連邊，因而在下一次預(yù)測時(shí)，應(yīng)當(dāng)適當(dāng)減小該節(jié)點(diǎn)對間的鏈路生成概率值。

圖1 示例演化網(wǎng)絡(luò)

鏈路預(yù)測誤差是本文方法的一個(gè)核心概念。

定義鏈路預(yù)測誤差(LPE)是指應(yīng)用SLPM方法得到的預(yù)想網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和真實(shí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之間的差異，可以用式(2)進(jìn)行度量。

其中為下一時(shí)刻真實(shí)網(wǎng)絡(luò)的鄰接矩陣，由于本文研究的是無向無權(quán)網(wǎng)，中的元素非1即0;為SLPM方法得到的鏈路生成概率矩陣，中的元素需要經(jīng)過如式(3)的歸一化處理：

如何依據(jù)記錄的預(yù)測誤差序列計(jì)算預(yù)測誤差修正值是本文方法的關(guān)鍵。最簡單的方法可以對所有預(yù)測誤差序列值求平均值，但這種方式?jīng)]有考慮誤差序列的時(shí)間特性以及誤差值的變化趨勢，本文采用式(4)計(jì)算鏈路預(yù)測誤差修正值。

基于以上分析，采用式(5)計(jì)算最終鏈路生成概率矩陣。

4 實(shí)驗(yàn)

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

本文在以下兩個(gè)不同類型的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上測試所提方法的有效性。

(1)安然公司郵件數(shù)據(jù)集[18](Enron email dataset)；

(2)高能量子物理科學(xué)家合作數(shù)據(jù)集[19](high- energy particle physics coauthorship dataset)。

本文使用的安然郵件數(shù)據(jù)集(Enron)是由USC大學(xué)Jitesh Shetty等人整理的一個(gè)完整性、一致性均較好的數(shù)據(jù)集版本，數(shù)據(jù)集總共包含了252,759封郵件。本文實(shí)驗(yàn)中抽取了1999年5月至2002年6月中151個(gè)員工之間的總計(jì)21,254封郵件構(gòu)建時(shí)序網(wǎng)絡(luò)圖，151個(gè)員工的郵件地址作為網(wǎng)絡(luò)的節(jié)點(diǎn)，每一條郵件表示發(fā)件人和收件人代表的兩個(gè)節(jié)點(diǎn)間存在連邊，郵件的發(fā)送時(shí)間作為演化網(wǎng)絡(luò)的時(shí)間戳。根據(jù)實(shí)驗(yàn)需要，本文依據(jù)劃分時(shí)序網(wǎng)絡(luò)圖的時(shí)間段長度的不同分別生成兩組時(shí)序網(wǎng)絡(luò)圖，一組是將郵件數(shù)據(jù)按月劃分得到的總共38個(gè)月的演化網(wǎng)絡(luò)，記為GE，另一組是將郵件數(shù)據(jù)按照周劃分得到的總共158個(gè)周的演化網(wǎng)絡(luò)GE。

高能量子物理科學(xué)家合作數(shù)據(jù)集(Hep-th)包含了1992年至2003年期間總共9200位作者，29555篇論文和87794個(gè)合作關(guān)系的數(shù)據(jù)，本文選取其中最高產(chǎn)并且與其他作者至少合作過一次的的96位作者之間的總共1796條合作記錄用于實(shí)驗(yàn)，每條論文合作記錄表示兩個(gè)作者代表的節(jié)點(diǎn)間存在連邊，以論文最終提交時(shí)間作為鏈路的時(shí)間戳，以季度為時(shí)間步長構(gòu)建時(shí)序網(wǎng)絡(luò)圖，記為G。

4.2 實(shí)驗(yàn)設(shè)計(jì)

為了全面驗(yàn)證本文方法的可行性與有效性，本節(jié)設(shè)計(jì)了4個(gè)實(shí)驗(yàn)，如表1所示。實(shí)驗(yàn)結(jié)果與4種SLPM方法以及文獻(xiàn)[15]提出的一種時(shí)序鏈路預(yù)測方法(TSCP)進(jìn)行對比。

表1實(shí)驗(yàn)設(shè)計(jì)

序號實(shí)驗(yàn)?zāi)康闹饕獏?shù)設(shè)置 Enron(Monthly)Enron(Weekly)Hep-th 1算法總體性能驗(yàn)證, , , 2時(shí)間窗口T參數(shù)分析,, , 3誤差影響衰減因子參數(shù)分析,,, 4預(yù)測誤差分析, , _

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

實(shí)驗(yàn)1 算法總體性能驗(yàn)證實(shí)驗(yàn)

圖3 AUC值計(jì)算訓(xùn)練集與測試集的選取方法

圖4 本文方法與SLPM方法對比

實(shí)驗(yàn)2 時(shí)間窗口參數(shù)影響實(shí)驗(yàn)

實(shí)驗(yàn)3 誤差影響衰減因子參數(shù)影響實(shí)驗(yàn)

實(shí)驗(yàn)4 鏈路預(yù)測誤差分析實(shí)驗(yàn)

圖5 本文方法與TSCP方法對比

圖6 時(shí)間滑窗大小對預(yù)測算法的影響

圖7誤差影響衰減因子對預(yù)測算法的影響

圖8預(yù)測誤差序列與各時(shí)刻鏈路總數(shù)序列

這是一個(gè)很有趣的現(xiàn)象，但不是一個(gè)巧合現(xiàn)象。前文分析過，采用鏈路預(yù)測方法預(yù)測得到的結(jié)果必然會(huì)和網(wǎng)絡(luò)真實(shí)結(jié)構(gòu)存在差異，這種結(jié)構(gòu)差異的現(xiàn)實(shí)含義可以很豐富，在不同類型的網(wǎng)絡(luò)中，產(chǎn)生這些結(jié)果差異的深層原因也是多種多樣的。之前關(guān)于在線社會(huì)網(wǎng)絡(luò)朋友推薦的例子中，是由于節(jié)點(diǎn)本身某些屬性影響造成鏈路預(yù)測產(chǎn)生較大偏差，而在對Enron郵件數(shù)據(jù)預(yù)測中，預(yù)測誤差的波動(dòng)是由于某些突發(fā)事件導(dǎo)致的。這兩個(gè)例子中，前者表明預(yù)測誤差與節(jié)點(diǎn)度指標(biāo)存在一定關(guān)系，后者表明預(yù)測誤差與網(wǎng)絡(luò)鏈路總數(shù)存在一定關(guān)系，這種關(guān)聯(lián)關(guān)系正好證明了預(yù)測誤差確實(shí)能夠反映出網(wǎng)絡(luò)演化趨勢信息，對鏈路預(yù)測起到積極影響。并且與節(jié)點(diǎn)度變化、鏈路總數(shù)變化這類指標(biāo)不同，后者用來描述網(wǎng)絡(luò)演化趨勢信息會(huì)受具體網(wǎng)絡(luò)類型的制約，而預(yù)測誤差由于不是對網(wǎng)絡(luò)本身屬性描述，因而具有普適性。由此可以得出結(jié)論本文方法能夠適用于不同類型現(xiàn)實(shí)網(wǎng)絡(luò)的鏈路預(yù)測。

5 結(jié)束語

鏈路預(yù)測最初作為數(shù)據(jù)挖掘領(lǐng)域的研究方向之一，如今已在多個(gè)領(lǐng)域具有重要應(yīng)用，鏈路預(yù)測方法近年來也受到廣泛關(guān)注。本文針對靜態(tài)鏈路預(yù)測方法忽視網(wǎng)絡(luò)演化趨勢信息的弊端，提出了一種基于預(yù)測誤差修正的時(shí)序鏈路預(yù)測方法，采用預(yù)測誤差來描述網(wǎng)絡(luò)演化趨勢信息，進(jìn)而輔助鏈路預(yù)測。以兩個(gè)真實(shí)數(shù)據(jù)集——安然郵件數(shù)據(jù)集和高能量子物理科學(xué)家合作數(shù)據(jù)集進(jìn)行了一系列實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文方法能夠較大程度地提升SLPM方法預(yù)測精度，與已有的一種典型的時(shí)序鏈路預(yù)測方法相比，在預(yù)測精度和算法時(shí)間復(fù)雜度上都具有一定優(yōu)勢。另外還通過實(shí)驗(yàn)分析了算法中兩個(gè)關(guān)鍵參數(shù)對預(yù)測結(jié)果的影響，最后通過分析預(yù)測誤差與網(wǎng)絡(luò)鏈路總數(shù)關(guān)系，證明了預(yù)測誤差是一種可以用來描述網(wǎng)絡(luò)演化趨勢信息的普適指標(biāo)，進(jìn)而證明了本文方法能夠適用于不同類型現(xiàn)實(shí)網(wǎng)絡(luò)的鏈路預(yù)測。

下一步研究重點(diǎn)包括兩個(gè)方面：(1)本文方法對于有向、加權(quán)網(wǎng)絡(luò)的適用性需要進(jìn)一步研究；(2)對于存在多種類型鏈路的網(wǎng)絡(luò)，如何預(yù)測節(jié)點(diǎn)之間會(huì)產(chǎn)生何種連邊是值得研究的問題。

[1] Chiluka N, Andrade N, and Pouwelse J. A link prediction approach to recommendations in large-scale user-generated content systems[C]. Proceedings of the 33rd European conference on Advances in Information Retrieval, Ireland, 2011: 189-200.

[2] Aiello L M, Barrat A, Schifanella R,.. Friendship prediction and homophily in social media[J].(), 2012, 6(2): 1-37.

[3] Yu H, Braun P, Yildirim M A,.. High-quality binary protein interaction map of the yeast interaction network[J]., 2008, 322(5898): 104-110.

[4] Stumpf M P H, Thorne T, Silva E de,.. Estimating the size of the human interaction[J]., 2008, 105(19): 6959-6964.

[5] Gu Q, Zhou J, and Ding C. Collaborative filtering: weighted nonnegative matrix factorization incorporating user and item graphs[C]. Proceedings of the SIAM International Conference on Data Mining, Columbus, 2010: 199-210.

[6] Mohammad Al Hasan and Mohammed J Zaki. A Survey of Link Prediction in Social Networks[M].New York, Social network Data Analysis, Springer, 2011: 243-275.

[7] Lü L and Zhou T. Link prediction in complex networks: a survey[J]., 2010, 390(6): 1150-1170.

[8] Clauset A, Moore C, and Newman M E J. Hierarchical structure and the prediction of missing links in networks[J]., 2008, 453: 98-101.

[9] Guimera R and Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks[J]., 2009, 106(52): 22073-22078.

[10] Jamali M, Huang T, and Ester M. A generalized stochastic block model for recommendation in social rating networks[C]. Proceedings of the fifth ACM Conference on Recommender Systems, New York, 2011: 53-60.

[11] Huang S, Chen M, and Luo B,.. Predicting aggregate social activities using continuous-time stochastic process[C]. Proceedings of the 21st ACM International Conference on Information and Knowledge Management, New York, 2012: 982-991.

[12] Liben-Nowell D and Kleinberg J. The link prediction problem for social networks[J]., 2007, 58(7): 1019-1031.

[13] Papadimitriou A, Symeonidis P, and Manolopoulos Y. Scalable link prediction in social networks based on local graph characteristics[C]. ITNG 2012 : 9th Int’l Conference on Information Technology- New Generations, Las Vegas, 2012: 738-743.

[14] Zhou T, Lü L, and Zhang Y C. Predicting missing links via local information[J]., 2009, 71: 623-630.

[15] Huang Z and Lin D K J. The time series link prediction problem with applications in communication surveillance[J]., 2009, 21(2): 286-303.

[16] Dunlavy D M, Kolda T G, and Acar E. Temporal link prediction using matrix and tensor factorizations[J]., 2011, 5(2): 1-27.

[17] Lahiri M and Berger-Wolf T Y. Structure prediction in temporal networks using frequent subgraphs[C]. Proceedings of the 2007 IEEE Symposium on Computational Intelligence and Data Mining, Hawaii, 2007: 35-42.

[18] Adibi J I. Enron email dataset[OL]. http://www.isi. edu/_adibi/Enron/Enron.htm, 2013.

[19] The Knowledge Discovery Laboratory (KDL), Hep-th dataset[OL]. https://kdl.cs.umass.edu/ display/ public/ HEP-Th, 2013.

鄧志宏： 男，1986年生，博士生，研究方向?yàn)橹笓]控制與指揮決策分析.

老松楊： 男，1968年生，教授，研究方向?yàn)橹笓]控制與指揮決策分析、視頻情報(bào)分析.

白 亮： 男，1978年生，副教授，研究方向?yàn)橹笓]控制與指揮決策分析、視頻情報(bào)分析.

A Temporal Link Prediction Method Based on Link Prediction Error Correction

Deng Zhi-hong Lao Song-yang Bai Liang

(,,410073,)

The temproral link prediction method is investigated in this paper. The disadvantages of the static link prediction methods are analyzed, considering that ignoring the evolving information of networks will lead to a negative impact on link predicting. The concept of link prediction error is proposed to describe the evolving information of networks, and a temporal link prediction method is proposed based on the prediction error correction. Firstly, several static link prediction are carried out using each graph in the previous periods window, and then the prediction errors are recorded and used for calculating the modification value. At last, the final prediction result is acquired through refining the static prediction result with the modification value. Several experiments are conducted using two real network datasets. The results show that the proposed method achieves better performance than the static link prediction methods and a typical temporal link prediction method. In addition, it can be found that a relation of ‘mirror symmetry’ exists between prediction error series and total link number series, which demonstrates the universality of the proposed method.

Complex network; Link prediction; Prediction error correction

TP391

A

1009-5896(2014)02-0325-07

10.3724/SP.J.1146.2013.00657

鄧志宏 lingyu0207@gmail.com

2013-05-10收到，2013-10-14改回

國家自然科學(xué)基金(60902094)資助課題