時序網絡中關鍵節(jié)點的識別方法研究進展

陳 詩，任卓明，劉 闖*，張子柯,2

(1.杭州師范大學阿里巴巴復雜科學研究中心 杭州 311121；2.移動健康管理系統(tǒng)教育部工程研究中心 杭州 311121)

時序網絡是拓撲結構隨時間不斷變化的網絡，其中拓撲結構變化表現為節(jié)點或連邊的增加或減少?，F實社會中，隨時間不斷變化的網絡無處不在[1-2]：在線社交網絡、通信網絡、合作網絡、科研網絡；經濟網絡、交通網絡、電力網絡；基因調控網絡、腦神經網絡等等。隨著藍牙、可穿戴設備、傳感器等的普及，用于構建時序網絡的帶時間戳的數據的獲取逐漸變得容易，基于時序網絡開展的研究成果也逐漸豐富。文獻[1-2]總結了時序網絡的類型、時序網絡拓撲結構的測度、時序網絡的模型以及時序網絡的傳播動力學等；文獻[3]用時序圖分析時序數據，提出了關于時序圖路徑的測度；文獻[4]總結了時序網絡相對靜態(tài)網絡的優(yōu)勢，發(fā)現時序網絡中從初始狀態(tài)到最終狀態(tài)，到達過程更快，需求的控制能量和控制軌跡數量級較小。此外，文獻[5]對進化的復雜系統(tǒng)中的排序方法進行總結時，提及了時序網絡中的節(jié)點重要性排序方法。相對靜態(tài)網絡，時序網絡增加了時間維度，考慮了節(jié)點間的交互順序，從而可以更準確地刻畫真實系統(tǒng)[6-11]。因此，時序網絡模型的構建及其相關理論和應用研究，已經成為網絡科學的一個重要研究方向。

關鍵節(jié)點一般是在整個網絡中處于核心位置的節(jié)點，對整個網絡的結構或者功能具有較大的影響力[5, 12-14]。網絡中關鍵節(jié)點的確定，可以獲得有關實體重要性的先驗知識從而預測事情的發(fā)展進程，如預測關鍵元件以防止電網或互聯(lián)網中的災難性故障、預測成功的科學家或流行的科學出版物等；可以有效調控傳播過程，如精準投放電子商務產品廣告以實施產品推廣、控制流行病爆發(fā)或抑制謠言傳播等。關鍵節(jié)點的識別方法之所以能在不同領域中得到應用，一方面取決于方法本身的判別價值，另一方面則是因為信息過載時代大眾的多方需求，現如今不論個人還是組織都希望以更低的成本獲取實現目的最相關的信息。因此，在網絡科學研究中，設計有效的關鍵節(jié)點識別方法，并提出合理的評價模型，有著很強的理論研究和實踐意義。

目前，時序網絡中的關鍵節(jié)點識別這一問題越來越受到學者的關注。以往對于關鍵節(jié)點的挖掘研究大多是將現實系統(tǒng)抽象成點邊相連的靜態(tài)網絡，再依據網絡的拓撲結構和動力學特征獲得表征節(jié)點重要性的度量指標，這些關于網絡中節(jié)點重要性的研究工作主要集中于網絡的靜態(tài)結構和理論分析上[15-20]。而真實的復雜系統(tǒng)隨時間不斷進化，個體間的交互呈現出典型的間歇性和陣發(fā)性，這使得過去基于靜態(tài)網絡的研究在相當程度上制約了研究成果在實際系統(tǒng)中應用的效果和可靠性。因此，有必要從不同角度總結時序網絡中關鍵節(jié)點挖掘的研究進展，并對未來可能的研究方向進行探討。

本文按如下思路展開：首先分析現有的時序網絡建模，再基于時序網絡模型從網絡的拓撲結構、隨機游走動力學以及機器學習的視角概括時序網絡中節(jié)點的排序測度或中心性指標；然后從網絡性能變化、傳播動力學以及預測性能三個方面介紹時序網絡中關鍵節(jié)點的評價方法；最后在總結和展望部分指出了當前面臨的問題和可能的發(fā)展方向。

1 時序網絡建模

時序網絡模型的構建是探索時序網絡中關鍵節(jié)點識別方法的基礎。這里我們所研究的時序網絡模型具有一個共同的特征：均不考慮時序網絡中節(jié)點的增加和移除，而只考慮連邊的出現和消失，即所構建的時序網絡模型中節(jié)點數目保持不變，連邊隨時間動態(tài)變化。其所依賴的數據記錄一般以三元組(i,j,t)的 形式呈現，其中i 和 j表示兩個相關的實體(即網絡中的節(jié)點)，t表示兩實體發(fā)生作用的時間(即在時間t， 節(jié)點i 點 j之間出現連邊)。目前，主要的時序網絡模型大致可分為三類：基于靜態(tài)圖的時序網絡模型，基于快照的時序網絡模型和基于明顯路徑流的時序網絡模型[21]。

1.1 基于靜態(tài)圖的時序網絡模型

基于靜態(tài)圖的時序網絡模型，也叫時間聚合以連邊 (B ,D)為例，時間聚合圖1 上的序列為[1,2,6]含交互的具體時間，對應表示節(jié)點B 和節(jié)點D 在時間 t=1、 t=2和 t=6時發(fā)生交互。此類模型在傳統(tǒng)靜態(tài)網絡的基礎上增加了時間信息，使其能更真實展示現實系統(tǒng)的演化，但在一定程度上不夠直觀，且不易用矩陣方式存儲和計算。圖(time aggregated graphs)，是在靜態(tài)網絡拓撲結構的基礎上，把節(jié)點間交互的時間信息存放在邊上的時序網絡模型。圖1 是常見的時間聚合圖模型。

關于此類時序網絡模型的研究，文獻[22]最早提出并將其用于研究時序網絡的連通性和推理問題。之后，文獻[23]將模型中的連邊建為有向邊，研究了社會溝通網絡中的信息路徑結構；文獻[21]將連邊上具體的時間信息轉化為相應時間的邊對應的有和無兩種狀態(tài)，探索了時序網絡中中心性測度的計算方法；文獻[24]也對時間聚合圖提出了改進，其假設連邊有向且一對節(jié)點之間可能存在帶有不同時間戳的多條連邊，探索了時序網絡中的時序PageRank 的表示與計算。此外，文獻[1-2]也表示通過靜態(tài)圖表征時序網絡可以研究時序網絡的時序屬性和拓撲屬性，并對相關的靜態(tài)圖進行了簡單介紹。

1.2 基于快照的時序網絡模型

基于快照(snapshots)的時序網絡模型，實際可以看作基于靜態(tài)圖的時序網絡模型的拓展，在一定程度上展示了事件的演變過程[25-26]。此類模型的核心在于將研究的整個時間段 [0, T]切分成連續(xù)的長度為 ω的 m個 快照 N1,N2,···,Nm(m=T/ω)。每個快照可以包含在特定時間瞬間發(fā)生的所有事件，也可以是在特定時間窗口內發(fā)生的所有事件的靜態(tài)聚合。根據模型中是否展現快照間的關系，可以將基于快照的時序網絡模型分成兩類。

1.2.1 時間窗圖模型

最常見的基于快照的時序網絡模型是如圖2 所示的時間窗圖模型。該模型將快照依次表示為時間聚合圖，快照的時間間隔即為時間窗口的大小。圖2b 中時間窗大小為 ω= 1，圖2c 中時間窗大小為ω=2?？煺罩械氖录鶕煺盏臅r間間隔而定。

文獻[25]首先提出將動態(tài)圖視為一系列的靜態(tài)圖。在此基礎上，不少學者將此類模型作為設計時序網絡中關鍵節(jié)點識別方法的基礎，提出了時序網絡中識別節(jié)點重要性或影響力的測度[4, 27-38]。此外，文獻[39]在探索動態(tài)網絡中的中心性測度時，將每個時間窗中的連邊定義為有向；文獻[40]在設計時序網絡的隨機游走中心性時，為每個時間窗中的連邊賦予權重，其中第t個快照中節(jié)點對之間的連邊權重用時間 (t ? 1)ω 到時間 tω間該節(jié)點對的接觸次數表示。應注意，快照時間間隔的選取(即時間窗大小的選擇)目前仍是無定論的問題[41-42]。當使用時間窗圖模型表示時序網絡時，有必要進一步探測模型中不同大小的時間窗口對研究結果的影響。

1.2.2 多層圖時序網絡模型

在時間窗圖模型的基礎上，學者提出了如圖3所示的多層圖時序網絡模型。該模型實質上也是基于快照的時序網絡模型，一般由層內關系和層間關系共同定義：層內關系對應一個快照，可理解為時間窗圖模型中的一個時間窗圖，表征節(jié)點間的交互作用；層間關系則表征相鄰時間窗中對應節(jié)點間的關系，且只有節(jié)點自身的連接。就層間關系而言，目前常用的思想有兩種，即采用固定的常數和采用相鄰時間快照間節(jié)點的相似性關系。圖3 中的 ωi即是對層間關系的表征。

關于此建模方法，文獻[43]對其進行了詳細的討論；文獻[44]將特征向量中心性推廣到時序網絡時用到該結構，并采用固定常數表示層間關系；文獻[14]則采用基于相鄰時間快照間的相似性關系定義層間關系，并基于該模型探索了不同時間層不同節(jié)點的特征向量。此外，文獻[46]針對層間耦合關系的度量方法進行了分析研究，通過計算不同層間相似性指標值與正理想解和負理想解之間的歐氏距離對度量方法進行排名，發(fā)現用優(yōu)先鏈接指標度量時序網絡時間層的耦合關系，所挖掘出的重要節(jié)點準確率最高。

1.3 基于明顯路徑流的時序網絡模型

基于明顯路徑流的時序網絡模型，是基于快照的時序網絡模型在時間維度上的進一步細化。模型中每個實體對應的節(jié)點根據交互信息跨時間復制，而表示潛在信息流的邊則用有向邊表示并按時間順序添加。圖4 是該模型的具體展示，其中水平軸表示時間尺度，豎直軸表示網絡中的節(jié)點，網絡節(jié)點的交互只發(fā)生在橫軸兩個相鄰的時間層之間，每個節(jié)點在前后時間層始終與自身相連。該建模方法已被文獻[47]用來研究時序網絡的節(jié)點重要性評估。文獻[3]在2009 年也提出了其近似模型，并表明是完全保留原始數據時間信息的時序圖模型。之后，文獻[48]將其用于時序網絡中覆蓋中心性的探測，發(fā)現大多數的高中心性節(jié)點位于某特定時間附近較小的時間窗內，從而獲知時序網絡中的大量信息只經過少量重要的時序節(jié)點傳送，且該傳送過程發(fā)生的時間存在對應的瓶頸期。

此外，文獻[49]基于小世界網絡和無標度網絡 擬 合 Susceptible-Infected-Susceptible(SIS)、Susceptible-Infected-Recovered(SIR)傳播模型，建立了基于明顯路徑流的時序網絡模型。當確定初始感染源時，每個時間層節(jié)點的狀態(tài)以及相鄰時間層節(jié)點間的連邊可以完全確定，即整個傳播過程生成的時序網絡模型固定。應注意，該模型層間不同節(jié)點間交互的發(fā)生存在激活概率，而不是與所有的鄰居節(jié)點都存在連邊。圖5 是確定初始傳播源，采用SIR 模型，根據節(jié)點交互情況和狀態(tài)變化生成的時序網絡模型。其中，紅色的節(jié)點表示感染狀態(tài)I，綠色的節(jié)點表示易感狀態(tài)S，白色的節(jié)點表示恢復狀態(tài)R；紅色的邊和綠色的邊均表示擬合SIR 模型時節(jié)點間連邊在相應的時間被激活而發(fā)生交互，其中紅色的邊表示t 時刻的感染節(jié)點致使t 時刻的易感節(jié)點變成 t+1時刻的感染節(jié)點，綠色的邊則表示t 時刻的易感節(jié)點與t的感染節(jié)點或易感節(jié)點發(fā)生交互而在 t+1時刻仍然保持易感狀態(tài)；灰色的邊則表示層間節(jié)點狀態(tài)的傳遞，其中感染狀態(tài)I 以一定概率成為恢復狀態(tài)R。

1.4 其他時序網絡模型

除了以上三類時序網絡模型，也有學者對時序網絡的建模及相關特征進行了專門研究。例如，文獻[50]除了考慮事件瞬時發(fā)生的情況，還考慮事件會持續(xù)一段時間的情況，從而在改進時序網絡模型的基礎上定義了時序平均距離；文獻[51]從進化的系統(tǒng)出發(fā)，提出了時間窗口大小不等的時間窗圖模型，其中時間窗口大小依據事件進化中事件相似性的最大值而確定；文獻[52]通過考慮一個與時間有關的哈密頓量，構造了一個隨時間變化的網絡的虛時間演化算子，從而通過函數解釋時序網絡模型中的動態(tài)變化；文獻[53]基于聚合時間圖和時間窗圖，在每個快照中加入節(jié)點和連邊的定量屬性及方向信息等，然后將t時刻的在線社交網絡表示為 Gt=(Vt,Et,FVt,FEt,t)， Vt是時間t時刻在線社交網絡中的節(jié)點集， Et是 時間t時刻在線社交網絡中連邊的集合， FVt是 按特征向量 fv定量描述節(jié)點v ∈Vt屬性的 |Vt|×|fv|維 矩陣， FEt是按特征向量 fe描述連邊 e ∈ Et屬 性的 |Et|×|fe|維矩陣，從而識別大規(guī)模時序在線社交網絡中的活躍節(jié)點；文獻[54]提出高階聚集網絡研究時序網絡的路徑結構，并對靜態(tài)網絡中的介數中心性、接近中心性和可達中心性進行了拓展。該模型背后的思想是每一個 k階連邊(v,w)表 示底層時序網絡中長度為 k的時序路徑存在的可能性。具體地，將 k?階靜態(tài)聚合網絡表示為G(k)=(V(k),E(k))， 其中 V(k)?Vk是 k個節(jié)點組成的元組的集合， E(k)?V(k)×V(k)是連邊的集合。簡化處理，設置v = (v1?v2?···?vk)∈V(k),vi∈V 以及w=(w1?w2?···?wk)∈V(k),wi∈V 是 k階靜態(tài)聚合圖中的節(jié)點， e= (v,w)∈E(k)是 k階靜態(tài)聚合圖中的連邊，連邊 e存在的條件為兩個 k階靜態(tài)聚合圖中的節(jié)點 v和w 恰好有k ?1個 元素重合，即有vi+1=wi,i=1,2,···,k ?1。此外，文獻[55]將時序網絡拓展到二分網絡，通過簡單將其劃分為過去的時間窗和未來的時間窗，構建了用戶-商品時序二分網絡，并基于此提出了商品的流行性和時序新穎性。這些其他時序網絡模型有的額外考慮了時序網絡的屬性和特征，有的直接將模型通過數值形式表征，都為進一步研究時序網絡中的節(jié)點重要性奠定了基礎。

2 時序網絡中關鍵節(jié)點的識別方法

時序網絡中關鍵節(jié)點識別方法的主要思路是基于時序數據構建時序網絡模型，然后通過時序網絡的拓撲結構或動力學特征，采用網絡節(jié)點排序算法，識別關鍵節(jié)點。下面主要從網絡的拓撲結構、動力學以及機器學習方法三個方面介紹。

2.1 基于拓撲結構的識別方法

節(jié)點的重要性很大程度上是由節(jié)點在網絡上的結構所決定的，依據網絡的拓撲結構設計節(jié)點的排序指標，是時序網絡中關鍵節(jié)點識別的一類重要方法。目前，這些方法的提出多基于靜態(tài)拓撲指標，如度中心性[56]、介數中心性[57]、接近中心性[58]、kshell 值[59]等。

2.1.1 基于度中心性的識別方法

靜態(tài)網絡中，節(jié)點中心性最直接的度量是度中心性[56]，即一個節(jié)點的度越大意味著這個節(jié)點越重要。在時序網絡，基于度中心性的時序節(jié)點中心性指標也同樣是最直接的識別重要節(jié)點的依據。

文獻[47]基于明顯路徑流的時序網絡模型，首先提出了在一段時間 [i,j]內 節(jié)點 v ∈ V的時序度值

式中， Dt(v)表 示時間t時 節(jié)點 v 的度，忽視從 vt?1到vt的自邊 (t= i+1,···,j)。節(jié)點的時序度值越大，節(jié)點越重要，該節(jié)點成為關鍵節(jié)點的可能性也越大。

文獻[37]基于時間窗圖模型，對各個時間窗內的時序度中心性值取標準差，提出了時序度中心性偏差值對節(jié)點重要性進行排序。具體計算公式如下：

基于度中心性的識別方法包括了時序度中心性以及時序度中心性偏差值，兩者均聚焦于時序網絡中隨時間變化節(jié)點度值的波動性。其中，時序度中心性通過取不同時間節(jié)點度的均值的方式對度值的波動性予以處理，而時序度偏差中心性則在時序度中心性的基礎上通過求標準差進一步體現出度值的波動性特征。因此，時序網絡中基于度中心性的識別方法優(yōu)于靜態(tài)網絡的度中心性，但在判斷過程中都遵循，所提出的表征節(jié)點重要性的指標值越大，節(jié)點越重要。此外，一個值得注意的潛在問題是，一個時間序列的中心性指標的均值越大，相應的方差也越大[60]。

2.1.2 基于最短路徑的識別方法

靜態(tài)網絡中，介數中心性[57]和接近中心性[58]是基于最短路徑刻畫節(jié)點重要性的典型指標。其中，介數中心性考量經過某節(jié)點的最短路徑的數目，刻畫該節(jié)點作為中介對信息沿著最短路徑傳輸的控制能力；接近中心性考量每個節(jié)點到其它節(jié)點的最短路徑的平均長度，刻畫節(jié)點傳輸信息的速度。

時序網絡中，由于路徑受連邊產生時間和產生順序的影響，呈現出不同于靜態(tài)網絡中路徑的特征[29, 54, 61]，主要包括路徑的不對稱性，未連通的節(jié)點更多，消息傳遞中的滯留或失效等?；诖耍S多學者對時序網絡中的路徑、最短路徑以及距離重新進行了考量，定義了時序路徑、時序最短路徑以及時序距離，并在此基礎上提出改進后的時序介數中心性、時序接近中心性以及其他基于時序最短路徑的相關指標。

文獻[27]以時間窗圖模型擬合時序網絡，分別從局部和全局的視角出發(fā)考慮網絡的演化，提出新的時序距離指標，量化和比較了信息擴散過程的速度；然后基于時序路徑和時序距離，提出了研究關鍵節(jié)點的時序中心性指標，研究了時序網絡中的小世界現象，并將時序中心性指標用于惡意軟件的檢測[27-29, 62-63]。關于時序路徑和時序距離，文獻[27]進行了如下定義：

表示同一時間窗內最大跳躍數為 h的條件下，從 t1時 間的節(jié)點 n1出 發(fā)在時間 tk到達節(jié)點 nk的時序路徑，其中 tmin?tk?1?tk?tmax。假設是節(jié)點i和節(jié)點 j間所有時序路徑的集合，若時序路徑不存在，則，說節(jié)點i和 節(jié)點 j是不連通的節(jié)點對，并設定距離

則節(jié)點i和 節(jié)點 j間的所有最短時序路徑集合為

基于此，文獻[28]從靜態(tài)網絡中的介數中心性和接近中心性出發(fā)，提出了時序介數中心性和時序接近中心性的計算方法。關于時序介數中心性，不僅需要考慮通過節(jié)點的最短路徑的數目，同時需要考慮最短路徑中節(jié)點在將信息傳遞給下一個節(jié)點前保留信息的時長。因此先計算節(jié)點i 在時間t 的時序介數中心性如下：

式中， w 表示時間窗的大小； m表示時序網絡中時間窗的總數目。

關于時序接近中心性，直接擴展靜態(tài)網絡中的計算公式得到時序接近中心性的計算如下：

所計算的節(jié)點的時序介數中心性和時序接近中心性的值越大，表明節(jié)點越重要。但是，這兩個時序節(jié)點重要性評價指標并不總是適用于任何場景。文獻[62-63]將所提出的時序指標用于選取關鍵節(jié)點用于阻斷惡意軟件傳播，便發(fā)現時序介數中心性與靜態(tài)指標的效果不顯著，但通過選取時序接近中心性高的節(jié)點則有顯著效果，因為時序接近中心性高的節(jié)點可以很快到達大多數節(jié)點。

式中， ?t,j(v,u)是 時間間隔 [t,j]內 節(jié)點 v 到節(jié)點u 的時序最短路徑距離，以路徑中的連邊數表示。當節(jié)點v 和節(jié)點u 之 間不存在時序路徑時， ?t,j(v,u)=∞。以Sx,y(s,d) 表示在時間間隔 [x,y]內 ，從節(jié)點 s到節(jié)點d的時序最短路徑的集合， Sx,y(s,d,v)是路徑中包含節(jié)點 v 的 Sx,y(s,d) 的子集。定義時間間隔 [i,j]內節(jié)點v ∈V標準化的時序介數中心性計算如下：

文獻[50]考慮到事件從發(fā)生到結束的耗時以及時序路徑的不同開始時間等影響，將整個網絡視為一個整體，研究了對有限周期內無窮距離的處理方法，并提出了節(jié)點對間的平均時序距離計算公式：

發(fā)現當且僅當節(jié)點間有唯一時序路徑時，平均時序距離獨立于路徑的開始時間，也獨立于觀測時間窗口的時間順序設置。在此基礎上，結合靜態(tài)網絡中的接近中心性公式定義了時序接近中心性：

該時序接近中心性與靜態(tài)網絡的接近中心性類似，值越大，則表明節(jié)點越重要。

文獻[33]發(fā)現時序網絡中基于路徑的節(jié)點重要性評估指標的研究，大多基于數據集起始時間開始的路徑，或雖考慮整個數據集時間跨度內的所有路徑但多計算單一的靜態(tài)指標，于是開放地考慮路徑的起始時間(即考慮開始于數據集時間間隔內任意時間為起始時間的所有路徑)，并將靜態(tài)網絡中的接近中心性拓展為隨時間不斷進化的時序接近中心性指標，從而用于評估任意給定時間任意節(jié)點的重要性。具體方法如下：

定義動態(tài)網絡中從節(jié)點 u0到 節(jié)點 vk開始于時間ts的時序路徑為連邊序列：

該序列滿足：

1)對所有i， i= 0,1···,k ?1,ui+1=vi；

2) 對所有i， i= 0,1···,k ?1,ti

3) t0ts。

那么該時序路徑的間隔時間為 tk? ts，且該間隔時間最短的路徑為最短時序路徑。定義從時間t開始節(jié)點 u到 節(jié)點 v的距離為最短時序路徑的間隔時間，用 dt( u,v)表 示；當路徑不存在時 dt( u,v)=∞。在此基礎上，定義時間t節(jié) 點u 的時序接近中心性如下：

實驗結果發(fā)現，節(jié)點重要性隨時間變化，捕捉節(jié)點全局重要性的聚合指標可能無用，但所提出的時序接近中心性有助于識別整個網絡時間間隔內一直很重要的節(jié)點，即節(jié)點在任意時間的時序接近中心性值都較大，則可以認定該節(jié)點在研究的時間間隔內一直很重要。

文獻[48]基于時序節(jié)點(節(jié)點索引和時間的組合)的最快時序路徑，提出了兩個時序節(jié)點在特定時間的中心性測度，并發(fā)現這兩個中心性測度對于時間標度的變化具有魯棒性。具體計算如下：令v=(v,τ),u=(u,τldt(v,u)),w=(w,τeat(v,w))。根據靜態(tài)網絡中的覆蓋率定義了時序網絡中的覆蓋率。如果滿足以下兩個條件，則時序節(jié)點 v覆蓋了節(jié)點對(u,w)：

1) τeat(u,w)=τeat(v,w)，即如果順便經過時序節(jié)點v，從時序節(jié)點u 出 發(fā)到達 w的最早時間不變；

2) τldt(w,u)=τldt(v,u)，即如果順便經過時序節(jié)點v，到達時序節(jié)點 w 從u 出發(fā)的最晚時間不變。

基于時序覆蓋率的定義，定義了時序覆蓋中心性(TCC)，即時序節(jié)點 v= (v,τ)所覆蓋的節(jié)點對(u,w)∈V×V ( V是網絡中的所有節(jié)點)的比例。如果時序節(jié)點 v的TCC 的值越接近1，說明該節(jié)點覆蓋的節(jié)點對越多，則其越中心。

由于即使移除TCC 值大的時序節(jié)點，也不能總是使 τeat(v,w)更 大或者 τldt(w,u)更小，所以在時序覆蓋率的基礎上加入額外的標準定義了邊界覆蓋率。如果滿足一下條件，就說時序節(jié)點 v在邊界上覆蓋了節(jié)點對 (u, w)： 1) (u, w)被 時序節(jié)點 v覆蓋；2)τeat(u,v)=τ 以及 τldt(w,v)=τ。

在此基礎上，定義時序邊界覆蓋中心性(TBCC)，即時序節(jié)點 v= (v,τ)在邊界上所覆蓋的節(jié)點對(u,w)∈V×V ( V是網絡中的所有節(jié)點)的比例。與時序覆蓋中心性相似，如果時序節(jié)點 v的TBCC 的值越接近1，說明該節(jié)點覆蓋的節(jié)點對越多，則其越中心。實驗結果表明真實時序網絡中的大量高中心性節(jié)點位于特定時間的很窄的時間窗內，而且大量信息會在短時間內通過少量重要的時序節(jié)點。

最近，文獻[64]基于明顯路徑流的時序網絡模型和節(jié)點重要性依賴于其鄰居重要性的觀點，提出了一個時序信息聚集過程(TIG-process)以識別時序網絡中的關鍵節(jié)點?；跁r序信息聚集過程，作者對比了最快到達路徑和最短時序路徑在節(jié)點重要性識別中的區(qū)別，并結合時序信息聚集深度、不同距離鄰居的重要性以及節(jié)點的初始信息分別給出了依據兩種最短路徑對節(jié)點重要性進行排序的tig-分數。經實驗驗證發(fā)現，在利用最快到達路徑評價節(jié)點間距離時可以獲得更好的識別性能，且可得到最優(yōu)的信息聚集深度，因為最快到達路徑可以聚集更多的時序信息。

基于時序最短路徑的指標是時序網絡中關鍵節(jié)點識別的一類重要方法，此類方法的重要區(qū)別在于定義時序最短路徑，是否考慮了如下諸多因素并對其做了何種處理，具體包括路徑的起始時間和終止時間、無窮路徑的處理方式、信息隨時間和距離的衰減，以及最短路徑究竟定義為途徑節(jié)點數目最少的路徑還是花費時間最少的路徑等。其優(yōu)勢在于通過對時序路徑和時序距離的定義，可以更好地捕獲時序網絡中的時間特性，但同時也存在計算復雜度提高、時間成本增加等問題。

應注意，節(jié)點的最短路徑數并不總是測量某節(jié)點中心性的最好方式，最短路徑也并不總是和相應的過程相關，比如疾病總是通過任意路徑隨機傳播，謠言總是沿著長于最短路徑的路徑進行傳播[30]。因此考慮隨機游走而不是最短路徑的節(jié)點識別方法也同樣重要，后文將在基于動力學的識別方法中討論時序網絡中基于隨機游走的識別方法。

2.1.3 基于K-核分解的識別方法

K-核分解用于靜態(tài)網絡中的關鍵節(jié)點識別和節(jié)點重要性指標設計，早已得到普遍認可和實踐。其中文獻[59]于2010 年首次運用K-核分解獲得的節(jié)點重要性的排序指標(k-shell)，以及在此基礎上不少學者進行的相關拓展。比如文獻[65]進行加權網絡中的K-核分解，提出了加權網絡中的ks 指標；文獻[66]綜合考慮目標節(jié)點自身K-核的信息和與網絡最大K-核的距離，提出新的度量節(jié)點重要性的指標；文獻[67]基于最小K-核節(jié)點鄰居集合中最大ks 值，提出了更深度的指標。在時序網絡的研究中，文獻[38]進行了時序網絡中基于邊的k-shell 分解，提出了同時考慮自身和鄰居的時序k-core 值的表征時序網絡中節(jié)點重要性的時序指標。其具體的分解方法和節(jié)點重要性計算指標如下：

1) 網絡快照創(chuàng)建：設置時序網絡的時間窗口大小為 T ，得到快照網絡序列 N1,N2,···Nm；

2) 快照中邊權計算：在每個快照網絡Nt(t=1,2,···,m)中，按照最初的k-shell 分解方法求得節(jié)點的k-shell 值，節(jié)點 i在 快照 Nt中的k-shell 值記為。對快照Nt，連邊( i,j)的 權值定義為=min

與此同時，為驗證同時考慮節(jié)點自身和鄰居的時序k-core 值的時序指標 TK (i)的優(yōu)越性，作者基于K-核分解提出3 個對比時序指標：

1) SK：靜態(tài)k-shell 值表征時序網絡中的核值；

2) TKD：同時考慮節(jié)點自身和鄰居的時序kcore 值的時序指標 TK (i)除以節(jié)點在靜態(tài)網絡中的度k(i)

以上4 個指標( TK ,SK,TKD,ASK)，均滿足節(jié)點對應的指標值越大越重要的規(guī)律。

基于K-核分解的識別方法除了考慮節(jié)點的位置屬性隨時間的變化，同時也考慮了隨時間變化節(jié)點間的連邊關系。通過在不同時間快照中進行K-核分解，初步獲得節(jié)點的瞬時核值；然后再將節(jié)點的瞬時核值映射到靜態(tài)圖的邊，并通過邊的核值獲得節(jié)點的全局時序核值。目前在時序網絡關鍵節(jié)點識別的研究中，這種從點到邊再到點的重要性傳遞方法尚不常見。

2.1.4 基于特征向量的識別方法

靜態(tài)網絡中的特征向量中心性[68]、PageRank[69-70]、樞紐值與權威值(即HITS)分數[71]以及特征因子[72]等基于特征向量的中心性測度，它們作為特征值問題的解決方案出現，常常通過計算中心性矩陣的主特征向量的元素獲得，是一類簡單且重要的節(jié)點重要性排序方法。

將此類方法推廣到時序網絡，文獻[44]提出了一種在有序多層圖表示的時序網絡中基于特征向量的中心性測度的泛化方法，該方法通過在超中心矩陣( NT ×NT維矩陣)中耦合時間層中心性矩陣(以權重 ω最相近的時間層間相同節(jié)點的耦合)實現。超中心矩陣用權重 ω表 示為 C( ω)，經轉換ε=1/ω變 成超中 心矩陣 C(ε)。 C(ε)的主特征向量v(ε)表 示 所 有 節(jié) 點-時 間 層 對 (i,t)的 聯(lián) 合 中 心 性(jointly centrality)，即表示時間層 t節(jié) 點 i的中心性，長度為 NT ，其中 N為節(jié)點數，T 為時序網絡中的時間層數。具體計算公式如下：

在聯(lián)合中心性的基礎上，將特征向量 v(ε)映射為 N× T 維矩陣W ，其中Wit=vN(t?1)+i(ε)，定義邊際節(jié)點中心性 xi( MNC)和邊際時間層中心性 yt(MLC)，分別反映節(jié)點和時間層的重要性。計算公式分別如下：

考慮特定的時間層t，有節(jié)點-時間層對 (i,t)的條件中心性 Zit，表示時間層t上 節(jié)點i相對于其他節(jié)點的重要性。計算公式如下：

實驗結果證明，所提的條件中心性和邊際中心性確實有效，通過這些中心性測度可以動態(tài)識別不同時間的重要節(jié)點，且中心性測度的值越大，節(jié)點越重要。

文獻[45]在文獻[44]的基礎上提出了改進，認為時序網絡建模中層間關系的參數表示忽略了不同節(jié)點層間連接關系的差異性。受文獻[29]對時序相關系數以及文獻[32]對時序網絡中鄰居拓撲重疊系數研究的啟發(fā)，文中將節(jié)點的層間連接關系用鄰居拓撲重疊系數表示，提出了基于節(jié)點層間相似性的超鄰接矩陣時序網絡構建方法。利用特征向量中心性指標，獲取節(jié)點在各個時間層上的重要性排序，從而研究節(jié)點重要性隨時間變化的軌跡。實驗證明，改進后的模型獲得的結果優(yōu)于文獻[44]的結果。

基于特征向量的識別方法與前三種基于拓撲結構的識別方法不同，其獲得的往往不是全局的節(jié)點重要性排序，而多用于獲得對應時間快照上的節(jié)點重要性排序以及不同時間快照上的重要性排序，因此結果相對而言更微觀且更真實，但難以實現全局上節(jié)點重要性的判斷。

2.2 基于動力學的識別方法

除了網絡結構之外，節(jié)點在網絡動力學行為中的影響力也常常被用來作為節(jié)點重要性的評判標準。目前，基于網絡動力學的識別方法可以粗略的分為基于隨機游走和傳播動力學兩類。

2.2.1 基于隨機游走的識別方法

過去基于隨機游走的方法，如Katz 中心性[73]、PageRank[74]、LeaderRank[75]等，已經很好評估了靜態(tài)網絡中的節(jié)點重要性。由于基于隨機游走的排序算法結合了網絡的拓撲屬性和動力學屬性，且不受網絡中信息多少的限制，這使得對隨機游走過程的研究以及對網絡中基于隨機游走的重要節(jié)點識別方法的研究逐漸拓展到時序網絡。關于時序網絡中的隨機游走過程：文獻[76]研究了時序網絡的可達性及連通性，并提出了一種與靜態(tài)網絡中隨機游走的譜間隔類似的結構測度表征時序網絡的連通性；文獻[77]分析了基于時序網絡數據的隨機游走模型的覆蓋率和平均首次通過時間，提出了時間最快的路徑和距離最短的路徑，發(fā)現時序網絡中的擴散相對靜態(tài)圖更慢；文獻[42]則將時序網絡數據和隨機游走的穩(wěn)定狀態(tài)概率結合起來。關于時序網絡中基于隨機游走的重要節(jié)點識別方法，部分研究是基于靜態(tài)指標的改進，另有部分研究則是基于時序網絡和隨機游走的特征，或是基于具體的隨機游走過程而提出的全新的指標。

靜態(tài)圖中基于隨機游走的經典例子是Katz 中心性[78]。其基本觀點是節(jié)點i和 節(jié)點 j溝通的傾向性可以根據從節(jié)點i到 節(jié)點 j 的長度為 ?= 1,2,3,···的隨機游走路徑數目決定，長度 ?較長的隨機游走路徑更重要，因此最初的想法是選擇適當的參數 α對長度為 ?的游走路徑按照 α?進行縮放。節(jié)點i和節(jié)點j之間長度為 ?的游走路徑數目對應鄰接矩陣 ?次冪的元素。因此矩陣 S= I+αA+α2A2+···的元素sij測 量了節(jié)點i和 節(jié)點 j 溝通的傾向性。當 α< ρ(A)鄰接矩陣的譜半徑時，矩陣S 可以收斂至 (I ? αA)?1。那么，節(jié)點i的Katz 中心性為矩陣 S 第i行的和，計算如下：

文獻[79]建立時間窗圖模型，通過類似的原理將Katz 中心性拓展到時序網絡。以 A(t)表示第t個時間窗對應的鄰接矩陣，那么任意長度 k的時序游走路徑的計數按如下形式獲得：

當 α< mintmρ(A(tm))，則有溝通性矩陣：

根據溝通性矩陣Q，定義傳播中心性以及接收溝通性，具體計算分別如下

文獻[80]則基于文獻[79]提出的時序網絡中的溝通性矩陣 Q，對文獻[81]和文獻[82]提出的基于隨機游走的溝通介數(communicability betweenness)和分解介數(resolvent betweenness)進行了相關拓展，并提出了基于隨機游走的時序網絡中節(jié)點 v的介數。具體計算如下：

對于時序網絡中PageRank 值的研究，大多仍然是融入時間因素的靜態(tài)PageRank 值。其中比較典型的是PageRank 值計算時加入與時間相關的衰減因子[83-86]，或結合不同類型網絡(如引文網絡[87-88]、體育社會網絡[89]、社交網絡[93]等)隨時間變化的特征改進轉移矩陣從而計算靜態(tài)PageRank 值。但是，文獻[24]則明確將時序網絡表示為基于靜態(tài)圖的時序網絡模型(連邊上的時間戳表示相應的到達時間)，并基于時序網絡中的隨機游走，結合時間信息和網絡動力學提出時序網絡中的時序PageRank，以此估計任何時間t節(jié) 點u 的重要性。具體計算方法如下：

首先，定義時序網絡 G中時間相關的隨機游走，即時序隨機游走為如下邊序列：

其中 ti? ti+1(1 ?i ?j?1)。

其次，對節(jié)點u 在靜態(tài)網絡中的PageRank 得分π(u)進行調整(如下公式)，使得計算只考慮時序游走而不是所有的游走。

調整過程如下：假設 ZT(v,u|t)是 從節(jié)點 v出發(fā)在時間t前到達節(jié)點 u的所有時序游走的集合，那么某特定的時序游走 z ∈ ZT(v,u|t)的概率

式中， c(z|t)是 所有從節(jié)點 v 出發(fā)在時間t前到達節(jié)點u的時序路徑的數目，分母表示所有從節(jié)點v 出發(fā)的與時序游走z 路徑長度相等的時序游走數。

結合上述兩個公式，節(jié)點 u在 時間t的時序PageRank 分數的計算公式為：

同時，由于上述時序PageRank，時序隨機游走開始的節(jié)點是u 的 概率與從節(jié)點 u開始的邊的數目成正比。假設向量 h′表示游走開始概率向量，即包含所有節(jié)點作為游走開始節(jié)點概率的向量。則對于節(jié)點u， 向量 h′中 的元素滿足對于所有節(jié)點v ∈ V，有h′(u)=(u,v,t)∈E/|E|。此外，給定個性化的特征向量h?，可得個性化的時序PageRank 值的計算公式為：

該個性化的時序PageRank 值越大，表明節(jié)點越重要。在此基礎上，文獻[24]提出了一個計算該時序PageRank 值的算法，并證明算法可以收斂，且當邊分布是靜態(tài)時可以收斂到靜態(tài)網絡的PageRank 值。真實數據上的結果也驗證了該方法的合理性，并表明其是一個靈活的測度，可以根據網絡隨時間的變化而調整。

文獻[40]提出的TempoRank 是基于隨機游走的時序網絡的中心性測度。該測度是基于明確路徑流的時序網絡模型在時間周期邊界條件下隨機游走的固定密度(即達到穩(wěn)態(tài)時可在節(jié)點中找到游走者的概率)，其與時序網絡對應的靜止加權有向網絡中的節(jié)點連入強度高度相近。具體求解過程如下：

1) 定義每個快照中節(jié)點對i 和j 之間的轉移概率(以第t個快照為例， ωij(t)表 示該快照中節(jié)點i與節(jié)點 j間的接觸次數，則第t個快照對應的鄰接矩陣為 ω(t )=(ωij(t)))

式中，當 i=j 時 δij=1， 否則 δij=0； q表 示節(jié)點i為非孤立節(jié)點時，不轉移到其他某一鄰居節(jié)點的概率； si(t) 表示在第t個 快照中節(jié)點i的所有連邊數量之和(即節(jié)點i的強度)，且有

當 si( t)=0 時表示節(jié)點i是 孤立點，當 si( t)1表示節(jié)點i是非孤立點；

2) 定義時序網絡一個周期的轉移矩陣為

式中， r表示一個周期內的所有快照的數目，B(t)=(Bij(t))是 第t個 快照的轉移矩陣。定義 Ptp的左側主特征向量(對應的特征值為1)為

文獻[39]從時間窗圖模型出發(fā)，規(guī)定每個時間窗為連邊不可變的有向圖快照Gt，定義其對應的鄰接矩陣為 A(t)?；凇叭绻麆討B(tài)網絡中的一個節(jié)點經過一段時間對另一個節(jié)點產生影響，那么在不同的時間存在一條可以通過中介連接起點和終點的路徑”的思想，提出了新的節(jié)點中心性測度?？紤]未來快照網絡Gtk+1的狀態(tài)除了依賴于當前快照網絡Gtk的狀態(tài)，是否還依賴于之前的狀態(tài)，將時序網絡中的信息傳播建模為無記憶的動力學過程和有記憶的動力學過程，分別如下。

令 ?1,n是 信息從時間 tk的任意節(jié)點i傳遞到時間tn的節(jié)點 j 的時間間隔 {t1,t2···,tn},(1 ?k ?n)。那么在給定的時間間隔 ?1,n內從節(jié)點i到 達節(jié)點 j的累積期望信息量由下面累積動態(tài)中心性矩陣的 (i,j)位置元素給定：

2) 有記憶的動力學過程，未來快照網絡Gtk+1的狀態(tài)依賴于之前所有快照網絡 Gti(i ?k)的狀態(tài)。除了上述的衰減因子 α 和 β，該過程定義了保留概率γ(0 ?γ ?1)和 保 留 時長 m( m ∈1,2,···n)，保 留 概率γ表示節(jié)點保留在時間 tk接收到的信息直到時間tk+1的概率。那么，依賴于之前時間鄰接矩陣的時間 tn的保留鄰接矩陣 R(tn)如下：

保留動態(tài)中心性矩陣為：

時間間隔 ?1,n內的保留累積動態(tài)中心矩陣為：

文獻[34]針對動態(tài)時序網絡，提出了一種實時性消息傳播過程中識別“最近較活躍”節(jié)點的方法。該方法擴展靜態(tài)網絡中基于通路(walk，即點邊交替出現的序列)的節(jié)點中心性分析方法到隨時間動態(tài)演化的網絡中，將消息傳播路徑分解到時間-空間兩個維度上，并利用兩個衰減因子分別刻畫消息的效用隨傳播路徑長度衰減及隨時間推移衰減這兩種自然特性，利用節(jié)點的歷史相遇信息，得到了節(jié)點傳播能力的量化分析函數，以此刻畫節(jié)點對時效性消息的相對傳播能力?；诳煺盏臅r序網絡模型，具體方法如下：

1) 定義動態(tài)通路為在一個非遞減的離散時間序列 t1? t2?···?tr?···?tk(t1,tk∈T)上的頂點與連邊的序列 vie1v1e2···vmervm+1···ewvj構 成節(jié)點i到節(jié)點j 的長度為 w的動態(tài)通路，當且僅當第r 個快照的鄰接矩陣滿足

2) 從空間維度和時間維度出發(fā)，將動態(tài)通路明確分為空間通路(在某單一靜態(tài)快照中形成的通路)和時間通路(由若干個連續(xù)或不連續(xù)快照的通路組成)。

3) 考慮所有動態(tài)通路的組合，按照“長步長通路賦予較小權重，短步長通路賦予較大權重”的原則，計算動態(tài)時序網絡的動態(tài)中心性指標矩陣Dt，有

展開式中，在節(jié)點的動態(tài)通路加權公式中加上n×n維 矩陣I，表示節(jié)點把消息傳遞給自己。同時，可以發(fā)現在同一拓撲快照內長度為 w的通路按照 βw/w!的方式衰減，利用不同拓撲快照完成的長度為 w的通路按照 βw/(l1!l2!···lr!)的方式衰減，其中w=l1+l2+···+lr表示跨越了 r個拓撲快照完成了長度為 w的通路，并在第 r 個快照中完成了 w中的lr步。

4) 由于上述衰減方式只按照通路長度對時間通路與空間通路進行衰減，并未體現節(jié)點之間產生影響的先后順序或消息的實時性，即未考慮動態(tài)通路產生的時間先后順序。因此考慮節(jié)點之間消息(影響)的實時性，基于“節(jié)點之間的影響強度或消息效用往往隨時間推移而遞減”的原則，提出了傳播實時消息的關鍵節(jié)點發(fā)現的迭代計算公式：

式中， ?tk+1=tk+1?tk， tk(k ∈N)表 示第 k個快照中產生的動態(tài)通路的發(fā)生時刻，值越大表示距當前時刻越近，那么該時刻的影響越重要，該時刻產生的動態(tài)通路受到較少的衰減； Qk∈n×n維矩陣表示截止到第 k個快照時動態(tài)時序網絡中節(jié)點的影響力矩陣， Q0=0； Ak表示第 k個快照網絡對應的鄰接矩陣；α為時間衰減因子，表示對時間因素按照自然指數方式衰減； e?α?t表示對不同靜態(tài)快照中的通路按照快照產生的先后順序進行衰減，并保證同一個靜態(tài)快照中不同長度的空間通路在時間維度上的衰減程度相同。另外， Qt+11、 (Qt+1)T1分別表示節(jié)點傳播、獲取實時性消息的關鍵程度，其中1 是n×1維 向量1 = (1,1,···,1)T。應用于移動P2P 社會網絡的實驗結果驗證了該方法的可行性，且可以明顯觀察到利用該方法選出來的關鍵節(jié)點作為消息傳播的起始節(jié)點，網絡消息的覆蓋速率明顯提升。

所述的基于隨機游走的識別方法，主要有3 類：1)基于Katz 中心性的時序拓展指標，分別有傳播中心性(衡量節(jié)點傳遞消息給其他節(jié)點的程度)、接收溝通性(衡量節(jié)點接收其他節(jié)點傳遞消息的程度)以及時序介數中心性(節(jié)點作為溝通網絡中中介的傾向性)，該類指標主要可用于溝通網絡或信息傳播網絡中起重要傳播作用的關鍵節(jié)點識別；2)基于PageRank 值的時序拓展指標，除了考慮時間衰減和網絡的特征的靜態(tài)PageRank 值，還有一類通過將靜態(tài)PageRank 的隨機游走拓展到時序隨機游走獲得的時序PageRank 值。該時序PageRank 更能反映網絡中真實的信息流動，且考慮到邊分布的變化能造成節(jié)點重要性的變化，估計的是任何時間t 節(jié)點u 的重要性，同時該時序指標也很好地實現了與靜態(tài)網絡中PageRank 值的契合，即當網絡生命周期中邊分布不變時，時序PageRank 值等于靜態(tài)PageRank 值；3)基于時序網絡中隨機游走的時序指標，此類指標脫離了靜態(tài)網絡中對節(jié)點重要性判斷的指標，僅僅通過時序隨機游走便可估計節(jié)點的重要性，其中的關鍵在于時序網絡隨機游走中轉移概率、衰減因子的設定。在此基礎上，計算游走達到穩(wěn)態(tài)時到達對應節(jié)點的概率，以及以節(jié)點作為消息傳播的起點，通過隨機游走查看消息覆蓋的速率，從而可獲得節(jié)點的重要性衡量指標。相對基于最短路徑的識別方法，基于隨機游走的識別方法所考慮的信息傳播路徑范圍不再受限于時序最短路徑，也無需再考慮用路徑長度最短還是時間間隔最短定義時序最短路徑。

2.2.2 基于傳播動力學的識別方法

目前，大多數網絡傳播動力學相關研究主要基于經典的流行病傳播動力學模型[91-92]。真實世界中的觀點、消息、疾病、惡意軟件等的傳播都可以建模成網絡中的傳染過程[93-96]，傳染過程可以用于研究網絡的結構特性及其組成部分的相對重要性[31]。從該角度出發(fā)，提出時序網絡中表征節(jié)點傳播影響力的指標，是基于網絡拓撲結構識別方法的重要延伸和拓展。

文獻[97]從網絡結構的拓撲特征和動力學屬性出發(fā)，提出了可以直接用于靜態(tài)網絡中有影響力傳播者定位的對動力學敏感的中心性(dynamicssensitive centrality)指標，并通過在4 個真實網絡中進行SIR 傳播模型和SI 傳播模型的擬合，發(fā)現該指標優(yōu)于度中心性、k-shell 指標以及特征向量中心性。具體方法如下：

對 t>1，有

式中，I 為單位矩陣。令 H =βA+(1?μ)I，則：

因此，在時間1 和t之間節(jié)點被感染的累積概率近似為：

定義 Si(t) 為在時間t節(jié) 點i的傳播影響，以節(jié)點i為初始感染節(jié)點時其他所有節(jié)點感染概率的總和表示。若 ei= (0,···,0,1,0,···,0)T是只有第i個元素為1 的 n×1維 向量，則在時間1 和t之間節(jié)點被感染的累積概率 x(t)可表示為

由此可知，以節(jié)點i為初始感染節(jié)點， x(t)實際為 βA ,βAH,···,βAHt?1的 第i列 元 素 之 和。因 為x(0)=ei且 Si(t) 是 x(t)的所有元素之和，故：

式中， L= (1,1,···,1)T是 所有元素為1 的 n×1維向量。由于 AT=A， HT=H ， AH =HA，故所有節(jié)點的傳播影響可寫為：

在SI 傳播模型中， μ= 0時 若 t → ∞， 則 S(t)也將無窮大。

在此基礎上，文獻[98]將該指標拓展到時序網絡，基于時間窗圖模型擬合SIR 傳播模型，提出了時序網絡中有影響力傳播者定位的時序對動力學敏感的 中 心 性 (temporal dynamic-sensitive centrality)指標，并通過在3 個真實時序網絡和一個理論時序網絡擬合SIR 傳播模型，發(fā)現其結果優(yōu)于利用靜態(tài)和時序的度中心性、接近中心性、介數中心性的結果。該方法的改進在于，該指標的計算基于時間窗圖模型，傳播過程中的鄰接矩陣是時間窗圖模型中各個快照對應的鄰接矩陣，而不始終是簡單無向連通圖對應的鄰接矩陣A。具體方法如下：

用鄰接矩陣 A(t)表 示第t個時間窗的快照網絡，仍然假設 x(t)表 示不超過時間t節(jié)點被感染的累積概率， P(t )=x(t)?x(t ?1) 表示節(jié)點在時間步t被感染的概率，其中 P(0 )=x(0)表示初始狀態(tài)；假定SIR 傳播模型中易感節(jié)點與感染節(jié)點接觸的感染概率為β，感染節(jié)點康復的恢復概率為μ。假設只有唯一的初始感染節(jié)點i， 那么 xi( 0)=1，則有

用數學歸納法求解可得：

Si(t)表 示傳播影響，即在時間t節(jié) 點i 的感染概率的總和

因為 A( t)T=A(t)， [H(t)]T=H?(t)，所以有

式中， V= (1,1,···,1)T； S(t)即為本文所提出測量節(jié)點在時序網絡中傳播影響的指標。該指標值越大，說明節(jié)點的傳播影響越大，則節(jié)點越重要。

基于傳播動力學的關鍵節(jié)點識別方法并不常見，但其往往作為測量標準，評價其他識別方法的好壞。后面在時序網絡中關鍵節(jié)點識別方法的評價指標中將進一步說明。

2.3 基于機器學習的識別方法

目前，機器學習結合復雜網絡的研究逐漸增多，基于網絡的機器學習算法的應用越來越廣泛[99]，包括理論研究中網絡的社區(qū)檢測[100]、動態(tài)網絡中的鏈路預測[101]或網絡中的動態(tài)鏈路預測[102]，以及現實社會中水電氣等供應網絡中的可達性[103]，城市運輸網絡中的交通預測[104]等。

將機器學習方法用于網絡中關鍵節(jié)點的挖掘也引起了大量學者的關注。如文獻[105]將社會網絡分析引入機器學習模型來預測P2P 行業(yè)的用戶違約，首先基于知名互聯(lián)網金融公司閃銀所提供的大規(guī)模脫敏數據，從復雜網絡的視角加以分析，然后將分析結果轉化為機器學習的輸入特征，用支持向量機的方法挖掘其內在的關聯(lián)，從而實現利用用戶的社會網絡結構性質預測用戶的信用情況。

此外，文獻[106]也通過機器學習的方法預測了社會網絡中最有力的說服者，其以時間T 為界，以在此之前的數據作為訓練數據，剩余的數據作為測試數據，探索了一種基于機器學習的預測關鍵節(jié)點的間接方式——首先基于社會網絡理論，提出社會影響 Ik、 實體相似 Rk及結構等效 Mk這3 個影響實體說服能力的影響因素；然后以此3 因素為特征，個體的決策 Dk∈(0,1)為標簽，通過50 次自助采樣訓練決策樹模型取平均值以估計個體間的說服概率：

式中， nD表示訓練數據中節(jié)點的 Dk=1的數目；nL表示所達葉節(jié)點中訓練數據的數目， m取P(Dk=1)是 訓練數據中 Dk=1的先驗概率。然后根據說服概率提出表征個體說服能力的指標值如下：

式中， pij是 所求的實體i說 服實體 j 的概率； cj表示實體i 服能力，由說服概率和其他所有實體vj∈V,的說服能力共同決定。通過冪迭代算法求解表征實體說服能力的指標值，值越大，則對應的實體越重要。

文獻[55]基于用戶-對象的二分網絡，將數據劃分為過去的時間窗和未來的時間窗，以識別并預測電子商務平臺或者社交媒體平臺中的關鍵節(jié)點，即未來流行或重要的對象(商品、對象或推文等)。具體地，考慮復雜網絡中驅動節(jié)點流行性的3 個影響因子(偏好連接、最近的流行度以及衰變)，提出表征節(jié)點在未來時間流行度或重要性的預測分數模型如下：

式中， Tp表 示過去的時間窗； s0( t,Tp)表示基于過去時間窗 Tp在 時間t對 象的預測分數；λ是調整新穎性和總流行性的參數；Tuo表示用戶u 消 費對象o 的時間；γ為自由參數。然后，基于過去時間窗中的數據用梯度下降算法求解出模型中的參數，迭代過程如下：

式中， ?e表示誤差。最后通過預測分數模型進行未來時間窗中對象流行度或重要度的預測，并根據準確率、新穎性、時序新穎性以及AUC 等值評價模型的好壞。該應用雖然未涉及具體的時序信息，但在一定程度上引入了時序概念，為后續(xù)開展將機器學習方法用于時序網絡中關鍵節(jié)點識別的研究提供了參考。

2.4 其他識別方法

除以上3 類方法外，有些研究從其他視角提出了關鍵節(jié)點的識別方法。如文獻[36]提出馬爾科夫時序網絡模型，沒有直接給出時序網絡中的Katz 中心性的靜態(tài)表示，而是通過成本最低不斷調整馬爾科夫時序網絡中邊的權重以優(yōu)化給定節(jié)點的Katz 中心性測度，解決的是一個關鍵節(jié)點識別的優(yōu)化問題。

文獻[107]通過對辦公大樓中面對面接觸的時序數據的研究，發(fā)現一種無需完全了解時序網絡，便可以根據部門的組織結構，獲得關鍵節(jié)點的方法。具體地，根據各個部門中節(jié)點在部門內的連邊與在部門間的連邊數量，將節(jié)點分為居住者(有更多的部門內連邊)、閑逛者(有更多的部門間連邊)和連接者(部門內連邊和部門間連邊各占一半)，其中連接者被定義為重要節(jié)點，因為他們的介數中心性更大，且在增強部門間的溝通方面起重要作用。

文獻[53]結合圖挖掘和序列挖掘，基于靜態(tài)結構屬性和時序行為屬性提出了一個識別信息擴散中活躍的有價值的節(jié)點的方法。具體的流程如下：首先，建立定量的時序聚合圖，在此基礎上根據社區(qū)探測算法揭示結構屬性，并選擇活躍有價值節(jié)點的候選者，這些候選者是社區(qū)的核心且是連接兩個社區(qū)的橋梁；然后，運用序列挖掘算法從活動記錄中提取候選者的行為趨勢；最后，通過分析行為趨勢的空間-時間特征，將候選者分為活躍節(jié)點與非活躍節(jié)點，于是得到活躍的有價值的節(jié)點。該方法通過對時間行為特征的跟蹤，無需分析每個網絡快照的結構。因此，具有相對較低的計算成本，且不會丟失活動有價值節(jié)點識別的準確性。

鑒于很多現有的時序網絡中的節(jié)點中心性指標很少考慮不同快照中節(jié)點影響的關系，而一般而言，如果一個節(jié)點連接到更多在后續(xù)的快照中有更多鄰居的節(jié)點，那么該節(jié)點可能是一個更重要的傳播者。文獻[35]從信息論的角度將靜態(tài)網絡中基于熵的中心性擴展到了時序網絡，定義是快照t中節(jié)點 vi的鄰居集合，是 快照t中 節(jié)點 vi的鄰居集合中節(jié)點的數目，定義是快照t中 節(jié)點 vi的信息，則有

由于快照t中 節(jié)點 vi的影響不僅由其鄰居數決定，還受其鄰居影響的影響?；诖?，定義為快照t中 節(jié)點 vi的影響，則有

式中， p ∈ [0,1]， 表示 t+1時 刻的節(jié)點 vi在多大程度上決定t時刻的節(jié)點 vi的影響。該指標值越大，說明節(jié)點在快照t中影響力越大，則該節(jié)點在相應的時間越重要。特別地，由于在最后一個時間戳圖中，不知道下一快照中節(jié)點 vi的鄰居影響，所以認為節(jié)點 vi的影響僅由其感染的不確定性決定，即有

同時由于當 t=1時，各節(jié)點的影響考慮了相鄰節(jié)點在整個時間段內的累積效應，所以作者利用t=1處各節(jié)點的影響衡量節(jié)點在計算機病毒時序網絡傳播過程中的重要性。

3 時序網絡中關鍵節(jié)點識別方法的評價指標

評價時序網絡中關鍵節(jié)點識別方法的效果有多種不同的角度，可以依據節(jié)點在網絡的結構和功能中的重要性，同時也可以與其他已有指標進行對比。一般而言，網絡中節(jié)點的重要性排序主要從網絡性能的變化、傳播效果的好壞、指標間的相關性三個角度驗證。

3.1 基于網絡性能變化的評價方法

網絡性能是考察節(jié)點對網絡結構的影響力的評價指標。節(jié)點刪除法是常用的利用網絡性能變化評價節(jié)點重要性的方法，其有累積刪除和依次刪除兩種思路[108]。假設網絡時序性能為 E(G )，首先按節(jié)點識別方法對節(jié)點重要性排序，再計算表征時序網絡性能變化的評價指標。具體有如下思路：

1) 分別衡量節(jié)點未刪除時的網絡性能以及節(jié)點刪除后的網絡性能，然后比較兩者的差值[24, 38, 45, 48]。記累積刪除σ 比例節(jié)點后的時序網絡性能為 E(G σ)，則計算如下：

若兩者差值越大，則說明節(jié)點對網絡性能的影響越大，同時也說明節(jié)點越重要，識別方法性能越好。

2) 設定網絡性能的閾值，觀察達到該閾值所需刪除的節(jié)點比例[108-109]。記累積刪除 σth比例節(jié)點后網絡性能達到閾值為 Eth(G)， 即有 Eth(Gσ)=Eth(G)，則計算如下：

若刪除的節(jié)點比例越少，則說明節(jié)點對網絡性能的影響越大，同時也說明識別出的節(jié)點越重要，識別方法性能越好。

3) 與上面直接刪除前 σ比例重要節(jié)點不同，這里按節(jié)點重要性排序依次刪除網絡中的節(jié)點直至網絡中所有節(jié)點被刪除。記節(jié)點vi刪除后的網絡性能為 E(G vi)，則計算如下：

該結果衡量單個節(jié)點依次移除后網絡性能的變化。若值越大，說明節(jié)點越重要，同時也說明識別方法有好的性能。

目前，針對時序網絡的衡量指標尚不多見，所用的方法大多是將靜態(tài)網絡中網絡性能的變量替換為時序網絡中定義的時間相關的變量。其中，較為常見的用于評價時序網絡關鍵節(jié)點識別方法的網絡時序性能指標是網絡時序效率和網絡時序最大連通分量：

1) 網絡時序效率：時序網絡中信息傳播效率的衡量指標，較小的值意味著信息能夠在時序網絡中更快傳播開。該時序性能指標來源于靜態(tài)網絡中的網絡效率[110]，即所有節(jié)點接近中心性的均值，定義如下：

式中， dij表示節(jié)點對 (i,j)間的最短路徑。在時序網絡中，基于不同的時序最短距離或時序接近中心性的定義，文獻[27]、文獻[33]以及文獻[45]將網絡的時序效率定義為：

式中， dt( u,v)表 示開始時間為t的 節(jié)點對 (u,v)間的時序距離，時序距離通過時序最短路徑計算。開始時間t 不同時，同一節(jié)點對 (u,v)間的時序距離也不一定相同。此外，當節(jié)點對 (u,v)間不存在時序路徑時， dt( u,v)=∞。

2) 網絡時序最大連通分量：衡量時序網絡可達性的指標，是時序網絡最大連通圖中的節(jié)點數占整個網絡所有節(jié)點的比例[38]。該時序性能指標來源于靜態(tài)網絡中的最大連通分量，即最大連通分量中節(jié)點的比例，定義如下：

① 基于時序網絡模型，選取初始時間的節(jié)點u，依次遍歷各個時間點直至結束，統(tǒng)計可到達的節(jié)點數目為| ?u|[111]，則有

② 分別求解各快照的最大連通分量并取均值[38]，即

3.2 基于傳播模型的評價方法

基于傳播模型的評價方法主要考慮節(jié)點在網絡信息傳遞中的作用。其中，常用的傳播模型有SI 傳播模型、SIS 傳播模型和SIR 傳播模型。三類模型共呈現出節(jié)點的3 種狀態(tài)：易感染狀態(tài)(S,Susceptible)即未來可能被感染的健康狀態(tài)，感染狀態(tài)(I, Infected)即患病狀態(tài)，以及移除狀態(tài)(R,Removed)即從感染狀態(tài)恢復并具備抵抗力。

在SI 傳播模型中，只存在易感染狀態(tài)(S)的節(jié)點以概率β 被感染狀態(tài)(I)的節(jié)點感染，即有：

在SIS 傳播模型中，易感染狀態(tài)(S)的節(jié)點以概率β 被感染狀態(tài)(I)的節(jié)點感染，感染狀態(tài)(I)的節(jié)點以概率γ 恢復成為易感染狀態(tài)(S)的節(jié)點，即有：

在SIR 傳播模型中，假設易感染狀態(tài)(S)的節(jié)點以概率β 被感染狀態(tài)(I)的節(jié)點感染，感染狀態(tài)(I)的節(jié)點以概率γ 成為移除狀態(tài)(R)的節(jié)點，則有：

一般而言，在時序網絡中基于傳播模型對時序網絡的節(jié)點識別方法的效果進行評價，主要在時序網絡模型中模擬這三類傳播模型的時序傳播。該過程與靜態(tài)網絡中擬合的區(qū)別在于，節(jié)點對間連邊產生和消失的時序性，因此傳播也需考慮連邊形成的時間。具體做法為基于幾種關鍵節(jié)點的識別方法對節(jié)點的重要性進行排序，則幾種關鍵節(jié)點識別方法性能評判的具體思路有：其一，取相同數目最重要節(jié)點群為初始感染源，最能促進“疾病”傳染的關鍵節(jié)點識別方法則更優(yōu)；其二，取相同數目最重要節(jié)點群為免疫群體，最能阻止“疾病”傳染的關鍵節(jié)點識別方法則更優(yōu)。

關于“疾病”傳染的衡量指標，即是對節(jié)點傳播能力的衡量。一般而言，在SI 傳播模型或者SIS 傳播模型中，常常以達到穩(wěn)定狀態(tài)時被感染的節(jié)點數目表示；在SIR 傳播模型中，常常則以能夠傳播的平均距離表示。與此同時，也有不少文獻基于時序網絡模型的特征提出了新的評價指標，如文獻[31]基于真實時序數據集構建時間窗圖模型擬合SI 傳播模型，定義每個節(jié)點i的傳播影響力為一半節(jié)點患病時間。具體方法為：假設節(jié)點i是傳播源并在時間 t0,i第一次出現，其他節(jié)點都是易患病節(jié)點，到時間 ti有 一半節(jié)點患病，那么定義節(jié)點i的傳播能力為

式中，Ti值越小，表示節(jié)點i 對疾病的傳播能力越強，即節(jié)點i 更重要。進一步，從疾病免疫的角度提出單個節(jié)點的感染延遲率：

文獻[49]提出了一種網絡影響的基準方法，用TKO 分數表示。該方法結合了超級傳播者和免疫過程的影響，同時還包括感染的時間，能夠克服不同的測度針對具體的網絡結構有效以及傳統(tǒng)方法的不足，從而更準確地測量節(jié)點對傳播的影響。具體過程如下：

1) 選擇初始傳播源，基于時序網絡運行疾病傳播模型，同時獲取每個節(jié)點的狀態(tài)以及每次迭代的時間。其中，感染節(jié)點的數量及感染持續(xù)的時間是基于該初始傳播源的疾病量級(magnitude)。

2) 對于對應時序網絡中的每個時間層的節(jié)點，實施移除操作分析。即移除某節(jié)點，運行相同的動力學模型，測量疾病量級的變化，獲得該節(jié)點的基于初始傳播源的邊際感染分數。

3) 使用每個節(jié)點作為初始感染源，執(zhí)行過程1)和2)，獲得每個時間層每個節(jié)點基于不同的初始傳播源的邊際感染分數。取平均值作為所求的TKO 分數。

TKO 分數是一個全方面的經驗度量，可以捕獲到節(jié)點在每個時期影響疾病傳播的潛力，常用于評估其他影響測量方法的準確性，是一種有效的基準測量方法。

此外，文獻[112]基于8 個人類接觸數據集構建時序網絡、靜態(tài)網絡及全連通網絡進行SIR 傳播模型仿真。提出兩個評估指標：滅絕時間和爆發(fā)規(guī)模。定義沒有感染的個體存在時，該傳染病消失，滅絕時間即為從爆發(fā)到消失的時間間隔；定義傳染病消失時，恢復狀態(tài)個體的比例定義為爆發(fā)規(guī)模。

3.3 基于相關性的評價方法

時序網絡中的關鍵節(jié)點識別方法主要實現對節(jié)點重要性的排序，預測時序網絡中全局最重要的節(jié)點或者特定時間層的重要節(jié)點。若設定某一基準識別方法或已知節(jié)點真實的重要性排序，則可基于相關性評價所提出識別方法的預測性能。常用的相關性評價指標有Kendall’s τ 相關系數[113]以及Spearman相關系數[114]，兩者的取值范圍均為[?1, 1]，值越大，相關性則越強，即說明節(jié)點重要性的排序方法更優(yōu)。

文獻[97]在評估所提出的時序對動力學敏感的中心性這一關鍵節(jié)點識別方法的性能時，在4 個時序網絡中擬合SIR 傳播模型，以一段時間后感染節(jié)點的數目衡量節(jié)點的傳播影響，選擇隨機選擇初始感染節(jié)點的結果為基準，同時獲得根據靜態(tài)度/介數/接近中心性、文獻[47]提出的時序度/介數/接近中心性、時序對動力學敏感的中心性這七個指標選擇初始感染節(jié)點的傳播影響；然后分別計算按照七個指標選取初始感染節(jié)點的傳播影響與隨機選擇初始感染節(jié)點的傳播影響的Kendall’s τ(肯德爾系數)，發(fā)現根據時序對動力學敏感的中心性選取初始感染節(jié)點的傳播影響的相關系數最大，從而得知所提出方法有更高的精度。

文獻[45]在提出時序網絡中的各時間層網絡上節(jié)點的特征向量中心性(SSAM)的方法后，基于兩個實證網絡數據，用節(jié)點刪除法得到節(jié)點時序全局效率差值并排序，然后利用Kendall’s τ(肯德爾系數)計算特征向量中心性與時序網絡效率差值的相關性；同時按照文獻[44]提出的SAM 方法選取不同的參數以相同的方法計算相應的Kendall’s τ 系數。對比可知，SSAM 方法得到的Kendall’s τ 系數結果大部分比SAM 方法的高，說明其得到節(jié)點重要性排序更為準確。

此外，在利于過去的節(jié)點重要性排序結果表征未來的節(jié)點重要性排序時，常見的有將時間t的重要節(jié)點作為下一時間 t+1的預測[47]，或劃分訓練集和測試集將訓練集中的重要節(jié)點作為測試集的預測[55, 105]，一般在已知真實的節(jié)點重要性排序時可計算其與預測的節(jié)點重要性排序之間的相關系數，從而評價識別方法的好壞。在此情況下，準確率[106]也是常見的評價指標。其表示預測的前 K個重要節(jié)點在真實排序中的數目占比。計算如下：

式中， PK和 RK為選取預測排序和真實排序的前 K點序列。準確率越高，說明節(jié)點識別方法的性能越好。

4 結 束 語

本文在介紹時序網絡建模的基礎上，總結了現有主要的時序網絡中關鍵節(jié)點的識別方法以及時序網絡中針對關鍵節(jié)點識別方法的評價方法，為后續(xù)開展設計時序網絡中節(jié)點重要性指標提供了重要參考。關于時序網絡中關鍵節(jié)點的識別方法的總結見表1。然而，時序網絡中的關鍵節(jié)點識別方法大多是靜態(tài)網絡中的中心性測度基于時序網絡模型的拓展，對關鍵節(jié)點識別方法的評價指標也多源自靜態(tài)網絡。雖然此類改進確實起到了提升關鍵節(jié)點識別方法性能的效果，但仍然存在諸多亟待解決的問題：

1) 網絡的時序演化?，F有的時序網絡多考慮節(jié)點和連邊隨時間的增加和減少，尚未考慮網絡結構的巨變，如從星形網絡(關鍵節(jié)點最好的識別方法為度中心性)到橋連通網絡(關鍵節(jié)點最好的識別方法為介數中心性)的演化。在此情況下，簡單的靜態(tài)圖、時間窗圖模型、多層圖模型或路徑流模型不再能概括時序網絡模型的演化特征，基于一類模型設計標準一致的關鍵節(jié)點識別方法也難以捕捉到不同時間的關鍵節(jié)點。因此，需要尋找新的網絡抽象方法，同時也需要探索可以隨網絡結構變化而調整的關鍵節(jié)點識別方法。

2) 時序網絡中關鍵節(jié)點識別方法的內在關系。

基于不同的角度獲得了各種關鍵節(jié)點識別方法，但這些方法實際上存在一定的聯(lián)系，比如前面討論的基于特征向量的識別方法和基于隨機游走的識別方法。因此可以基于多個時序數據集構建不同的時序網絡模型，對比分析這些時序識別方法間的聯(lián)系和區(qū)別。

表1 時序網絡中的關鍵節(jié)點識別方法

3) 時序網絡中節(jié)點重要性的定義。相對靜態(tài)網絡中對關鍵節(jié)點識別的各種中心性測度，現有的時序網絡中對關鍵節(jié)點的識別方法大多仍然是基于時序網絡模型提出的全局時序靜態(tài)指標，因此忽略了節(jié)點的位置和功能隨時間而變化的情形；雖然有基于特定時間層的時序指標，但忽略了網絡結構隨時間變化的情形。而同一類型的時序指標只能探索節(jié)點在一個層面的重要性，因此在設計時序網絡中的關鍵節(jié)點時，可以同時結合網絡結構、節(jié)點位置以及節(jié)點功能等多方面的影響因素。

4) 時序網絡中基于機器學習的關鍵節(jié)點識別方法。隨著大數據時代的到來，機器學習由于能從海量數據中挖掘出有價值的信息而逐漸呈現出巨大優(yōu)勢。目前，機器學習方法已被應用于靜態(tài)網絡的關鍵節(jié)點分析并取得了較好的效果，機器學習有望應用于時序網絡探索關鍵節(jié)點的識別方法，因此可以從該角度出發(fā)進行嘗試性探索與應用。

本文研究還得到S-Tech 學術支持計劃?互聯(lián)網傳播學項目的資助，在此表示感謝。