朱宇航 劉樹新 吉立新 何贊園 李英樂

(中國人民解放軍戰(zhàn)略支援部隊信息工程大學信息技術(shù)研究所 鄭州 450002)

1 引言

自然界中一切事物都是運動的，現(xiàn)實世界中的各種復雜網(wǎng)絡(luò)也都是隨著時間變化而不停演化的動態(tài)網(wǎng)絡(luò)，如航空交通運輸網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、文獻引用網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、社交推薦網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)等等，這些真實網(wǎng)絡(luò)都可以抽象成為一個個由節(jié)點和連邊組成的動態(tài)時序復雜網(wǎng)絡(luò)。挖掘節(jié)點與節(jié)點之間、連邊與連邊之間的相互作用，分析動態(tài)網(wǎng)絡(luò)的演化規(guī)律，預測網(wǎng)絡(luò)的變化情況，對研究網(wǎng)絡(luò)科學和復雜系統(tǒng)具有重要意義。鏈路預測作為研究復雜科學的重要技術(shù)之一，已成為近年來的研究熱點問題[1,2]。

鏈路預測是挖掘網(wǎng)絡(luò)數(shù)據(jù)之間潛在關(guān)系的一種重要方法，原理就是利用已知的網(wǎng)絡(luò)節(jié)點屬性、連邊屬性和拓撲結(jié)構(gòu)等信息，預測網(wǎng)絡(luò)中未連接節(jié)點之間產(chǎn)生連邊的可能性[3]?；凇芭笥训呐笥押芸赡芤彩桥笥选钡纫?guī)律，最常用的鏈路預測指標包括CN(Common Neighbors)，AA(Adamic-Adar)，RA(Resource Allocation)，PA(Preferential Attachment)，LP(Local Path)，Katz等[4]。近年來，許多學者對預測指標的優(yōu)化開展了大量的研究工作，李治成等人[5]利用節(jié)點的拓撲穩(wěn)定性對相似性指標進行了優(yōu)化；王凱等人[6]對信息在傳輸路徑上的有效性進行了刻畫，優(yōu)化了RA指標；劉樹新等人[7]從資源傳輸匹配的角度對資源雙向傳輸進行了準確量化。在靜態(tài)網(wǎng)絡(luò)鏈路預測的基礎(chǔ)上，時序鏈路預測利用每一個時刻的靜態(tài)預測指標，結(jié)合時間序列分析的方法，實現(xiàn)對動態(tài)時序網(wǎng)絡(luò)的分析。最樸素的思路就是對所有時刻圖的特征建立總體平均模型[8]，即利用每一時刻相似度特征的平均值去預測下一時刻的情況。Huang等人[9]將時間序列應(yīng)用到鏈路預測中，計算網(wǎng)絡(luò)中所有節(jié)點對在每一個時刻相似性分數(shù)的時間序列矩陣，結(jié)果表明，引入時間序列的動態(tài)算法性能優(yōu)于傳統(tǒng)的靜態(tài)算法。Güne?等人[10]將靜態(tài)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)相似性指標與ARIMA(Autoregressive Integrated Moving Average model)模型進行融合，提出的時序鏈路預測算法取得了良好的實驗結(jié)果。劉繼嘉等人[11]利用LR(Liner Regression)線性回歸模型對改進相似性特征的時間序列進行建模，實現(xiàn)了對動態(tài)網(wǎng)絡(luò)不錯的預測效果。

上述方法從時間序列分析的角度進行分析，未考慮網(wǎng)絡(luò)演化過程對網(wǎng)絡(luò)本身的影響，許多學者在計算歷史時刻圖信息特征的基礎(chǔ)上，增加不同的網(wǎng)絡(luò)演化規(guī)律方面的特征，提出了精度更高的時序鏈路預測算法。如Munasinghe等人[12]認為節(jié)點對之間的相互作用會隨時間發(fā)生變化，如果近期兩個節(jié)點與它們的共同鄰居之間的連邊越多，那么未來這兩個節(jié)點間發(fā)生連邊的概率也會變大。Zhang等人[13]利用基于隱藏空間模型的方法，把共同鄰居的關(guān)系映射到隱藏空間，在隱藏空間中的距離越近的節(jié)點對，產(chǎn)生連接的可能性更大。鄧志宏等人[14]以傳統(tǒng)的結(jié)構(gòu)相似性算法為基礎(chǔ)，提出了基于誤差修正的時序網(wǎng)絡(luò)鏈路預測算法，取得了較好的預測結(jié)果。Bliss等人[15]通過協(xié)方差矩陣自適應(yīng)演化策略對相似性指標進行了優(yōu)化，在Twitter數(shù)據(jù)集中取得較好的精確度。這些時序鏈路預測算法雖然有效地利用了時間信息，但它們只考慮了局部連邊的網(wǎng)絡(luò)演化規(guī)律，對網(wǎng)絡(luò)拓撲結(jié)構(gòu)的特性挖掘有限。因此，可以進一步挖掘網(wǎng)絡(luò)微觀結(jié)構(gòu)在演化過程中節(jié)點變化和連邊變化的影響力演化模型。

此外，還有很多學者從網(wǎng)絡(luò)動力學的角度，對網(wǎng)絡(luò)的離散性、動態(tài)性、自適應(yīng)和高階特征等方面開展了相關(guān)研究，提出了基于線性方程[16]、基于壓縮感知[17]、基于相位同步[18]、基于霍克斯過程[19]等模型，這些模型都把網(wǎng)絡(luò)演化過程抽象成不同的非線性迭代訓練過程，但這些模型要么僅對稀疏連邊的演化進行建模，要么僅對連邊變化映射相位的演化進行建模，要么僅對節(jié)點事件的演化進行建模。這些模型的應(yīng)用場景比較單一，如線性方程和壓縮感知的方法大多把時序網(wǎng)絡(luò)轉(zhuǎn)換成線性系統(tǒng)，相位同步模型的方法更適應(yīng)馬爾可夫網(wǎng)絡(luò)，對記憶網(wǎng)絡(luò)的效果不好，基于霍克斯過程的模型大多針對節(jié)點的演化信息進行擬合，而忽略了網(wǎng)絡(luò)結(jié)構(gòu)的其他信息對網(wǎng)絡(luò)演化的影響，也沒有對各類特征的融合進行建模研究。

基于以上分析，本文首先從研究這些模型的迭代規(guī)律入手，認為網(wǎng)絡(luò)自身的本質(zhì)特征是網(wǎng)絡(luò)全局長期的影響效果，把網(wǎng)絡(luò)拓撲演化過程中節(jié)點、連邊的自相關(guān)和協(xié)相關(guān)定義為局部影響，再加上噪聲的因素，提出一種基于拓撲結(jié)構(gòu)影響力的時序鏈路預測算法的通用模型 (Common Temporal Link Prediction Model, CTLPM)；其次，在僅考慮拓撲局部影響的情況下，利用節(jié)點和連邊在時序動態(tài)網(wǎng)絡(luò)上的演化規(guī)律，給出了融合局部拓撲影響力的時序鏈路預測算法 (Temporal Link Prediction base on Fusion Local Structure Influence, TLP-FLSI)；最后，在7個真實數(shù)據(jù)集上分步驟進行實驗，考察節(jié)點和連邊作用的權(quán)重比例，直接影響力和間接影響力的作用優(yōu)先順序，并且與經(jīng)典時序算法進行預測性能對比，實驗結(jié)果表明了TLP-FLSI算法的可行性和有效性。

2 問題描述及評價指標

常見的動態(tài)網(wǎng)絡(luò)建模方式是根據(jù)時序?qū)?shù)據(jù)進行等間隔切分，把動態(tài)網(wǎng)絡(luò)分解為一系列的時間快照圖集合，這樣的建模方式相當于對動態(tài)網(wǎng)絡(luò)在時間維度上進行采樣，將動態(tài)網(wǎng)絡(luò)拆分成多個靜態(tài)網(wǎng)絡(luò)序列，使得靜態(tài)網(wǎng)絡(luò)的預測算法能夠適用于動態(tài)網(wǎng)絡(luò)的處理。

復雜網(wǎng)絡(luò)通常以圖的形式進行描述，靜態(tài)網(wǎng)絡(luò)通常用G=(V,E)表示，其中V={v1,v2,...,vN}表示節(jié)點集合；N=|V|表示網(wǎng)絡(luò)中節(jié)點數(shù)量；E ?V×V表示節(jié)點集合中任意兩個節(jié)點連接構(gòu)成的集合(有向或無向)，E={eij|i,j=1,2,...,N}，eij表示節(jié)點間連接關(guān)系緊密度，即邊的權(quán)重，如果邊不存在，eij=0，如果是無權(quán)圖，則eij始終為1，如果節(jié)點對之間是多種關(guān)系，則eij可以用向量進行表示。

動態(tài)時序網(wǎng)絡(luò)在t (0

時序鏈路預測是指利用動態(tài)網(wǎng)絡(luò)的歷史快照數(shù)據(jù)G={G1,G2,...,GT}，預測GT+1的網(wǎng)絡(luò)拓撲分布。如圖1(b)所示，通過時刻1到時刻T的數(shù)據(jù)作為訓練集合進行建模分析，進而實現(xiàn)對t=T+1時刻的鏈路預測。

時序鏈路預測的評價指標與靜態(tài)鏈路預測相同，也可以采用AUC(Area Under Curve)指標和RS(Ranking Score)指標[20]對預測結(jié)果進行評價。兩種指標考慮的著重點不一樣，其中，AUC 是最常用的一種評價指標，它能從整體衡量算法的精確度，而RS則更多地考慮了所預測的邊的排序。

3 算法設(shè)計

首先給出時序鏈路預測通用模型的定義，在此模型基礎(chǔ)上提出基于融合局部拓撲影響力的時序鏈路預測算法，并對節(jié)點和連邊的歷史信息與演化信息進行分析。

3.1 基于網(wǎng)絡(luò)拓撲影響力的通用時序鏈路預測模型

網(wǎng)絡(luò)拓撲的影響力包括全局影響和局部影響，局部影響又可以分為直接影響和間接影響。全局影響力可以衡量拓撲對網(wǎng)絡(luò)整體的重要性，如中心性指標可用于表示節(jié)點和連邊的全局重要性，特征向量指標可用于刻畫網(wǎng)絡(luò)產(chǎn)生的長期影響；在網(wǎng)絡(luò)動態(tài)變化時，對于網(wǎng)絡(luò)中的一個個實體來說，只有與它有關(guān)系的節(jié)點和連邊才會在相鄰的一個時刻產(chǎn)生短期影響，節(jié)點度指標便可以衡量節(jié)點的直接影響力，緊密度指標則可以衡量節(jié)點的間接影響力；另外，對時序序列數(shù)據(jù)進行建模時，還需要考慮噪聲和時間衰減變化等因素。因此，發(fā)生于T 時刻的新事件不僅受網(wǎng)絡(luò)的全局和局部拓撲結(jié)構(gòu)的影響，還受之前時刻的歷史事件影響。由此，對于時序動態(tài)網(wǎng)絡(luò)的預測，給出預測未來時刻得分矩陣函數(shù)的通用模型(CTLPM)為

全局影響力可以使用網(wǎng)絡(luò)中節(jié)點或邊的各類中心性指標進行度量。節(jié)點的度中心性指標可以更準確地表示它對鄰居的影響力，不同網(wǎng)絡(luò)的節(jié)點即使度相同，由于網(wǎng)絡(luò)整體的最大度不同，它們對鄰居節(jié)點的影響力也不同；介數(shù)中心性利用通過連邊的最短路徑數(shù)量表示該連邊和在該連邊上節(jié)點的重要性，如網(wǎng)絡(luò)中2個社團之間的連邊要比社團之間的連邊的重要性更大；特征向量中心性可以表征為節(jié)點中心性的函數(shù)，與節(jié)點連接的鄰居越重要，該節(jié)點就越重要。不同類型的網(wǎng)絡(luò)往往具有不同的特色演化規(guī)律，可以挑選合適的中心性指標進行度量。

局部影響力可以考慮網(wǎng)絡(luò)拓撲中節(jié)點和連邊在局部范圍內(nèi)的結(jié)構(gòu)特征進行融合表示，可以用節(jié)點和連邊的相似性，以及演化過程中的相關(guān)性進行度量。對于t時刻的節(jié)點i和j的局部影響力計算為

(1) 首先計算網(wǎng)絡(luò)中每一個節(jié)點的影響力度量、連邊的相似性度量以及它們的自相關(guān)度量，并分別得到網(wǎng)絡(luò)的度量矩陣；

(2) 使用矩陣的自身數(shù)值與矩陣最大數(shù)值的比值作為最終的度量得分，如式(7)所示，實現(xiàn)對節(jié)點對局部影響力的歸一化。其中，V為網(wǎng)絡(luò)在t時刻的節(jié)點集合。

3.2 融合局部拓撲影響力的時序鏈路預測算法

對大規(guī)模網(wǎng)絡(luò)計算全局特征的成本較高，進一步只考慮融合局部拓撲影響力的作用，這樣可以大大減低計算的復雜度，給出一種融合局部拓撲影響力的時序鏈路預測指標，記作TLP-FLSI，具體計算如式(11)，它與通用模型的關(guān)系如圖2所示

圖2 TLP-FLSI與CTLPM的關(guān)系圖

定義FLSI-III為考慮連邊和連邊協(xié)相關(guān)因素的

步驟3 計算連邊的局部影響力的演化因子，根據(jù)連邊的1階和2階相似度特征，得到連邊的局部拓撲影響力得分、連邊局部介數(shù)的變化比值，并對得分進行歸一化；

步驟4 把節(jié)點和連邊的演化因子按照不同的權(quán)重進行求和，得到融合特征的相似度分值；

步驟5 按照時序演化因子，分別按照線性衰減、泊松衰減、指數(shù)衰減這3種模型，在時間長度p內(nèi)，得到該時刻經(jīng)過時序衰減后的最終相似度分值；

步驟6 返回步驟2，計算下一時刻相似度分值，與之前的總分值進行迭代運算后，得到算法的最終相似度得分值。

下面將分別對節(jié)點、連邊的局部拓撲影響力的演化因子，以及時間序列分布衰減的演化因子展開進一步的分析。

3.2.1 基于節(jié)點局部影響力的演化因子

首先對節(jié)點的局部影響力進行分析，如果要預測下一時刻兩個節(jié)點之間存在連邊關(guān)系，必要條件是需要保證這兩個節(jié)點存在，因此，可以認為節(jié)點存在的概率越大，連邊存在的概率也就越大。鏈路預測問題可以從節(jié)點存在的概率這一角度進行分析，t時刻一個節(jié)點對的局部影響力就等于各自節(jié)點影響力之和，具體為

根據(jù)網(wǎng)絡(luò)類型的不同，可以從多個角度去定義節(jié)點的影響力。一般而言，前一時刻節(jié)點存在的連接關(guān)系越多，下一時刻節(jié)點存在的概率越大，通常利用節(jié)點的度指標來表征節(jié)點的直接影響力，在社交網(wǎng)絡(luò)中表示此節(jié)點的直接社會關(guān)系；利用節(jié)點的拓撲緊密性的指標來表征節(jié)點的間接影響力，在社交網(wǎng)絡(luò)中表示此節(jié)點的間接社會關(guān)系。圖3(a)為利用節(jié)點度進行影響力演化的示意圖，因為只利用目標節(jié)點對中兩個節(jié)點自身的直接影響力進行演化，基于節(jié)點度數(shù)表征節(jié)點對的局部影響力的FLSI-I(1)指標具體為

其中，λ1和λ2分別表示1階和2階基于度數(shù)的局部作用系數(shù)，z表示節(jié)點i和節(jié)點j的共同鄰居。

另外，還可以從節(jié)點的拓撲緊密性方面對節(jié)點的局部影響力進行設(shè)計，如果一個節(jié)點對的共同鄰居形成的三角閉合關(guān)系越多，說明節(jié)點對的拓撲越穩(wěn)定，在下一時刻存在的概率越大。如圖3(b)所示，以T 時刻為例，節(jié)點i和節(jié)點j的共同鄰居z1,z2, z3之間的連接關(guān)系(z1,z2), (z1,z3), (z2,z3)，這3條邊都會與節(jié)點i和節(jié)點j共同形成了三角閉合關(guān)系，利用這種三角拓撲的分布情況，基于拓撲緊密度表征節(jié)點對的局部影響力的FLSI-I(2)指標具體為

圖3 節(jié)點局部影響力演化示意圖

3.2.2 基于連邊局部影響力的演化因子

在靜態(tài)網(wǎng)絡(luò)鏈路預測的方法中，對節(jié)點對的連邊關(guān)系的預測也可以轉(zhuǎn)化為對其拓撲結(jié)構(gòu)中路徑信息的相似性判決問題。如LP指標就考慮了有限的3階路徑長度，它的定義為

其中，A表示網(wǎng)絡(luò)的鄰接矩陣，λ為調(diào)節(jié)參數(shù)，S是最終的得分預測矩陣。而Katz指標把節(jié)點i和節(jié)點j之間的全局所有路徑都考慮進來，定義為

該思路利用了真實路徑和虛擬路徑對資源分配的共同作用，那么在動態(tài)網(wǎng)絡(luò)中對路徑的影響力進行綜合考慮，可以把動態(tài)網(wǎng)絡(luò)在每一時刻的路徑影響都進行計算。如圖4所示，不僅要考慮節(jié)點i和j之間的連邊變化情況，還要考慮它們與共同鄰居之間連邊的變化情況。

圖4 連邊局部影響力演化示意圖

無向網(wǎng)絡(luò)連邊的1階相似性是指有連邊存在的節(jié)點對之間的相似性[22]，主要由連邊的權(quán)重決定，沒有連邊的節(jié)點對之間的相似性為0，2階相似性是指節(jié)點的鄰近網(wǎng)絡(luò)結(jié)構(gòu)的相似性，若節(jié)點間沒有共同的1階鄰居，則2階相似性為0。針對動態(tài)網(wǎng)絡(luò)的某一時刻t，考慮1階路徑和2階路徑的結(jié)構(gòu)作用，基于連邊局部影響力的FLSI-II指標具體為

在連邊局部影響的基礎(chǔ)上，考慮連邊的自相關(guān)演化因素為相鄰時刻連邊的局部介數(shù)的比值，連邊的協(xié)相關(guān)演化因素為在不同時刻的虛擬2階路徑，得到FLSI-III指標具體定義為

3.2.3 基于時序衰減的影響力演化因子

網(wǎng)絡(luò)拓撲的節(jié)點和連邊可以抽象成一個個事件，這些事件可以組成時間序列數(shù)據(jù)。時間序列的模型一般可以分為加法模型、乘法模型和混合模型。對應(yīng)這3種模型，可以擬合成線性分布、長尾分布、鐘擺分布這3種概率分布模型，如圖5所示。

圖5 影響力時序演化示意圖

假設(shè)拓撲影響力按照線性分布進行演化，事件的影響力隨時間變化按照固定大小進行線性衰減。

假設(shè)拓撲影響力按照長尾分布進行演化，事件的影響力隨時間變化按照先急劇下降，再緩慢下降的模型進行衰減，本文用指數(shù)衰減來擬合長尾分布的時序演化場景。

假設(shè)拓撲影響力按照鐘擺分布進行演化，很多熱點事件影響力衰減的情景是符合鐘擺分布模型，事件發(fā)生后影響力在均值時間前是上升的，之后再進行下降的衰減。本文用泊松變化來擬合鐘擺分布的時序演化場景。

4 實驗驗證

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

本文采用7個通信社交網(wǎng)絡(luò)數(shù)據(jù)集對算法性能進行評估。Email數(shù)據(jù)集[23]是某大型歐洲研究機構(gòu)從2003年10月到2005年5月的電子郵件數(shù)據(jù)生成的；Enron數(shù)據(jù)集[24]由Enron公司從2001年1月到2002年3月雇員之間發(fā)送的電子郵件數(shù)據(jù)組成；Facebook數(shù)據(jù)集[25]包含了從2006年11月到2009年1月用戶在另一個用戶墻上留言的交流記錄；DNC數(shù)據(jù)集[26]由2016年5月美國民主黨全國委員會郵件泄露事件中采集的郵件往來網(wǎng)絡(luò)，其節(jié)點表示郵件賬號，連邊表示某賬號發(fā)往另一賬號的郵件；MAN數(shù)據(jù)集[26]是某制造業(yè)工廠內(nèi)部員工的郵件往來網(wǎng)絡(luò)，包括2010年1月至10月的郵件數(shù)據(jù)；UCI數(shù)據(jù)集[27]由加州大學歐文分校的學生之間傳遞的短信構(gòu)成的在線社交網(wǎng)絡(luò)，選用2014年7月至11月的連邊構(gòu)建數(shù)據(jù)集；LEM數(shù)據(jù)集[28]由堪薩斯事件數(shù)據(jù)系統(tǒng)基于包含WEIS編碼事件的文件夾收集的交互網(wǎng)絡(luò)，涵蓋了1979年4月至2004年6月內(nèi)的事件，各數(shù)據(jù)集參數(shù)如表1所示。

表1 數(shù)據(jù)集參數(shù)表

4.2 實驗對比算法

(1)基于最近時刻算法[8]：利用馬爾可夫網(wǎng)絡(luò)的思想，假設(shè)每一個時刻僅與最近的一個相鄰時刻有關(guān)，只使用網(wǎng)絡(luò)最近一個時刻的相似度指標進行預測的方法，記作Last。

(2)移動平均時序算法[10]：利用移動范圍內(nèi)每一個訓練時間快照的相似性指標的均值進行度量的方法，記作AV，如果移動范圍為預測之前的全部窗口，則算法等價為總體平均算法，如果移動范圍僅為預測之前的1個窗口，則算法等價為最近時刻算法。

(3)基于鄰居擴展指標的時序鏈路預測算法[10]：基于鄰居擴展指標的方法對時序網(wǎng)絡(luò)數(shù)據(jù)進行分段加權(quán)處理的同時，基于距離越近，作用越大的原理，再結(jié)合指數(shù)函數(shù)表征時間的衰減作用，記作TS-W。

(4)基于有效增量的時序鏈路預測算法[13]：該方法僅對時序網(wǎng)絡(luò)中的節(jié)點增量和增量節(jié)點對應(yīng)的鄰居重新計算影響力得分，由于只考慮了2階條件下的節(jié)點增量更新處理，使得減小了計算復雜度的同時，也能獲取不錯的檢測精度，記作TLP-I。

(5)基于誤差修正的時序鏈路預測算法[14]：將每一個時刻的預測分值與連接關(guān)系之差為預測誤差，再計算相鄰時刻的誤差的偏移，進而融合得到最終的誤差預估矩陣，把最后一刻的預測進行最終誤差修正后得到預測得分，記作LPE。

(6)基于概略圖的算法[29]：把移動范圍內(nèi)所有時刻快照圖疊加成為一個有權(quán)靜態(tài)圖的方法，記作Reduce。該方法把有權(quán)靜態(tài)圖當作最近鄰時刻圖進行訓練，實現(xiàn)對下一時刻的預測。

(7)基于節(jié)點匹配度的時序鏈路預測算法[30]：該方法在兩級拓撲結(jié)構(gòu)中，利用節(jié)點三角形閉合數(shù)量和節(jié)點度共同定義節(jié)點的重要性，利用指數(shù)衰減對時序作用進行擬合，記作TMDN。

(8)基于自注意力機制實現(xiàn)的圖嵌入模型算法[31]：利用網(wǎng)絡(luò)拓撲自注意力聚合網(wǎng)絡(luò)快照中各節(jié)點的結(jié)構(gòu)特征，利用多頭注意力機制捕捉網(wǎng)絡(luò)快照之間的演化特性，記作DySAT。

(9)基于圖注意力網(wǎng)絡(luò)的動態(tài)鏈路預測方法[32]：利用圖注意力網(wǎng)絡(luò)提取靜態(tài)網(wǎng)絡(luò)快照中的結(jié)構(gòu)特征，隨后利用門控循環(huán)單元提取網(wǎng)絡(luò)快照序列中的時序演化特征，并結(jié)合自注意力機制聚焦重要的網(wǎng)絡(luò)快照，利用生成的圖嵌入向量實現(xiàn)對未來連邊可能性的評估，記作TASM。

4.3 實驗結(jié)果分析

4.3.1 性能對比分析

實驗初始設(shè)置如下：設(shè)定訓練時長p=7，即固定利用預測時刻的前7個時刻的網(wǎng)絡(luò)數(shù)據(jù)進行訓練；設(shè)定λ1=λ2=1，即考慮節(jié)點和連邊的1階影響和2階影響相同；設(shè)定線性時序衰減d=1/7；指數(shù)時序衰減因子d=0.8，則指數(shù)的時序衰減為(0.8)T ?t，t為距離T 時刻的時間間隔數(shù)量；設(shè)定泊松時序分布的均值為2。

對本文提出的FLSI-I, FLSI-II和FLSI-III算法，首先計算節(jié)點和連邊的局部影響力演化因子后，再進行線性、指數(shù)、泊松時序衰減變化，其中，F(xiàn)LSI-I(1)采用節(jié)點度數(shù)計算節(jié)點的局部影響力，F(xiàn)LSI-I(2)采用節(jié)點的集聚系數(shù)計算節(jié)點的局部影響力。Last,AV, Reduce, LPE, TS-W, TLP-I, TMDN這7種模型分別使用CN, AA, RA, JC等幾種相似性指標進行的時序模型運算，以及對比DySAT, TASM這2種基于圖注意力網(wǎng)絡(luò)的方法，并且對連續(xù)多個時刻進行預測取得平均值后，對它們的AUC值進行對比，實驗結(jié)果如表2所示。

表2 不同方法的平均AUC性能結(jié)果

首先對比FLSI方法與其他方法，在Facebook數(shù)據(jù)集中FLSI方法比DySAT和TASM的效果差，但是對比7種基于結(jié)構(gòu)相似性的時序方法仍然取得了相對較好的效果；在其他6個數(shù)據(jù)集中FLSI都取得了更好的預測效果，3類FLSI方法的效果比其他模型的AUC性能有明顯提升，平均提升的幅度在1%～8%。

然后對比3類FLSI方法的效果，總體上看，在幾個網(wǎng)絡(luò)數(shù)據(jù)集中，其中FLSI-II的效果最好。對比基于節(jié)點度的FLSI-I(1)方法比基于節(jié)點緊密度的FLSI-I(2)方法，在Email, DNC和LEM這3個數(shù)據(jù)集中效果相差不大，說明在前5個數(shù)據(jù)集中的節(jié)點直接影響力和節(jié)點的間接影響力的作用差不多，在Enron, Facebook和UCI網(wǎng)絡(luò)中FLSI-I(2)的效果不好，說明這時節(jié)點的直接影響力比間接影響力的作用大很多，在MAN數(shù)據(jù)集中則正好相反；除了MAN數(shù)據(jù)集，在其他6個數(shù)據(jù)集中FLSI-II和FLSI-III方法的效果優(yōu)于FLSI-I方法，說明在這幾個數(shù)據(jù)集中利用連邊信息比節(jié)點信息的效果更好；FLSI-III比FLSI-II效果稍差一點，說明基于連邊的相關(guān)性因素雖然產(chǎn)生了一定的影響力，但由于與連邊的局部拓撲影響計算出現(xiàn)了一定的重復，所以產(chǎn)生了一些負面的作用。

對于RS評價標準來說，越低的RS值意味著鏈路預測方法對準確邊的排序越靠前，則表示預測性能越好。從圖6所示結(jié)果可以看出，與AUC結(jié)果相似，在大多數(shù)網(wǎng)絡(luò)中FLSI-II和FLSI-III指標的RS值相比其他方法取得了更好的效果；同時，除了FLSI-I(2)在Facebook和UCI數(shù)據(jù)集中的效果不好之外，F(xiàn)LSI-I的2種方法RS性能也比其他方法好。FLSI方法的平均RS性能在幾個數(shù)據(jù)集中提升幅度在1.5%～20%。

圖6 不同方法的平均RS性能對比圖

綜上所述，在AUC和RS衡量標準下，本文提出的TLP-FLSI方法的時序鏈路預測效果優(yōu)于采用移動均值、誤差修正或加權(quán)演化的基于結(jié)構(gòu)相似性預測算法效果，預測性能提升幅度顯著，實驗效果最好的是利用連邊影響的FLSI-II模型。FLSI模型較好地利用了網(wǎng)絡(luò)的拓撲結(jié)構(gòu)的歷史信息和網(wǎng)絡(luò)的動態(tài)演化信息，實現(xiàn)了更高的預測效果。在Facebook數(shù)據(jù)集中基于圖嵌入學習的2種預測方法效果最好，但對資源消耗有要求的復雜網(wǎng)絡(luò)分析場景時，F(xiàn)LSI方法具有更好的應(yīng)用價值。

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

由于FLSI-III的精度比FLSI-II的AUC效果稍差，在對局部影響力的調(diào)節(jié)系數(shù)進行敏感性測試時設(shè)置β=1?α, δ=0，觀察在只考慮節(jié)點和連邊對局部影響力發(fā)揮作用時，1階特征和2階特征對最終準確率的影響情況，觀察在7個數(shù)據(jù)集的實驗結(jié)果變化曲線，利用節(jié)點度與連邊影響力不同比例的變化記作KE方法，利用節(jié)點集聚系數(shù)與連邊影響力不同比例的變化記作CE方法；在α=1時，KE即是FLSI-I(1)方法，CE即是FLSI-I(2)方法。

步驟1 考慮直接影響力和間接影響力產(chǎn)生相同作用的情況，設(shè)置節(jié)點和連邊的1階和2階局部作用系數(shù)分別為λ1=λ2=1，在數(shù)據(jù)集中測試不同的權(quán)重參數(shù)α的比例，驗證對最終相似性得分的影響。實驗選取30次不同時刻的AUC平均值作為最終的結(jié)果進行對比，如圖7(a)—圖7(g)所示，從結(jié)果可以看出不同的權(quán)重值對AUC的影響，觀察到隨著權(quán)重參數(shù)的變化，AUC的值也在波動變化。在Email和MAN這2個數(shù)據(jù)集中，KE方法顯示上升波動，CE方法顯示下降波動，說明節(jié)點或連邊在不同場景下需要配置不同的比例，才能取得最好的效果；在Enron, Facebook, DNC和UCI中KE和CE方法的效果波動不大，只有CE方法在α=1時發(fā)生陡變，調(diào)節(jié)系數(shù)設(shè)置不大于0.9就可以得到較好的AUC值；在LEM數(shù)據(jù)集中，KE和CE方法的AUC結(jié)果隨著α的變化而波動，最優(yōu)的調(diào)節(jié)系數(shù)介于0和1之間，說明節(jié)點和連邊特征融合后共同對最終的AUC計算產(chǎn)生影響。

圖7 步驟1實驗權(quán)重參數(shù)影響的變化曲線

步驟2 設(shè)置連邊的局部作用系數(shù)分別為λ1=0,λ2=1，節(jié)點的局部作用系數(shù)仍為λ1=λ2=1時，此時連邊只有2階間接影響，實驗結(jié)果如圖8(a)—圖8(g)所示，在前5個數(shù)據(jù)集中都在α=0.1時精度產(chǎn)生了大幅提升，說明了節(jié)點產(chǎn)生的影響非常重要，此時，KE曲線比CE曲線得到的AUC得分更高，因為集聚系數(shù)表示鄰居節(jié)點的聚集程序，在網(wǎng)絡(luò)拓撲中距離需要預測的連邊更遠，說明在這5個真實社交網(wǎng)絡(luò)數(shù)據(jù)集中，節(jié)點的直接影響力比間接影響力要大，而在后2個數(shù)據(jù)集中則得到相反結(jié)論。

圖8 步驟2實驗權(quán)重參數(shù)影響的變化曲線

步驟3 設(shè)置節(jié)點和連邊都不考慮1階影響力的情況，即設(shè)置局部作用系數(shù)都為λ1=0,λ2=1，如圖9(a)—圖9(g)所示，可以看到在7個數(shù)據(jù)集中調(diào)節(jié)參數(shù)在不同位置時取得相應(yīng)的最優(yōu)AUC值，說明2階情況下，仍是節(jié)點和連邊特征融合共同作用能夠取得最優(yōu)值；同時，不考慮1階特征的情況下，AUC整體比前面2種情況要低，說明節(jié)點和連邊的1階特征具有重要的影響作用。

圖9 步驟3實驗權(quán)重參數(shù)影響的變化曲線

綜上所述，在采用FLSI方法針對通信社交類動態(tài)網(wǎng)絡(luò)進行時序預測分析時，距離待預測連邊的距離越近，拓撲實體所產(chǎn)生的影響力越大。連邊的1階信息表示待預測連邊在過去時刻的存在情況，可以看成與待預測連邊的距離為0；待預測連邊的兩側(cè)節(jié)點的距離次之，它們的影響力僅次于1階連邊；以此類推，與共同鄰居連邊的影響力再次之，然后才是共同鄰居節(jié)點的影響力。在FLSI模型和通用時序鏈路預測模型中，都需要針對這種規(guī)律調(diào)節(jié)局部作用系數(shù)的大小；在不同的局部作用系數(shù)下，考慮節(jié)點和連邊的權(quán)重調(diào)節(jié)參數(shù)，即如果網(wǎng)絡(luò)連邊的拓撲情況較好，則連邊的權(quán)重應(yīng)該分配更大，反之，則節(jié)點的權(quán)重應(yīng)該分配更大。

5 結(jié)束語

本文總結(jié)了基于時間序列分析和基于連邊動態(tài)演化的時序鏈路預測方法，提出了一種基于拓撲結(jié)構(gòu)影響力的時序鏈路預測算法的通用模型。在不考慮噪聲和全局特征的前提下，僅利用節(jié)點和連邊局部拓撲特征影響力演化的規(guī)律，給出了基于融合局部拓撲影響力的時序鏈路算法TLP-FLSI。在7個真實社交網(wǎng)絡(luò)數(shù)據(jù)集上的實驗結(jié)果表明，該算法具有較好的預測效果。本文實驗中，只對局部拓撲特征的調(diào)節(jié)系數(shù)做了敏感性測試，后續(xù)研究中將針對更多其他類型的時序網(wǎng)絡(luò)，對模型的衰減調(diào)節(jié)參數(shù)、訓練窗口的時間長度、數(shù)據(jù)集劃分間隔長度等參數(shù)進一步分析，以及針對時序的網(wǎng)絡(luò)全局特征和網(wǎng)絡(luò)環(huán)境噪聲的影響展開分析，進一步提高該時序鏈路預測算法的普適性。