一種基于博弈論的時序網絡鏈路預測方法

劉 留 王煜堯 倪琦瑄 曹 杰 卜 湛

1(南京財經大學信息工程學院 南京 210013)2(南京理工大學計算機科學與工程學院 南京 210094)

許多現實世界的網絡系統是非靜態的，節點間的連接關系隨時間動態變化，此類網絡可由一系列包含時間戳的鏈路集合[1]表示.在動態網絡研究領域中，除了研究最為廣泛的社區發現問題[2-3]，鏈路預測問題[4-6]研究如何利用網絡歷史拓撲信息預測未來的鏈路存在情況，是一項具有重要研究意義的課題.鏈路預測對于人們理解網絡演化[7]規律至關重要，且在諸多實際應用中發揮著重要作用，如預測蛋白質間的相互作用[8]、社交網絡中的朋友推薦[9]和科研網絡的合作推薦[10]等.

區別于已有的鏈路預測研究，本文旨在研究時序網絡[11]的演化機制，即給定一組由固定節點集合構成的靜態網絡序列，如g1,g2,…,gt,我們嘗試預測該網絡在未來時刻t+1到t+T的拓撲結構.一方面，傳統的鏈路預測方法[12]多關注于靜態網絡的鏈路預測問題，忽略了每條鏈路上的時間戳信息，故不能被直接應用于解決時序網絡的鏈路預測問題.另一方面，現實世界的網絡系統通常具有較大的規模，包含海量有復雜聯系的網絡參與者.例如，一個包含105個節點和106條鏈路的稀疏網絡，若預測未來可能生成的新鏈路，其搜索空間的數量級為1010；而預測未來可能消失鏈路的搜索空間的數量級為106，僅占前者的0.01%.受限于上述真實網絡的這種稀疏性特性，有監督的鏈路預測方法會面臨不同程度的分類樣本分布失衡問題.

基于上述分析，本文構建了一個高效的鏈路預測框架.首先，采用ε-鄰接網絡序列定義時序網絡的表示模型，從包含時間戳的鏈路集合中生成真實的網絡演化序列.另外，由于生存分析中的Cox比例風險模型不需對生存時間的分布作出假定，僅通過一個模型就可分析生存時間的分布規律.因此，我們為每條鏈路關聯一組基于拓撲相似性的特征向量，并借助Cox比例風險模型分別學習鏈路的消失和重連概率.然而，現實中的大多數網絡為稀疏網絡，即大多數的節點對之間不存在鏈路.因此，為壓縮搜索空間，我們將節點對之間的連邊情況模擬為2個玩家之間的博弈，進而提出一種基于動態博弈的雙向選擇機制來預測未來的網絡拓撲結構.除此之外，由于計算特征向量所采用的鄰近性指標是基于每個節點的鄰居來計算得到的，故我們將可能與節點i發生重連的節點約束在距i的最短路徑距離不超過2的范圍內.此舉有效地壓縮了鏈路預測的搜索空間，提高了算法的計算效率，緩解了稀疏網絡帶來的分類樣本分布失衡問題.

1 相關工作

傳統的復雜網絡鏈路預測方法主要分為3類：1)無監督預測方法；2)有監督預測方法；3)基于概率模型的預測方法.

無監督預測方法，也被稱為評分方法[13-14].此類方法的基本假設是：若2個節點拓撲相似度越大，它們在未來形成鏈路的概率越高.基于此假設，無監督預測方法通過定義一系列節點對的相似性函數，來刻畫網絡中任一鏈路的存在概率.其中最常用的相似性函數包括CN(common neighbor index)[15]，JC(Jaccard coefficient)[16]，PA(preferential attach-ment index)[17]，AA(adamic-adar index)[18]等.由于這些相似性函數多采用網絡的局部拓撲信息，故此類無監督預測方法通常具有較低的時間復雜度.此外，一些無監督預測方法則基于節點對連通路徑特征來定義節點對的相似性函數.此類方法的基本假設是：若2個節點間的距離越短，則它們在未來形成鏈路的概率越高.例如，Katz[19]不僅考慮2個節點之間所有的路徑，同時還利用路徑的權重來計算它們之間的相似性.Lü等人[20]提出的局部路徑(local path, LP)指標同時考慮直接鄰居和間接鄰居，獲取的路徑信息相對更為穩定、可靠.Yang等人[21]提出了一種基于聚類和決策樹的鏈路預測方法.基于隨機游走的鏈路預測算法的基本假設是：若某個節點進行隨機游走，到達另外一個節點所需要的平均游走步數最少，此時2個節點的相似性最高.Lichtenwalter等人[22]在隨機游走的基礎上進行了一定的改進，提出了PropFlow方法.Tong等人[23]提出了一種新的隨機游走方法，充分考慮網絡中普遍存在的社區結構特性.Jin等人[24]提出一種基于路徑反轉影響和隨機游走矩陣的鏈路預測方法.與經典的基于鄰居相似度的無監督預測方法相比，基于節點對連通路徑特征的無監督預測方法考慮了網絡的全局拓撲特征，其預測準確率相對較高，但節點對路徑特征的計算過程具有較高的時間復雜度.

有監督預測方法將鏈路預測問題轉化為二進制分類問題，根據歷史的網絡演化序列構建訓練樣本，并借助現有的分類器，如邏輯回歸[25]、支持向量機[26]、決策樹[27]、多層感知器神經網絡[28]和樸素貝葉斯[29]等，訓練分類器參數，進而再利用訓練好的分類器進行鏈路預測.例如，Pujari等人[30]提出一種監督式的排序融合方法對復雜網絡進行鏈路預測.Chen等人[31]利用正則化參數來完成貝葉斯推理，進而提高學習潛在特性的辨別能力.Nguyen-Thi等人[32]提出一種基于徑向基函數(radial basis function, RBF)的支持向量機(support vector machine, SVM)分類器，可有效提高預測精度且降低分類器的訓練時間.基于監督學習的鏈路預測方法在構建訓練樣本時都不同程度地面臨樣本類別分布失衡問題.真實的網絡系統呈現極強的稀疏特征，假定時刻t存在一個包含n個節點和m條鏈路的無向網絡gt，其稀疏性表現為m?n(n-1)2，其中n(n-1)2表示gt網絡最大可能的無向鏈路數量.當gt演化至時刻t′，我們可以根據網絡gt′與網絡gt的拓撲差異，分別構建相應的訓練集來預測未來的消失鏈路和重連鏈路.以重連鏈路預測為例，我們可以將{eij|eij∈(gt′-gt)}中的鏈路標記為正例樣本，將{eij|eij?(gt′-gt)}中的鏈路標記為負例樣本.考慮到真實網絡的動態演化呈現顯著的漸進性，網絡拓撲結構的變化是一個相對緩慢的過程.由于|{eij|eij∈(gt′-gt)}|?|{eij|eij?(gt′-gt)}|，采用上述方法構建的訓練集中，正例樣本和負例樣本存在嚴重的分布失衡現象，傳統的機器學習分類器難以訓練出理想的重連鏈路預測模型.

基于概率模型的鏈路預測的基本思想是建立一個含有多個可調參數的模型，利用某種優化策略尋找參數的最優值，從而使得網絡的結構和關系特征能夠在模型中得到更好的體現.網絡中任意節點對的重連概率可表示為基于最優參數配置的條件概率.Wang等人[33]提出了一個基于局部概率模型(local probabilistic model, LPM)的鏈路預測方法，可極大地降低大規模復雜網絡鏈路預測問題的時間復雜度和空間復雜度.Coutant等人[34]提出了一種基于聚類不確定性的概率關系模型(probabilistic relational models with clustering uncertainty, PRM-CU)用于分析復雜網絡的級聯失效，該概率模型能夠充分利用網絡的拓撲信息，衡量節點對的交互能力，能夠有效地提高鏈路預測的準確性.由于網絡結構本身較為復雜，為表示更高層次的非線性網絡結構，Wang等人[35]提出了結構化深層網絡嵌入模型(structural deep network embedding， SDNE).與傳統鏈路預測方法相比，SDNE模型能夠有效地提取網絡的局部和全局結構信息，重構網絡結構，進而得到更高的預測精度.

此外，還有一些鏈路預測方法考慮了鏈路的時間戳信息和網絡的社團結構特征.例如，Sharan等人[36]提出了基于不同時間關系的分類模型，采用2個實體間動態關系信息的關系模型.Rossi等人[37]提出了基于時序關系從屬分類的集成預測方法.Clauset等人[38]提出了一種利用網絡層次結構進行鏈路預測的方法，且在具有明顯層次結構的網絡中，該方法能取得更好的預測性能.這些鏈路預測方法大多對網絡的拓撲結構有較高的要求，且計算時間復雜度普遍較高.

2 問題定義

現實世界的時序網絡可表示為一個時序鏈路集γ={ip,jp,τp|p=1,2,…,M}，其中ip,jp,τp表示一個帶有時間戳的時序鏈路，表明節點ip和節點jp在時刻τp是連通的.當忽略時序鏈路的時間戳和重復鏈路時，時序網絡就退化為一個靜態網絡g(γ)={eij|?ip,jp,τp∈γ}.

定義1.δ-時序范式.時刻t的δ-時序范式是一個有序鏈路序列Mt(δ)=its,jts,τts,…,ite,jte,τte，滿足(τts≤…≤τte)∧(δ=τte-τts)，且靜態網絡gt(δ)=(Vt(δ),Et(δ))，Et(δ)?Vt(δ)×Vt(δ)是連通的.

靜態網絡gt演化至與其ε-鄰接的網絡gt′包含3種可能情況：1)從gt中消失的鏈路；2)gt中任意2個不連通的節點形成的鏈路；3)至少有1個外部節點參與形成的鏈路.由于外部信息具有較大的隨機性，本文將重點關注前2種情況的鏈路預測問題，并假設出現在所有周期的節點集合是固定的.

定義3.ε-鄰接網絡序列.從初始網絡g0(δ)=(V,E0)開始，ε-鄰接網絡序列由一系列耦合的靜態網絡組成，即Gε(g0(δ))={g1,g2,…}，滿足?t≥1：1)gt-1和gt是ε-鄰接的；2)Vt?V，Et?V×V.

為強調從gt-1到gt的網絡演化過程，令Mt和Rt分別表示從gt-1消失的鏈路集合和在gt中新生成的鏈路集合.顯然，Mt=Et-1-Et和Rt=Et-Et-1.

定義4.多層網絡[39]序列.令ε-鄰接網絡序列Gε(g0(δ))={E1,E2,…}中任意第t個周期的靜態網絡都對應一個多層網絡Mt(L)={Et,Pt(L)}，其中，Et?V×V是周期t中靜態網絡的鏈路集，Pt(L)?V×V是gt最近L個靜態網絡投影所得的鏈路集：

(1)

這樣，由任意周期窗口L導出的多層網絡序列表示為MNS(L)={M0(L),M1(L),…}.

定義5.拓撲相似性函數.令Ni={j|eij∈E*}表示節點i在某個靜態網絡中的鄰居集合，鏈路ip,jp,τp的拓撲相似性可由一些相似性函數度量計算得到.例如，CN[15]，JC[16]，Sa(salton index)，So(sorensen index)，HP(hub promoted index)，HD(hub depressed index)，LN(Leicht-Newman index)，PA[17]，AA[18]等，具體為

定義6.消失鏈路序列(missing link sequence，MLS).給定一個ε-鄰接網絡序列Gε(g0(δ))，由此導出的消失鏈路序列表示為GM(g0(δ))={M1,M2,…}，滿足?t≥1,Mt=Et-1-Et.

定義7.重連鏈路序列(reconnected link sequ-ence， RLS).給定一個ε-鄰接網絡序列Gε(g0(δ))，由此導出的重連鏈路序列表示為GR(g0(δ))={R1,R2,…}，滿足?t≥1,Rt=Et-Et-1.

(2)

(3)

(4)

(5)

3 時序網絡鏈路預測模型

基于定義8和定義9，我們可借助于Cox比例風險模型分別學習鏈路消失和重連所對應特征向量的權重系數.Cox比例風險模型采用最大似然估計方法對模型參數進行估計，上述2個事件對應的協變量系數WM*和WR*可分別通過式(6)(7)學習得到：

(6)

(7)

(8)

(9)

(10)

Ψt對應的納什均衡點集為

(11)

Et+1=Q(Et,Θt,Φt)=Et-Dt,M+Dt,R.

(12)

4 基于自治計算的網絡演化算法

算法1.網絡演化算法.

輸入：初始靜態網絡g0(δ)=(V,E0)、時間窗口長度L、最大迭代次數I、消失鏈路的協變量系數WM*、重連鏈路的協變量系數WR*；

①t←0；

③ repeat

④ ?i∈V，并行計算：

基于上述定義的自治計算系統，本文提出了基于博弈論的時序網絡預測算法，具體過程見算法1.從單個節點智能體的角度來看，步驟初始化節點智能體vi的三元組為其中表示初始靜態網絡g0中節點i的鄰居集.在每輪迭代中，步驟⑤～并行化地計算和步驟～計算相應收益矩陣Θt和Φt的納什均衡點集；步驟生成下一周期靜態網絡的鏈路集合.當系統時間達到預設的最大迭代次數I時，算法將會輸出一個預測的網絡演化序列

5 實驗和結果

5.1 實驗設置

我們選擇斯坦福網絡分析平臺SNAP中的4個時序網絡Math，Ask，Super，Stack，生成4個ε-鄰接網絡序列.具體來說，對于每個時序網絡，我們使用第1年的數據元組構建一個無向網絡，并抽取該網絡的最大連通子圖生成初始的靜態網絡g0(初始靜態網絡的統計特征見表1).接下來，我們進一步將ε設置為2%，生成相應的ε-鄰接網絡序列.圖1分別記錄了4個ε-鄰接網絡序列中相應的|Et|，|Mt|，|Rt|包含的鏈路數量.可見，隨著時間周期t的增加，|Et|，|Mt|，|Rt|都呈顯著的下降趨勢.后續實驗中，我們將這4個ε-鄰接網絡序列作為真實的網絡演化序列，并將算法1分別應用于表1的4個初始靜態網絡.通過對比預測得到的網絡演化序列和真實網絡演化序列的相似度，來評價鏈路預測算法的優劣.

我們選擇5種基于監督學習的鏈路預測方法，包括Logistic回歸(logistic regression， LR)、SVM、決策樹(C4.5)、多層感知器神經網絡(multi-layer perception neural network， MPNN)和樸素貝葉斯(na?ve Bayes， NB)作為對比算法.針對每個耦合的靜態網絡對，如(Et-1,Et)，然后將所有Mt中的鏈路標記為正例，并從Et-1-Mt中隨機選擇相同數量的鏈路標記為反例.這些鏈路實例的特征向量基于相應靜態網絡Et-1計算生成.這樣，我們可以選擇一種分類器在上述訓練集上進行訓練，并將訓練好的分類器用于消失鏈路預測.采取相同的思路，我們可以構建另一個訓練樣本進行重連鏈路預測，其中節點對的特征向量基于相應的投影網絡Pt-1(L)計算生成.此外，我們還選擇了3種基于概率模型的鏈路預測方法，包括Wang等人[33]提出的LPM模型、Coutant等人[34]提出的PRM-CU模型、Wang等人[35]提出的SDNE模型.

(13)

5.2 基于Cox比例風險模型的參數學習

采用相同的分析過程，我們可以分別對其他3個時序網絡進行類似的分析，其結果見表4.其中，每個數據集中，加粗字體的協變量系數表示該特征與對應事件是正相關，正常字體的協變量系數表示該特征與對應事件是負相關，而缺失協變量系數表示該特征與對應事件不相關.在所有數據集中，PA特征[17]與鏈路的消失和重連都是獨立的.經典的BA網絡演化模型[40]假設一個新的節點同已知網絡中的節點i連接的概率同ki呈正比.而本文考慮的網絡演化序列是基于固定節點集V生成的，排除了新節點加入對網絡演化的影響.在這種情境下，傳統的基于BA模型的無標度網絡生成模型可能并不適用.

Table 2 Results of Survival Analysis on HM Dataset of theTemporal Network Math表2 基于Math時序網絡HM數據集的生存分析結果

Notes: Bold values represent a positive correlation between the feature and link missing event, while the regular ones represent a negative correlation. Sig. means significance.

Table 3 Results of Survival Analysis on HR Dataset of theTemporal Network Math表3 基于Math時序網絡HR數據集的生存分析結果

Notes: Bold values represent a positive correlation between the feature and link reconnection event, while the regular ones represent a negative correlation. Sig. means significance.

Table 4 Learning Results of the Covariate Coefficients Based on the Cox Proportional Hazards Model表4 Cox比例風險模型協變量系數學習結果

Notes: Bold values represent a positive correlation between the feature and link missing/reconnection event, the regular ones represent a negative correlation, while the missing values represent that the features are independent from the related events.

Fig. 2 The F1-score matrices between the predicted network evolution sequence and the ground-truth one圖2 真實網絡演化序列同預測網絡演化序列的F1-score矩陣

5.3 時序網絡鏈路預測結果

接下來，我們將算法1同其他鏈路預測方法進行性能對比.從圖3中可觀察到，本文所提方法明顯優于對比算法.其中，MPNN只在Stack網絡上有較好的表現，但無法準確預測其他3個網絡的演化序列.多數基于監督式學習的鏈路預測方法對訓練樣本很敏感，受分類樣本失衡問題的影響，這些方法盡管在消失鏈路預測上可以取得不錯效果，但難以準確地預測重連鏈路.本文方法采用動態博弈的雙向選擇機制，可以篩選出最可能消失的鏈路和最可能重連的節點對.這種相對保守的預測方法盡管在召回率方面有所犧牲，但可以獲得更高的準確率.因此，在AvgF1指標上，本文方法要明顯優于基于有監督學習的鏈路預測方法.與基于概率模型的鏈路預測方法相比，本文方法在Super網絡上的預測性能稍遜于SDNE；而在其他網絡上，算法1得到的網絡演化序列能更好地模擬真實網絡的演化過程.

Fig. 3 Accuracy comparison of the network evolution sequences obtained by different link prediction algorithms圖3 不同算法對網絡演化序列的預測準確性比較

最后，我們對比了不同鏈路預測算法在100次連續預測過程中的執行效率，從圖4可以看出，不論在小規模的Math數據集上，還是在大規模的Stack數據集上，算法1的執行效率都明顯優于其他對比算法.由于本文采用了Cox比例風險模型對每個數據集中不相關的鏈路特征進行了排序，因此在迭代預測過程中，每個節點對的特征向量更新耗時更少.在動態博弈框架下，每個節點的特征向量更新和策略選擇是獨立的，故算法1可以很好地并行化.另外，我們發現本文所提方法的執行效率比基于有監督學習的鏈路預測算法提高了將近2倍，比基于概率模型的鏈路預測算法的執行效率提高了將近10倍.

Fig. 4 Comparison of the total running time of differentlink prediction algorithms圖4 不同鏈路預測算法的執行時間對比

6 總 結

本文提出了一種新穎的用于預測時序網絡的演化序列半監督學習框架.為簡化研究問題，假設時序網絡的演化是在一組固定節點集中進行的，此時網絡的演化預測問題轉換為：如何根據歷史的網絡演化序列預測下一時刻靜態網絡的消失鏈路集和重連鏈路集.為解決此問題，首先為每條鏈路定義一組基于鄰居相似度的特征向量，利用Cox比例風險模型學習對應鏈路消失和重連事件的特征向量權重.為壓縮網絡演化預測的搜索空間，提出了一種基于動態博弈的雙向選擇機制來預測未來的網絡拓撲結構.在理論研究基礎上，提出了一種基于多智能體自治計算的鏈路預測算法，并在真實時序網絡數據集上驗證了方法的有效性和高效性.未來將關注于如何將網絡的社團結構信息融入預測模型，進而提高預測算法的準確性.