楊 磊，李臣龍

(1．安徽工程大學(xué) 計算機與信息學(xué)院，安徽 蕪湖 241000；2．安徽工程大學(xué) 計算機應(yīng)用技術(shù)重點實驗室，安徽 蕪湖 241000)

?

基于動態(tài)網(wǎng)絡(luò)的鏈接分析與預(yù)測研究

楊 磊1,2，李臣龍1,2

(1．安徽工程大學(xué) 計算機與信息學(xué)院，安徽 蕪湖 241000；2．安徽工程大學(xué) 計算機應(yīng)用技術(shù)重點實驗室，安徽 蕪湖 241000)

復(fù)雜網(wǎng)絡(luò)通過新節(jié)點和新鏈接的增加而隨著時間快速演化，使用網(wǎng)絡(luò)的靜態(tài)特征難以產(chǎn)生精確的鏈接預(yù)測。通過分析動態(tài)網(wǎng)絡(luò)特征，結(jié)合張量分解，提出了一種新的基于動態(tài)網(wǎng)絡(luò)的鏈接預(yù)測方法，并應(yīng)用于真實的復(fù)雜動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集中對未來鏈接進行分析預(yù)測，實驗演示了該方法的優(yōu)點和效果，取得了較好的預(yù)測結(jié)果。

鏈接預(yù)測；動態(tài)網(wǎng)絡(luò)；張量分析；局部路徑

隨著在線社交平臺和信息網(wǎng)絡(luò)的增長，復(fù)雜靜態(tài)網(wǎng)絡(luò)研究在社交網(wǎng)絡(luò)、信息網(wǎng)絡(luò)等多方面已經(jīng)有了大量的研究，并取得了很多成果，但這些研究僅僅關(guān)注復(fù)雜網(wǎng)絡(luò)單個快照的靜態(tài)圖屬性，缺少網(wǎng)絡(luò)演化的動態(tài)信息[1-2]，而動態(tài)網(wǎng)絡(luò)的影響擴散過程與靜態(tài)網(wǎng)絡(luò)有很大不同?，F(xiàn)實世界中幾乎所有復(fù)雜網(wǎng)絡(luò)都具有某種動態(tài)性，其中個體之間的交互隨時間推移而不斷發(fā)生變化。由于鏈接預(yù)測的挑戰(zhàn)，通過分析網(wǎng)絡(luò)中大量節(jié)點的增加或減少，抽取隨著時間改變的動態(tài)信息對于解決鏈接預(yù)測問題是必要的。

動態(tài)網(wǎng)絡(luò)是一種隨著時間演化的特殊網(wǎng)絡(luò)，表示復(fù)雜網(wǎng)絡(luò)在不同時刻的快照，分析每個時刻網(wǎng)絡(luò)的演化情況，是動態(tài)網(wǎng)絡(luò)研究的重點。目前動態(tài)網(wǎng)絡(luò)研究還處于起步階段，國內(nèi)外很多研究人員針對動態(tài)網(wǎng)絡(luò)的各種問題進行探索，很多問題的提出及研究方法都源于靜態(tài)網(wǎng)絡(luò)。然而，基于動態(tài)網(wǎng)絡(luò)的時序特點，動態(tài)模式挖掘不是各時刻快照上的簡單疊加，動態(tài)網(wǎng)絡(luò)在最短路徑、聚集系數(shù)等指標(biāo)的全局及局部時序度量方面與靜態(tài)指標(biāo)度量有很大區(qū)別[2]。Shan 等人[3]依據(jù)所考察網(wǎng)絡(luò)相鄰時刻拓?fù)浣Y(jié)構(gòu)變化不太大的特點，用網(wǎng)絡(luò)變化增量方式考察每個時刻的社團結(jié)構(gòu)信息，李艷梅等人[4]針對動態(tài)信息網(wǎng)絡(luò)中異常結(jié)構(gòu)演化過程，通過角色定義刻畫網(wǎng)絡(luò)的結(jié)構(gòu)特征，提出了角色演化異常的概念，并給出了基于模式挖掘的角色演化異常發(fā)現(xiàn)算法。大多數(shù)動態(tài)網(wǎng)絡(luò)模型是基于平均節(jié)點度的增長函數(shù)[5-6]，在鏈接預(yù)測方面有許多廣泛的應(yīng)用，如基于過去瀏覽歷史預(yù)測一個網(wǎng)絡(luò)沖浪者在一個特定的日子或許會訪問的Web頁面，預(yù)測計算機網(wǎng)絡(luò)故障的模式，預(yù)測一個旅行者在一個特定的月份將要飛往的地方?？茖W(xué)家合作網(wǎng)絡(luò)是典型的動態(tài)網(wǎng)絡(luò)，隨著新作者的加入和原作者間新的合作關(guān)系的產(chǎn)生而不斷變化，通過研究以前T年的科學(xué)會議出版數(shù)據(jù)，預(yù)測作者將會在T+1年在哪次會議發(fā)表論文。

本文利用張量分解理論[7]，結(jié)合局部路徑指標(biāo)鏈接預(yù)測方法[8]，通過分析包括時間維在內(nèi)的三維張量網(wǎng)絡(luò)鏈接結(jié)構(gòu)，提出了一種動態(tài)網(wǎng)絡(luò)的鏈接分析預(yù)測方法，新的方法應(yīng)用于真實的動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集中進行實驗分析及評價，并與共同鄰居(CN)、Katz指標(biāo)方法以及EVtCF[9]進行比較參考，取得了較好的實驗結(jié)果。

1 問題描述

定義1.1(動態(tài)網(wǎng)絡(luò)) 對于無向網(wǎng)絡(luò)圖G(V，E)，其中V是節(jié)點集合，E是節(jié)點間邊的集合，集合{GT，t=1, 2, …, T}是一個動態(tài)圖，Gt是t 時刻網(wǎng)絡(luò)拓?fù)鋱D，GT+1= (V, ET+1)，ET+1是時刻T+1上圖的邊集。圖1是網(wǎng)絡(luò)在不同時刻的狀態(tài)變化，節(jié)點a和節(jié)點b比其他節(jié)點活躍，隨著時間變化而不斷產(chǎn)生新的鏈接。

圖1 網(wǎng)絡(luò)節(jié)點在不同時刻的狀態(tài)示例

定義1.2 (動態(tài)網(wǎng)絡(luò)鏈接預(yù)測) 給定T時刻動態(tài)網(wǎng)絡(luò)圖{ GT, t=1, 2, …, T}，鏈接預(yù)測的問題是推斷出下一時刻T+1的圖GT+1=(V,ET+1)，其中ET+1是T+1時刻的邊集。

為了觀察鏈接關(guān)系在時間上的演化趨勢，動態(tài)網(wǎng)絡(luò)鏈接數(shù)據(jù)可以組織成一個三階張量。通過分析三維張量鏈接結(jié)構(gòu)，把時間定義為單獨的一維，相應(yīng)時間t上Z的矩陣切片表示為Zt，通過分析Z的鏈接結(jié)構(gòu)來預(yù)測T+1時刻上的鏈接。定義一個M*N*T大小的張量如下：

2 張量分析

張量分析首先出現(xiàn)在心理測驗學(xué)科和化學(xué)統(tǒng)計學(xué)中，近幾年被其他學(xué)科領(lǐng)域廣泛采用，包括數(shù)據(jù)挖掘和圖分析。張量作為高維數(shù)據(jù)( 多維數(shù)組) 的一種數(shù)學(xué)表示，一階和二階張量分別稱為向量和矩陣，張量的階為三或者更高則稱為高階張量，一個N階張量是n個矢量空間的乘積。比較典型的張量分解方法有Tucker分解方法、CP分解方法、HOSVD 分解方法等，CP模型在可解釋性、解的唯一性和參數(shù)的確定方面更有優(yōu)勢。

一個張量Z是由一系列切片組成，每個切片相當(dāng)于沿著時段T上的鄰接矩陣。一個三維CP張量Z可以表示秩1張量之和形式，如圖2所示，即向量ak，bk，ck間的外積與權(quán)重λk相乘之后的連加和：

(1)

圖2 三階張量的CP分解

其中° 表示外積，k為秩1要素的數(shù)量，k=1, …, K。λk∈R+，ak∈RM，bk∈RM，ck∈RM，每個被加數(shù)λk(ak° bk° ck)為一個要素，每個向量為一個因子，每個因子矩陣成為來自秩1要素的向量的組合。向量ak，bk，ck進行標(biāo)準(zhǔn)化，假定||ak||=||bk||=||ck||=1，則λk包含了第k個分量的權(quán)重。

(2)

3 鏈接預(yù)測方法

3.1 三維張量轉(zhuǎn)化二維矩陣

首先把數(shù)據(jù)存入張量Z，則切片Zt(i, j)表示時間段[tD, (t+1)D]上頂點對i和j之間的鏈接狀態(tài)，如果在時間D上鏈接存在，則為Zt(i, j)=1，否則為0。張量是由一系列Z1到ZT間的鄰接矩陣組成，其中下標(biāo)為時段。為了把數(shù)據(jù)轉(zhuǎn)換為矩陣X，引入權(quán)重θ∈(0, 1)，鏈接結(jié)構(gòu)考慮時間越近的鄰接矩陣，權(quán)重越大，則得到公式：

(3)

本文鏈接預(yù)測方法考慮了具有時間因素矩陣中捕獲的時間趨勢的多重網(wǎng)絡(luò)快照，其中時間趨勢由張量分解獲取，采用Holt-Winters方法[10]用來獲取張量的時間序列數(shù)據(jù)。時間序列數(shù)據(jù)由xt表示，st為x的下一個輸出值。序列在時間t=0開始，指數(shù)平滑法的最簡單形式如下表達(dá)式：

s1=x0

st+1=axt+(1-a)st

(4)

a為平滑因子(0

st+1=axt+(1-a)st=axt+a(1-a)st-1+(1-a)2st-2= axt+a(1-a)st-1+a(1-a)2st-2+…+(1-a)ts0

(5)

從方程3和5可以推導(dǎo)出，預(yù)測向量Zt+1用公式表示為：

Zt+1=aZt+a(1-a)Zt-1+a(1-a)2Zt-2+…+(1-a)tZ0

(6)

Zt+1為加權(quán)二維矩陣，Zt+1(i,j)表示節(jié)點i和j在T+1時刻的鏈接關(guān)系。

3.2 局部路徑鏈接預(yù)測

基于路徑的鏈接預(yù)測相似性指標(biāo)有LP指標(biāo)(Local Path，局部路徑)、Katz指標(biāo)等。LP是在共同鄰居指標(biāo)的基礎(chǔ)上考慮三階鄰居的貢獻(xiàn)，比CN視野更廣，提供了較好的精度和復(fù)雜度平衡，是一個比全局測量復(fù)雜度相對更低的局部測量。定義如下：

Si,j=A2+εA3

(7)

其中Si, j表示節(jié)點i和j相似度分?jǐn)?shù)，值越大，則節(jié)點間存在鏈接可能性越大。A為網(wǎng)絡(luò)的鄰接矩陣，A等價于前文3.1節(jié)中的Zt+1，A(i, j)則為節(jié)點i和j在時間t+1時刻的鏈接關(guān)系。當(dāng)節(jié)點i和j之間存在鏈接，則Ai,j=1，否則為0。(A3)xy等于節(jié)點x和y間長度為3的不同路徑數(shù)量。ε是一個可調(diào)節(jié)參數(shù)，用于控制三階路徑的作用，取值為接近于0的很小數(shù)字，通過調(diào)節(jié)ε的值可以獲取最高精確度的最優(yōu)值，對于不同的網(wǎng)絡(luò)，最優(yōu)值取值不同。當(dāng)ε=0而且x和y不是直接鏈接時，此測量方法退化為CN。

4 實驗與評價

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

為了驗證所提出的動態(tài)網(wǎng)絡(luò)鏈接預(yù)測算法的性能，本文采用兩個合著關(guān)系網(wǎng)絡(luò)數(shù)據(jù)集作為實驗數(shù)據(jù)，分別是hep-lat(high energy physics-lattice)和hep-th(High Energy Physics-Theory)，數(shù)據(jù)集來自于大型的科技論文數(shù)據(jù)庫e-print arXiv1，這種網(wǎng)絡(luò)關(guān)系數(shù)據(jù)廣泛地應(yīng)用于復(fù)雜網(wǎng)絡(luò)的動態(tài)結(jié)構(gòu)研究，實驗結(jié)果與CN、AA以及EVtCF鏈接預(yù)測算法進行對比。每個作者作為一個節(jié)點，兩個作者之間若有論文合作關(guān)系則建立一條邊，則表示有鏈接存在。實驗抽取了1992～2010年間的合著關(guān)系數(shù)據(jù)，以年為粒度建立合著網(wǎng)絡(luò)。相關(guān)數(shù)據(jù)信息如表1所示。

表1 合著關(guān)系網(wǎng)絡(luò)

對數(shù)據(jù)集使用移動窗口切片方法，把數(shù)據(jù)劃分成訓(xùn)練集和測試集，其中每個訓(xùn)練集包含T=10年的數(shù)據(jù)，相對應(yīng)的測試集包含接下來的T+1年也就是第11年數(shù)據(jù)。訓(xùn)練集中僅保留那些至少10篇出版物的作者(也就是平均下來每年一篇)，每條論文合著記錄表示兩個作者在相應(yīng)時間點存在鏈接。

4.2 實驗結(jié)果與分析

實驗使用Matlab 2012a軟件，Intel Core i5-4560處理器，32G內(nèi)存。實驗使用AUC[9](Area Under the Receiver Operating Characteristic Curve)指標(biāo)來衡量算法精確性，從動態(tài)科技論文合著網(wǎng)絡(luò)中抽取不同時刻數(shù)據(jù)構(gòu)成不同規(guī)模的網(wǎng)絡(luò)，每次選取T=10年的數(shù)據(jù)作為訓(xùn)練集，以T+1年數(shù)據(jù)為測試集數(shù)據(jù)計算1次AUC值，然后時間窗口往后移動一年，進行下一次AUC值計算，最后對所有AUC值取平均作為對應(yīng)時間窗口T取值的鏈接預(yù)測方法的AUC值。

根據(jù)訓(xùn)練集上初步測試以及文獻(xiàn)資料，設(shè)定參數(shù)θ=0.2，ε=0.01，本文方法和其他經(jīng)典算法CN、Katz、EVtCF對比實驗結(jié)果如上圖3所示。從圖3可以看出，本文方法在hep-lat數(shù)據(jù)集上表現(xiàn)最好，在hep-th數(shù)據(jù)集上表現(xiàn)僅次于EVtCF算法。

圖3 鏈接預(yù)測實驗效果

5 結(jié)論

本文主要針對靜態(tài)網(wǎng)絡(luò)忽視網(wǎng)絡(luò)演化趨勢信息的問題，提出了一種基于動態(tài)網(wǎng)絡(luò)的鏈接預(yù)測方法，采用張量分析及Hold-Winters方法，結(jié)合局部鏈接預(yù)測方法，以兩個真實動態(tài)網(wǎng)絡(luò)數(shù)據(jù)集進行了實驗，實驗結(jié)果表面，新算法在預(yù)測精度方面有所提高。當(dāng)然，隨著復(fù)雜網(wǎng)絡(luò)的高速發(fā)展，復(fù)雜網(wǎng)絡(luò)隨著時間而不斷演化發(fā)展趨勢及預(yù)測仍有待更進一步的深入研究。

[1]陳小強，周麗華，程超，等．動態(tài)網(wǎng)絡(luò)中穩(wěn)定社區(qū)發(fā)現(xiàn)[J]．小型微型計算機系統(tǒng)，2015，36(9)：1977-1981．

[2]高琳，楊建業(yè)，覃桂敏．動態(tài)網(wǎng)絡(luò)模式挖掘方法及其應(yīng)用[J]．軟件學(xué)報，2013，24(9)：2042-2061．

[3]Shan B, Jiang S X, Zhang S, et al. IC: Incremental algorithm for community identification in dynamic social networks[J]. Journal of Software, 2009(20): 184-192.

[4]李艷梅，李川，唐常杰，等．動態(tài)信息網(wǎng)絡(luò)中的角色演化異常及其發(fā)現(xiàn)[J]．計算機科學(xué)與探索，2015，9(3)：321-329．

[5]李曉東，崔麗娟．大學(xué)生網(wǎng)絡(luò)交往動機與網(wǎng)絡(luò)行為特點關(guān)系研究綜述[J]．安徽科技學(xué)院學(xué)報，2011，25(1)：104-106．

[6]AGGARWAL C, SUBBIAN K. Evolutionary network analysis: a survey[J]. ACM Computing Surveys, 2014, 47(1): 1-35.

[7]ZHAO Qi-bin, ZHANG Li-qing, CICHOCKI A. Bayesian CP factorization of incomplete tensors with automatic rank determination[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(9): 1751-1763.

[8]LUE L, JIN Ci-hang, ZHOU Tao. Similarity index based on local paths for Link prediction of complex networks[J]. Physical Review E, 2009, 80(4): 1-9.

[9]Mangal D, Sett N, Singh S R, et al. Link prediction on evolving social network using spectral analysis[C]. Advanced Networks and Telecommunications Systems (ANTS), 2013 IEEE International Conference on. IEEE, 2013: 1-6.

[10]MASMOUDI M, EL B K, LOUKIL A, et al. Real-Time prediction of RTT based on Holt-Winters method for Internet-BasedTeleoperation[J]. International Review on Computers and Software(IRECOS), 2015, 10(1): 72-79.

(責(zé)任編輯：李孟良)

Research On Link Analysis and Prediction Based On Dynamic Network

YANG Lei1,2，LI Chen-long1,2

(1．Coll. of Comp. Info., Anhui Polytechnic University, Wuhu 241000，China;2．Key Laboratory of Computer Application Technology, Anhui Polytechnic University, Wuhu 241000, China)

Complex networks evolve rapidly over time by adding new nodes and new links, and it is difficult to get an accurate prediction by using the static characteristics of networks. By analyzing the dynamic characteristics of the networks, according to the tensor factorization theory, a new method of link prediction based on dynamic network is proposed, which is applied to the real complex dynamic network data for link analysis and prediction, The experiment demonstrates the advantages and effectiveness of this method, which achieves good prediction performance.

Link prediction; Dynamic network; Tensor factorization; Local path

2016-04-16

安徽省高等教育提升計劃省級自然科學(xué)研究一般項目(TSKJ2015B20)；安徽工程大學(xué)計算機應(yīng)用技術(shù)重點實驗室開放基金項目(JSJKF201515)；安徽工程大學(xué)校青年基金項目(2009YQ040)。

楊磊(1982-)，男，安徽省臨泉縣人，碩士，講師，主要從事數(shù)據(jù)挖掘研究。

TP391

A

1673-8772(2016)05-0062-05