基于預測誤差修正的時序鏈路預測方法

鄧志宏 老松楊 白 亮

?

基于預測誤差修正的時序鏈路預測方法

鄧志宏*老松楊 白 亮

(國防科學技術大學信息系統與管理學院 長沙 410073)

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

復雜網絡；鏈路預測；預測誤差修正

1 引言

網絡中的鏈路預測(link prediction)問題是關于復雜網絡的演化特性研究中一個重要內容，是指如何通過已知的網絡結構等信息預測網絡中尚未產生連邊的兩個節點之間產生連接的可能性。網絡中的鏈路預測既包含了對未知鏈接(existent yet unknown links)的預測，也包含了對未來鏈接(future links)的預測。預測已經存在但尚未被發現的連接實際上是一種數據挖掘的過程，而對于未來可能產生的連邊的預測則是對網絡演化規律的把握。

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

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

本文以基于結構相似性的靜態鏈路預測方法為基礎，針對時序鏈路預測問題，提出一種基于預測誤差修正的時序鏈路預測方法，主要思想是改變以往只依據某一時刻網絡拓撲結構信息進行預測的方式，通過觀察待預測點前一個時間段內的預測結果與真實網絡的結構差異，記錄這些差異作為下一時刻預測結果的修正值，從而使得最終預測結果向真實網絡拓撲結構逼近。

2 問題描述與符號注記

3 方法

SLPM僅僅依據前一個時刻網絡拓撲快照進行預測，這就類似于對移動目標進行位置預測時，單純依靠前一時刻目標快照信息對目標下一時刻位置進行預測。這類方法忽視了預測對象在過去一段時間內的變化趨勢，必然會很大程度上受網絡演化在單一時刻表現出的隨機性以及噪聲的影響，因而采用SLPM方法預測得到的結果必然會和網絡真實結構存在差異。這種結構差異的現實含義可以很豐富，在不同類型的網絡中，產生這些結果差異的深層原因也是多種多樣的。

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

圖1 示例演化網絡

鏈路預測誤差是本文方法的一個核心概念。

定義鏈路預測誤差(LPE)是指應用SLPM方法得到的預想網絡拓撲結構和真實網絡拓撲結構之間的差異，可以用式(2)進行度量。

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

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

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

4 實驗

4.1 數據集

本文在以下兩個不同類型的真實網絡數據集上測試所提方法的有效性。

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

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

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

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

4.2 實驗設計

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

表1實驗設計

序號實驗目的主要參數設置 Enron(Monthly)Enron(Weekly)Hep-th 1算法總體性能驗證, , , 2時間窗口T參數分析,, , 3誤差影響衰減因子參數分析,,, 4預測誤差分析, , _

4.3 實驗結果與分析

實驗1 算法總體性能驗證實驗

圖3 AUC值計算訓練集與測試集的選取方法

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

實驗2 時間窗口參數影響實驗

實驗3 誤差影響衰減因子參數影響實驗

實驗4 鏈路預測誤差分析實驗

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

圖6 時間滑窗大小對預測算法的影響

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

圖8預測誤差序列與各時刻鏈路總數序列

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

5 結束語

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

下一步研究重點包括兩個方面：(1)本文方法對于有向、加權網絡的適用性需要進一步研究；(2)對于存在多種類型鏈路的網絡，如何預測節點之間會產生何種連邊是值得研究的問題。

[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年生，博士生，研究方向為指揮控制與指揮決策分析.

老松楊： 男，1968年生，教授，研究方向為指揮控制與指揮決策分析、視頻情報分析.

白 亮： 男，1978年生，副教授，研究方向為指揮控制與指揮決策分析、視頻情報分析.

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改回

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