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

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

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

1 引言

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

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

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

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

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

2 問題描述及評價指標

常見的動態網絡建模方式是根據時序對數據進行等間隔切分，把動態網絡分解為一系列的時間快照圖集合，這樣的建模方式相當于對動態網絡在時間維度上進行采樣，將動態網絡拆分成多個靜態網絡序列，使得靜態網絡的預測算法能夠適用于動態網絡的處理。

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

動態時序網絡在t (0

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

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

3 算法設計

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

3.1 基于網絡拓撲影響力的通用時序鏈路預測模型

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

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

局部影響力可以考慮網絡拓撲中節點和連邊在局部范圍內的結構特征進行融合表示，可以用節點和連邊的相似性，以及演化過程中的相關性進行度量。對于t時刻的節點i和j的局部影響力計算為

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

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

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

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

圖2 TLP-FLSI與CTLPM的關系圖

定義FLSI-III為考慮連邊和連邊協相關因素的

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

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

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

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

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

3.2.1 基于節點局部影響力的演化因子

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

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

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

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

圖3 節點局部影響力演化示意圖

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

在靜態網絡鏈路預測的方法中，對節點對的連邊關系的預測也可以轉化為對其拓撲結構中路徑信息的相似性判決問題。如LP指標就考慮了有限的3階路徑長度，它的定義為

其中，A表示網絡的鄰接矩陣，λ為調節參數，S是最終的得分預測矩陣。而Katz指標把節點i和節點j之間的全局所有路徑都考慮進來，定義為

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

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

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

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

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

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

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

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

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

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

4 實驗驗證

4.1 實驗數據集

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

表1 數據集參數表

4.2 實驗對比算法

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

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

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

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

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

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

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

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

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

4.3 實驗結果分析

4.3.1 性能對比分析

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

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

表2 不同方法的平均AUC性能結果

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

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

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

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

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

4.3.2 參數敏感性分析

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

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

圖7 步驟1實驗權重參數影響的變化曲線

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

圖8 步驟2實驗權重參數影響的變化曲線

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

圖9 步驟3實驗權重參數影響的變化曲線

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

5 結束語

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