時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的識(shí)別方法研究進(jìn)展

陳 詩(shī)，任卓明，劉 闖*，張子柯,2

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

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

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

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

本文按如下思路展開(kāi)：首先分析現(xiàn)有的時(shí)序網(wǎng)絡(luò)建模，再基于時(shí)序網(wǎng)絡(luò)模型從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、隨機(jī)游走動(dòng)力學(xué)以及機(jī)器學(xué)習(xí)的視角概括時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)的排序測(cè)度或中心性指標(biāo)；然后從網(wǎng)絡(luò)性能變化、傳播動(dòng)力學(xué)以及預(yù)測(cè)性能三個(gè)方面介紹時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的評(píng)價(jià)方法；最后在總結(jié)和展望部分指出了當(dāng)前面臨的問(wèn)題和可能的發(fā)展方向。

1 時(shí)序網(wǎng)絡(luò)建模

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

1.1 基于靜態(tài)圖的時(shí)序網(wǎng)絡(luò)模型

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

關(guān)于此類(lèi)時(shí)序網(wǎng)絡(luò)模型的研究，文獻(xiàn)[22]最早提出并將其用于研究時(shí)序網(wǎng)絡(luò)的連通性和推理問(wèn)題。之后，文獻(xiàn)[23]將模型中的連邊建為有向邊，研究了社會(huì)溝通網(wǎng)絡(luò)中的信息路徑結(jié)構(gòu)；文獻(xiàn)[21]將連邊上具體的時(shí)間信息轉(zhuǎn)化為相應(yīng)時(shí)間的邊對(duì)應(yīng)的有和無(wú)兩種狀態(tài)，探索了時(shí)序網(wǎng)絡(luò)中中心性測(cè)度的計(jì)算方法；文獻(xiàn)[24]也對(duì)時(shí)間聚合圖提出了改進(jìn)，其假設(shè)連邊有向且一對(duì)節(jié)點(diǎn)之間可能存在帶有不同時(shí)間戳的多條連邊，探索了時(shí)序網(wǎng)絡(luò)中的時(shí)序PageRank 的表示與計(jì)算。此外，文獻(xiàn)[1-2]也表示通過(guò)靜態(tài)圖表征時(shí)序網(wǎng)絡(luò)可以研究時(shí)序網(wǎng)絡(luò)的時(shí)序?qū)傩院屯負(fù)鋵傩裕?duì)相關(guān)的靜態(tài)圖進(jìn)行了簡(jiǎn)單介紹。

1.2 基于快照的時(shí)序網(wǎng)絡(luò)模型

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

1.2.1 時(shí)間窗圖模型

最常見(jiàn)的基于快照的時(shí)序網(wǎng)絡(luò)模型是如圖2 所示的時(shí)間窗圖模型。該模型將快照依次表示為時(shí)間聚合圖，快照的時(shí)間間隔即為時(shí)間窗口的大小。圖2b 中時(shí)間窗大小為 ω= 1，圖2c 中時(shí)間窗大小為ω=2。快照中的事件根據(jù)快照的時(shí)間間隔而定。

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

1.2.2 多層圖時(shí)序網(wǎng)絡(luò)模型

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

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

1.3 基于明顯路徑流的時(shí)序網(wǎng)絡(luò)模型

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

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

1.4 其他時(shí)序網(wǎng)絡(luò)模型

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

2 時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的識(shí)別方法

時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別方法的主要思路是基于時(shí)序數(shù)據(jù)構(gòu)建時(shí)序網(wǎng)絡(luò)模型，然后通過(guò)時(shí)序網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)或動(dòng)力學(xué)特征，采用網(wǎng)絡(luò)節(jié)點(diǎn)排序算法，識(shí)別關(guān)鍵節(jié)點(diǎn)。下面主要從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、動(dòng)力學(xué)以及機(jī)器學(xué)習(xí)方法三個(gè)方面介紹。

2.1 基于拓?fù)浣Y(jié)構(gòu)的識(shí)別方法

節(jié)點(diǎn)的重要性很大程度上是由節(jié)點(diǎn)在網(wǎng)絡(luò)上的結(jié)構(gòu)所決定的，依據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)節(jié)點(diǎn)的排序指標(biāo)，是時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別的一類(lèi)重要方法。目前，這些方法的提出多基于靜態(tài)拓?fù)渲笜?biāo)，如度中心性[56]、介數(shù)中心性[57]、接近中心性[58]、kshell 值[59]等。

2.1.1 基于度中心性的識(shí)別方法

靜態(tài)網(wǎng)絡(luò)中，節(jié)點(diǎn)中心性最直接的度量是度中心性[56]，即一個(gè)節(jié)點(diǎn)的度越大意味著這個(gè)節(jié)點(diǎn)越重要。在時(shí)序網(wǎng)絡(luò)，基于度中心性的時(shí)序節(jié)點(diǎn)中心性指標(biāo)也同樣是最直接的識(shí)別重要節(jié)點(diǎn)的依據(jù)。

文獻(xiàn)[47]基于明顯路徑流的時(shí)序網(wǎng)絡(luò)模型，首先提出了在一段時(shí)間 [i,j]內(nèi) 節(jié)點(diǎn) v ∈ V的時(shí)序度值

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

文獻(xiàn)[37]基于時(shí)間窗圖模型，對(duì)各個(gè)時(shí)間窗內(nèi)的時(shí)序度中心性值取標(biāo)準(zhǔn)差，提出了時(shí)序度中心性偏差值對(duì)節(jié)點(diǎn)重要性進(jìn)行排序。具體計(jì)算公式如下：

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

2.1.2 基于最短路徑的識(shí)別方法

靜態(tài)網(wǎng)絡(luò)中，介數(shù)中心性[57]和接近中心性[58]是基于最短路徑刻畫(huà)節(jié)點(diǎn)重要性的典型指標(biāo)。其中，介數(shù)中心性考量經(jīng)過(guò)某節(jié)點(diǎn)的最短路徑的數(shù)目，刻畫(huà)該節(jié)點(diǎn)作為中介對(duì)信息沿著最短路徑傳輸?shù)目刂颇芰Γ唤咏行男钥剂棵總€(gè)節(jié)點(diǎn)到其它節(jié)點(diǎn)的最短路徑的平均長(zhǎng)度，刻畫(huà)節(jié)點(diǎn)傳輸信息的速度。

時(shí)序網(wǎng)絡(luò)中，由于路徑受連邊產(chǎn)生時(shí)間和產(chǎn)生順序的影響，呈現(xiàn)出不同于靜態(tài)網(wǎng)絡(luò)中路徑的特征[29, 54, 61]，主要包括路徑的不對(duì)稱(chēng)性，未連通的節(jié)點(diǎn)更多，消息傳遞中的滯留或失效等。基于此，許多學(xué)者對(duì)時(shí)序網(wǎng)絡(luò)中的路徑、最短路徑以及距離重新進(jìn)行了考量，定義了時(shí)序路徑、時(shí)序最短路徑以及時(shí)序距離，并在此基礎(chǔ)上提出改進(jìn)后的時(shí)序介數(shù)中心性、時(shí)序接近中心性以及其他基于時(shí)序最短路徑的相關(guān)指標(biāo)。

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

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

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

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

式中， w 表示時(shí)間窗的大小； m表示時(shí)序網(wǎng)絡(luò)中時(shí)間窗的總數(shù)目。

關(guān)于時(shí)序接近中心性，直接擴(kuò)展靜態(tài)網(wǎng)絡(luò)中的計(jì)算公式得到時(shí)序接近中心性的計(jì)算如下：

所計(jì)算的節(jié)點(diǎn)的時(shí)序介數(shù)中心性和時(shí)序接近中心性的值越大，表明節(jié)點(diǎn)越重要。但是，這兩個(gè)時(shí)序節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)并不總是適用于任何場(chǎng)景。文獻(xiàn)[62-63]將所提出的時(shí)序指標(biāo)用于選取關(guān)鍵節(jié)點(diǎn)用于阻斷惡意軟件傳播，便發(fā)現(xiàn)時(shí)序介數(shù)中心性與靜態(tài)指標(biāo)的效果不顯著，但通過(guò)選取時(shí)序接近中心性高的節(jié)點(diǎn)則有顯著效果，因?yàn)闀r(shí)序接近中心性高的節(jié)點(diǎn)可以很快到達(dá)大多數(shù)節(jié)點(diǎn)。

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

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

發(fā)現(xiàn)當(dāng)且僅當(dāng)節(jié)點(diǎn)間有唯一時(shí)序路徑時(shí)，平均時(shí)序距離獨(dú)立于路徑的開(kāi)始時(shí)間，也獨(dú)立于觀測(cè)時(shí)間窗口的時(shí)間順序設(shè)置。在此基礎(chǔ)上，結(jié)合靜態(tài)網(wǎng)絡(luò)中的接近中心性公式定義了時(shí)序接近中心性：

該時(shí)序接近中心性與靜態(tài)網(wǎng)絡(luò)的接近中心性類(lèi)似，值越大，則表明節(jié)點(diǎn)越重要。

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

定義動(dòng)態(tài)網(wǎng)絡(luò)中從節(jié)點(diǎn) u0到 節(jié)點(diǎn) vk開(kāi)始于時(shí)間ts的時(shí)序路徑為連邊序列：

該序列滿(mǎn)足：

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

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

3) t0ts。

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

實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，節(jié)點(diǎn)重要性隨時(shí)間變化，捕捉節(jié)點(diǎn)全局重要性的聚合指標(biāo)可能無(wú)用，但所提出的時(shí)序接近中心性有助于識(shí)別整個(gè)網(wǎng)絡(luò)時(shí)間間隔內(nèi)一直很重要的節(jié)點(diǎn)，即節(jié)點(diǎn)在任意時(shí)間的時(shí)序接近中心性值都較大，則可以認(rèn)定該節(jié)點(diǎn)在研究的時(shí)間間隔內(nèi)一直很重要。

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

1) τeat(u,w)=τeat(v,w)，即如果順便經(jīng)過(guò)時(shí)序節(jié)點(diǎn)v，從時(shí)序節(jié)點(diǎn)u 出 發(fā)到達(dá) w的最早時(shí)間不變；

2) τldt(w,u)=τldt(v,u)，即如果順便經(jīng)過(guò)時(shí)序節(jié)點(diǎn)v，到達(dá)時(shí)序節(jié)點(diǎn) w 從u 出發(fā)的最晚時(shí)間不變。

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

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

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

最近，文獻(xiàn)[64]基于明顯路徑流的時(shí)序網(wǎng)絡(luò)模型和節(jié)點(diǎn)重要性依賴(lài)于其鄰居重要性的觀點(diǎn)，提出了一個(gè)時(shí)序信息聚集過(guò)程(TIG-process)以識(shí)別時(shí)序網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。基于時(shí)序信息聚集過(guò)程，作者對(duì)比了最快到達(dá)路徑和最短時(shí)序路徑在節(jié)點(diǎn)重要性識(shí)別中的區(qū)別，并結(jié)合時(shí)序信息聚集深度、不同距離鄰居的重要性以及節(jié)點(diǎn)的初始信息分別給出了依據(jù)兩種最短路徑對(duì)節(jié)點(diǎn)重要性進(jìn)行排序的tig-分?jǐn)?shù)。經(jīng)實(shí)驗(yàn)驗(yàn)證發(fā)現(xiàn)，在利用最快到達(dá)路徑評(píng)價(jià)節(jié)點(diǎn)間距離時(shí)可以獲得更好的識(shí)別性能，且可得到最優(yōu)的信息聚集深度，因?yàn)樽羁斓竭_(dá)路徑可以聚集更多的時(shí)序信息。

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

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

2.1.3 基于K-核分解的識(shí)別方法

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

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

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

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

1) SK：靜態(tài)k-shell 值表征時(shí)序網(wǎng)絡(luò)中的核值；

2) TKD：同時(shí)考慮節(jié)點(diǎn)自身和鄰居的時(shí)序kcore 值的時(shí)序指標(biāo) TK (i)除以節(jié)點(diǎn)在靜態(tài)網(wǎng)絡(luò)中的度k(i)

以上4 個(gè)指標(biāo)( TK ,SK,TKD,ASK)，均滿(mǎn)足節(jié)點(diǎn)對(duì)應(yīng)的指標(biāo)值越大越重要的規(guī)律。

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

2.1.4 基于特征向量的識(shí)別方法

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

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

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

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

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

文獻(xiàn)[45]在文獻(xiàn)[44]的基礎(chǔ)上提出了改進(jìn)，認(rèn)為時(shí)序網(wǎng)絡(luò)建模中層間關(guān)系的參數(shù)表示忽略了不同節(jié)點(diǎn)層間連接關(guān)系的差異性。受文獻(xiàn)[29]對(duì)時(shí)序相關(guān)系數(shù)以及文獻(xiàn)[32]對(duì)時(shí)序網(wǎng)絡(luò)中鄰居拓?fù)渲丿B系數(shù)研究的啟發(fā)，文中將節(jié)點(diǎn)的層間連接關(guān)系用鄰居拓?fù)渲丿B系數(shù)表示，提出了基于節(jié)點(diǎn)層間相似性的超鄰接矩陣時(shí)序網(wǎng)絡(luò)構(gòu)建方法。利用特征向量中心性指標(biāo)，獲取節(jié)點(diǎn)在各個(gè)時(shí)間層上的重要性排序，從而研究節(jié)點(diǎn)重要性隨時(shí)間變化的軌跡。實(shí)驗(yàn)證明，改進(jìn)后的模型獲得的結(jié)果優(yōu)于文獻(xiàn)[44]的結(jié)果。

基于特征向量的識(shí)別方法與前三種基于拓?fù)浣Y(jié)構(gòu)的識(shí)別方法不同，其獲得的往往不是全局的節(jié)點(diǎn)重要性排序，而多用于獲得對(duì)應(yīng)時(shí)間快照上的節(jié)點(diǎn)重要性排序以及不同時(shí)間快照上的重要性排序，因此結(jié)果相對(duì)而言更微觀且更真實(shí)，但難以實(shí)現(xiàn)全局上節(jié)點(diǎn)重要性的判斷。

2.2 基于動(dòng)力學(xué)的識(shí)別方法

除了網(wǎng)絡(luò)結(jié)構(gòu)之外，節(jié)點(diǎn)在網(wǎng)絡(luò)動(dòng)力學(xué)行為中的影響力也常常被用來(lái)作為節(jié)點(diǎn)重要性的評(píng)判標(biāo)準(zhǔn)。目前，基于網(wǎng)絡(luò)動(dòng)力學(xué)的識(shí)別方法可以粗略的分為基于隨機(jī)游走和傳播動(dòng)力學(xué)兩類(lèi)。

2.2.1 基于隨機(jī)游走的識(shí)別方法

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

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

文獻(xiàn)[79]建立時(shí)間窗圖模型，通過(guò)類(lèi)似的原理將Katz 中心性拓展到時(shí)序網(wǎng)絡(luò)。以 A(t)表示第t個(gè)時(shí)間窗對(duì)應(yīng)的鄰接矩陣，那么任意長(zhǎng)度 k的時(shí)序游走路徑的計(jì)數(shù)按如下形式獲得：

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

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

文獻(xiàn)[80]則基于文獻(xiàn)[79]提出的時(shí)序網(wǎng)絡(luò)中的溝通性矩陣 Q，對(duì)文獻(xiàn)[81]和文獻(xiàn)[82]提出的基于隨機(jī)游走的溝通介數(shù)(communicability betweenness)和分解介數(shù)(resolvent betweenness)進(jìn)行了相關(guān)拓展，并提出了基于隨機(jī)游走的時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn) v的介數(shù)。具體計(jì)算如下：

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

首先，定義時(shí)序網(wǎng)絡(luò) G中時(shí)間相關(guān)的隨機(jī)游走，即時(shí)序隨機(jī)游走為如下邊序列：

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

其次，對(duì)節(jié)點(diǎn)u 在靜態(tài)網(wǎng)絡(luò)中的PageRank 得分π(u)進(jìn)行調(diào)整(如下公式)，使得計(jì)算只考慮時(shí)序游走而不是所有的游走。

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

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

結(jié)合上述兩個(gè)公式，節(jié)點(diǎn) u在 時(shí)間t的時(shí)序PageRank 分?jǐn)?shù)的計(jì)算公式為：

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

該個(gè)性化的時(shí)序PageRank 值越大，表明節(jié)點(diǎn)越重要。在此基礎(chǔ)上，文獻(xiàn)[24]提出了一個(gè)計(jì)算該時(shí)序PageRank 值的算法，并證明算法可以收斂，且當(dāng)邊分布是靜態(tài)時(shí)可以收斂到靜態(tài)網(wǎng)絡(luò)的PageRank 值。真實(shí)數(shù)據(jù)上的結(jié)果也驗(yàn)證了該方法的合理性，并表明其是一個(gè)靈活的測(cè)度，可以根據(jù)網(wǎng)絡(luò)隨時(shí)間的變化而調(diào)整。

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

1) 定義每個(gè)快照中節(jié)點(diǎn)對(duì)i 和j 之間的轉(zhuǎn)移概率(以第t個(gè)快照為例， ωij(t)表 示該快照中節(jié)點(diǎn)i與節(jié)點(diǎn) j間的接觸次數(shù)，則第t個(gè)快照對(duì)應(yīng)的鄰接矩陣為 ω(t )=(ωij(t)))

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

當(dāng) si( t)=0 時(shí)表示節(jié)點(diǎn)i是 孤立點(diǎn)，當(dāng) si( t)1表示節(jié)點(diǎn)i是非孤立點(diǎn)；

2) 定義時(shí)序網(wǎng)絡(luò)一個(gè)周期的轉(zhuǎn)移矩陣為

式中， r表示一個(gè)周期內(nèi)的所有快照的數(shù)目，B(t)=(Bij(t))是 第t個(gè) 快照的轉(zhuǎn)移矩陣。定義 Ptp的左側(cè)主特征向量(對(duì)應(yīng)的特征值為1)為

文獻(xiàn)[39]從時(shí)間窗圖模型出發(fā)，規(guī)定每個(gè)時(shí)間窗為連邊不可變的有向圖快照Gt，定義其對(duì)應(yīng)的鄰接矩陣為 A(t)。基于“如果動(dòng)態(tài)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)經(jīng)過(guò)一段時(shí)間對(duì)另一個(gè)節(jié)點(diǎn)產(chǎn)生影響，那么在不同的時(shí)間存在一條可以通過(guò)中介連接起點(diǎn)和終點(diǎn)的路徑”的思想，提出了新的節(jié)點(diǎn)中心性測(cè)度。考慮未來(lái)快照網(wǎng)絡(luò)Gtk+1的狀態(tài)除了依賴(lài)于當(dāng)前快照網(wǎng)絡(luò)Gtk的狀態(tài)，是否還依賴(lài)于之前的狀態(tài)，將時(shí)序網(wǎng)絡(luò)中的信息傳播建模為無(wú)記憶的動(dòng)力學(xué)過(guò)程和有記憶的動(dòng)力學(xué)過(guò)程，分別如下。

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

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

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

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

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

1) 定義動(dòng)態(tài)通路為在一個(gè)非遞減的離散時(shí)間序列 t1? t2?···?tr?···?tk(t1,tk∈T)上的頂點(diǎn)與連邊的序列 vie1v1e2···vmervm+1···ewvj構(gòu) 成節(jié)點(diǎn)i到節(jié)點(diǎn)j 的長(zhǎng)度為 w的動(dòng)態(tài)通路，當(dāng)且僅當(dāng)?shù)趓 個(gè)快照的鄰接矩陣滿(mǎn)足

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

3) 考慮所有動(dòng)態(tài)通路的組合，按照“長(zhǎng)步長(zhǎng)通路賦予較小權(quán)重，短步長(zhǎng)通路賦予較大權(quán)重”的原則，計(jì)算動(dòng)態(tài)時(shí)序網(wǎng)絡(luò)的動(dòng)態(tài)中心性指標(biāo)矩陣Dt，有

展開(kāi)式中，在節(jié)點(diǎn)的動(dòng)態(tài)通路加權(quán)公式中加上n×n維 矩陣I，表示節(jié)點(diǎn)把消息傳遞給自己。同時(shí)，可以發(fā)現(xiàn)在同一拓?fù)淇煺諆?nèi)長(zhǎng)度為 w的通路按照 βw/w!的方式衰減，利用不同拓?fù)淇煺胀瓿傻拈L(zhǎng)度為 w的通路按照 βw/(l1!l2!···lr!)的方式衰減，其中w=l1+l2+···+lr表示跨越了 r個(gè)拓?fù)淇煺胀瓿闪碎L(zhǎng)度為 w的通路，并在第 r 個(gè)快照中完成了 w中的lr步。

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

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

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

2.2.2 基于傳播動(dòng)力學(xué)的識(shí)別方法

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

文獻(xiàn)[97]從網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)涮卣骱蛣?dòng)力學(xué)屬性出發(fā)，提出了可以直接用于靜態(tài)網(wǎng)絡(luò)中有影響力傳播者定位的對(duì)動(dòng)力學(xué)敏感的中心性(dynamicssensitive centrality)指標(biāo)，并通過(guò)在4 個(gè)真實(shí)網(wǎng)絡(luò)中進(jìn)行SIR 傳播模型和SI 傳播模型的擬合，發(fā)現(xiàn)該指標(biāo)優(yōu)于度中心性、k-shell 指標(biāo)以及特征向量中心性。具體方法如下：

對(duì) t>1，有

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

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

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

由此可知，以節(jié)點(diǎn)i為初始感染節(jié)點(diǎn)， x(t)實(shí)際為 β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é)點(diǎn)的傳播影響可寫(xiě)為：

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

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

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

用數(shù)學(xué)歸納法求解可得：

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

因?yàn)?A( t)T=A(t)， [H(t)]T=H?(t)，所以有

式中， V= (1,1,···,1)T； S(t)即為本文所提出測(cè)量節(jié)點(diǎn)在時(shí)序網(wǎng)絡(luò)中傳播影響的指標(biāo)。該指標(biāo)值越大，說(shuō)明節(jié)點(diǎn)的傳播影響越大，則節(jié)點(diǎn)越重要。

基于傳播動(dòng)力學(xué)的關(guān)鍵節(jié)點(diǎn)識(shí)別方法并不常見(jiàn)，但其往往作為測(cè)量標(biāo)準(zhǔn)，評(píng)價(jià)其他識(shí)別方法的好壞。后面在時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別方法的評(píng)價(jià)指標(biāo)中將進(jìn)一步說(shuō)明。

2.3 基于機(jī)器學(xué)習(xí)的識(shí)別方法

目前，機(jī)器學(xué)習(xí)結(jié)合復(fù)雜網(wǎng)絡(luò)的研究逐漸增多，基于網(wǎng)絡(luò)的機(jī)器學(xué)習(xí)算法的應(yīng)用越來(lái)越廣泛[99]，包括理論研究中網(wǎng)絡(luò)的社區(qū)檢測(cè)[100]、動(dòng)態(tài)網(wǎng)絡(luò)中的鏈路預(yù)測(cè)[101]或網(wǎng)絡(luò)中的動(dòng)態(tài)鏈路預(yù)測(cè)[102]，以及現(xiàn)實(shí)社會(huì)中水電氣等供應(yīng)網(wǎng)絡(luò)中的可達(dá)性[103]，城市運(yùn)輸網(wǎng)絡(luò)中的交通預(yù)測(cè)[104]等。

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

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

式中， nD表示訓(xùn)練數(shù)據(jù)中節(jié)點(diǎn)的 Dk=1的數(shù)目；nL表示所達(dá)葉節(jié)點(diǎn)中訓(xùn)練數(shù)據(jù)的數(shù)目， m取P(Dk=1)是 訓(xùn)練數(shù)據(jù)中 Dk=1的先驗(yàn)概率。然后根據(jù)說(shuō)服概率提出表征個(gè)體說(shuō)服能力的指標(biāo)值如下：

式中， pij是 所求的實(shí)體i說(shuō) 服實(shí)體 j 的概率； cj表示實(shí)體i 服能力，由說(shuō)服概率和其他所有實(shí)體vj∈V,的說(shuō)服能力共同決定。通過(guò)冪迭代算法求解表征實(shí)體說(shuō)服能力的指標(biāo)值，值越大，則對(duì)應(yīng)的實(shí)體越重要。

文獻(xiàn)[55]基于用戶(hù)-對(duì)象的二分網(wǎng)絡(luò)，將數(shù)據(jù)劃分為過(guò)去的時(shí)間窗和未來(lái)的時(shí)間窗，以識(shí)別并預(yù)測(cè)電子商務(wù)平臺(tái)或者社交媒體平臺(tái)中的關(guān)鍵節(jié)點(diǎn)，即未來(lái)流行或重要的對(duì)象(商品、對(duì)象或推文等)。具體地，考慮復(fù)雜網(wǎng)絡(luò)中驅(qū)動(dòng)節(jié)點(diǎn)流行性的3 個(gè)影響因子(偏好連接、最近的流行度以及衰變)，提出表征節(jié)點(diǎn)在未來(lái)時(shí)間流行度或重要性的預(yù)測(cè)分?jǐn)?shù)模型如下：

式中， Tp表 示過(guò)去的時(shí)間窗； s0( t,Tp)表示基于過(guò)去時(shí)間窗 Tp在 時(shí)間t對(duì) 象的預(yù)測(cè)分?jǐn)?shù)；λ是調(diào)整新穎性和總流行性的參數(shù)；Tuo表示用戶(hù)u 消 費(fèi)對(duì)象o 的時(shí)間；γ為自由參數(shù)。然后，基于過(guò)去時(shí)間窗中的數(shù)據(jù)用梯度下降算法求解出模型中的參數(shù)，迭代過(guò)程如下：

式中， ?e表示誤差。最后通過(guò)預(yù)測(cè)分?jǐn)?shù)模型進(jìn)行未來(lái)時(shí)間窗中對(duì)象流行度或重要度的預(yù)測(cè)，并根據(jù)準(zhǔn)確率、新穎性、時(shí)序新穎性以及AUC 等值評(píng)價(jià)模型的好壞。該應(yīng)用雖然未涉及具體的時(shí)序信息，但在一定程度上引入了時(shí)序概念，為后續(xù)開(kāi)展將機(jī)器學(xué)習(xí)方法用于時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別的研究提供了參考。

2.4 其他識(shí)別方法

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

文獻(xiàn)[107]通過(guò)對(duì)辦公大樓中面對(duì)面接觸的時(shí)序數(shù)據(jù)的研究，發(fā)現(xiàn)一種無(wú)需完全了解時(shí)序網(wǎng)絡(luò)，便可以根據(jù)部門(mén)的組織結(jié)構(gòu)，獲得關(guān)鍵節(jié)點(diǎn)的方法。具體地，根據(jù)各個(gè)部門(mén)中節(jié)點(diǎn)在部門(mén)內(nèi)的連邊與在部門(mén)間的連邊數(shù)量，將節(jié)點(diǎn)分為居住者(有更多的部門(mén)內(nèi)連邊)、閑逛者(有更多的部門(mén)間連邊)和連接者(部門(mén)內(nèi)連邊和部門(mén)間連邊各占一半)，其中連接者被定義為重要節(jié)點(diǎn)，因?yàn)樗麄兊慕閿?shù)中心性更大，且在增強(qiáng)部門(mén)間的溝通方面起重要作用。

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

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

由于快照t中 節(jié)點(diǎn) vi的影響不僅由其鄰居數(shù)決定，還受其鄰居影響的影響。基于此，定義為快照t中 節(jié)點(diǎn) vi的影響，則有

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

同時(shí)由于當(dāng) t=1時(shí)，各節(jié)點(diǎn)的影響考慮了相鄰節(jié)點(diǎn)在整個(gè)時(shí)間段內(nèi)的累積效應(yīng)，所以作者利用t=1處各節(jié)點(diǎn)的影響衡量節(jié)點(diǎn)在計(jì)算機(jī)病毒時(shí)序網(wǎng)絡(luò)傳播過(guò)程中的重要性。

3 時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別方法的評(píng)價(jià)指標(biāo)

評(píng)價(jià)時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別方法的效果有多種不同的角度，可以依據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)的結(jié)構(gòu)和功能中的重要性，同時(shí)也可以與其他已有指標(biāo)進(jìn)行對(duì)比。一般而言，網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性排序主要從網(wǎng)絡(luò)性能的變化、傳播效果的好壞、指標(biāo)間的相關(guān)性三個(gè)角度驗(yàn)證。

3.1 基于網(wǎng)絡(luò)性能變化的評(píng)價(jià)方法

網(wǎng)絡(luò)性能是考察節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響力的評(píng)價(jià)指標(biāo)。節(jié)點(diǎn)刪除法是常用的利用網(wǎng)絡(luò)性能變化評(píng)價(jià)節(jié)點(diǎn)重要性的方法，其有累積刪除和依次刪除兩種思路[108]。假設(shè)網(wǎng)絡(luò)時(shí)序性能為 E(G )，首先按節(jié)點(diǎn)識(shí)別方法對(duì)節(jié)點(diǎn)重要性排序，再計(jì)算表征時(shí)序網(wǎng)絡(luò)性能變化的評(píng)價(jià)指標(biāo)。具體有如下思路：

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

若兩者差值越大，則說(shuō)明節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)性能的影響越大，同時(shí)也說(shuō)明節(jié)點(diǎn)越重要，識(shí)別方法性能越好。

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

若刪除的節(jié)點(diǎn)比例越少，則說(shuō)明節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)性能的影響越大，同時(shí)也說(shuō)明識(shí)別出的節(jié)點(diǎn)越重要，識(shí)別方法性能越好。

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

該結(jié)果衡量單個(gè)節(jié)點(diǎn)依次移除后網(wǎng)絡(luò)性能的變化。若值越大，說(shuō)明節(jié)點(diǎn)越重要，同時(shí)也說(shuō)明識(shí)別方法有好的性能。

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

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

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

式中， dt( u,v)表 示開(kāi)始時(shí)間為t的 節(jié)點(diǎn)對(duì) (u,v)間的時(shí)序距離，時(shí)序距離通過(guò)時(shí)序最短路徑計(jì)算。開(kāi)始時(shí)間t 不同時(shí)，同一節(jié)點(diǎn)對(duì) (u,v)間的時(shí)序距離也不一定相同。此外，當(dāng)節(jié)點(diǎn)對(duì) (u,v)間不存在時(shí)序路徑時(shí)， dt( u,v)=∞。

2) 網(wǎng)絡(luò)時(shí)序最大連通分量：衡量時(shí)序網(wǎng)絡(luò)可達(dá)性的指標(biāo)，是時(shí)序網(wǎng)絡(luò)最大連通圖中的節(jié)點(diǎn)數(shù)占整個(gè)網(wǎng)絡(luò)所有節(jié)點(diǎn)的比例[38]。該時(shí)序性能指標(biāo)來(lái)源于靜態(tài)網(wǎng)絡(luò)中的最大連通分量，即最大連通分量中節(jié)點(diǎn)的比例，定義如下：

① 基于時(shí)序網(wǎng)絡(luò)模型，選取初始時(shí)間的節(jié)點(diǎn)u，依次遍歷各個(gè)時(shí)間點(diǎn)直至結(jié)束，統(tǒng)計(jì)可到達(dá)的節(jié)點(diǎn)數(shù)目為| ?u|[111]，則有

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

3.2 基于傳播模型的評(píng)價(jià)方法

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

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

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

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

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

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

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

文獻(xiàn)[49]提出了一種網(wǎng)絡(luò)影響的基準(zhǔn)方法，用TKO 分?jǐn)?shù)表示。該方法結(jié)合了超級(jí)傳播者和免疫過(guò)程的影響，同時(shí)還包括感染的時(shí)間，能夠克服不同的測(cè)度針對(duì)具體的網(wǎng)絡(luò)結(jié)構(gòu)有效以及傳統(tǒng)方法的不足，從而更準(zhǔn)確地測(cè)量節(jié)點(diǎn)對(duì)傳播的影響。具體過(guò)程如下：

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

2) 對(duì)于對(duì)應(yīng)時(shí)序網(wǎng)絡(luò)中的每個(gè)時(shí)間層的節(jié)點(diǎn)，實(shí)施移除操作分析。即移除某節(jié)點(diǎn)，運(yùn)行相同的動(dòng)力學(xué)模型，測(cè)量疾病量級(jí)的變化，獲得該節(jié)點(diǎn)的基于初始傳播源的邊際感染分?jǐn)?shù)。

3) 使用每個(gè)節(jié)點(diǎn)作為初始感染源，執(zhí)行過(guò)程1)和2)，獲得每個(gè)時(shí)間層每個(gè)節(jié)點(diǎn)基于不同的初始傳播源的邊際感染分?jǐn)?shù)。取平均值作為所求的TKO 分?jǐn)?shù)。

TKO 分?jǐn)?shù)是一個(gè)全方面的經(jīng)驗(yàn)度量，可以捕獲到節(jié)點(diǎn)在每個(gè)時(shí)期影響疾病傳播的潛力，常用于評(píng)估其他影響測(cè)量方法的準(zhǔn)確性，是一種有效的基準(zhǔn)測(cè)量方法。

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

3.3 基于相關(guān)性的評(píng)價(jià)方法

時(shí)序網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別方法主要實(shí)現(xiàn)對(duì)節(jié)點(diǎn)重要性的排序，預(yù)測(cè)時(shí)序網(wǎng)絡(luò)中全局最重要的節(jié)點(diǎn)或者特定時(shí)間層的重要節(jié)點(diǎn)。若設(shè)定某一基準(zhǔn)識(shí)別方法或已知節(jié)點(diǎn)真實(shí)的重要性排序，則可基于相關(guān)性評(píng)價(jià)所提出識(shí)別方法的預(yù)測(cè)性能。常用的相關(guān)性評(píng)價(jià)指標(biāo)有Kendall’s τ 相關(guān)系數(shù)[113]以及Spearman相關(guān)系數(shù)[114]，兩者的取值范圍均為[?1, 1]，值越大，相關(guān)性則越強(qiáng)，即說(shuō)明節(jié)點(diǎn)重要性的排序方法更優(yōu)。

文獻(xiàn)[97]在評(píng)估所提出的時(shí)序?qū)?dòng)力學(xué)敏感的中心性這一關(guān)鍵節(jié)點(diǎn)識(shí)別方法的性能時(shí)，在4 個(gè)時(shí)序網(wǎng)絡(luò)中擬合SIR 傳播模型，以一段時(shí)間后感染節(jié)點(diǎn)的數(shù)目衡量節(jié)點(diǎn)的傳播影響，選擇隨機(jī)選擇初始感染節(jié)點(diǎn)的結(jié)果為基準(zhǔn)，同時(shí)獲得根據(jù)靜態(tài)度/介數(shù)/接近中心性、文獻(xiàn)[47]提出的時(shí)序度/介數(shù)/接近中心性、時(shí)序?qū)?dòng)力學(xué)敏感的中心性這七個(gè)指標(biāo)選擇初始感染節(jié)點(diǎn)的傳播影響；然后分別計(jì)算按照七個(gè)指標(biāo)選取初始感染節(jié)點(diǎn)的傳播影響與隨機(jī)選擇初始感染節(jié)點(diǎn)的傳播影響的Kendall’s τ(肯德?tīng)栂禂?shù))，發(fā)現(xiàn)根據(jù)時(shí)序?qū)?dòng)力學(xué)敏感的中心性選取初始感染節(jié)點(diǎn)的傳播影響的相關(guān)系數(shù)最大，從而得知所提出方法有更高的精度。

文獻(xiàn)[45]在提出時(shí)序網(wǎng)絡(luò)中的各時(shí)間層網(wǎng)絡(luò)上節(jié)點(diǎn)的特征向量中心性(SSAM)的方法后，基于兩個(gè)實(shí)證網(wǎng)絡(luò)數(shù)據(jù)，用節(jié)點(diǎn)刪除法得到節(jié)點(diǎn)時(shí)序全局效率差值并排序，然后利用Kendall’s τ(肯德?tīng)栂禂?shù))計(jì)算特征向量中心性與時(shí)序網(wǎng)絡(luò)效率差值的相關(guān)性；同時(shí)按照文獻(xiàn)[44]提出的SAM 方法選取不同的參數(shù)以相同的方法計(jì)算相應(yīng)的Kendall’s τ 系數(shù)。對(duì)比可知，SSAM 方法得到的Kendall’s τ 系數(shù)結(jié)果大部分比SAM 方法的高，說(shuō)明其得到節(jié)點(diǎn)重要性排序更為準(zhǔn)確。

此外，在利于過(guò)去的節(jié)點(diǎn)重要性排序結(jié)果表征未來(lái)的節(jié)點(diǎn)重要性排序時(shí)，常見(jiàn)的有將時(shí)間t的重要節(jié)點(diǎn)作為下一時(shí)間 t+1的預(yù)測(cè)[47]，或劃分訓(xùn)練集和測(cè)試集將訓(xùn)練集中的重要節(jié)點(diǎn)作為測(cè)試集的預(yù)測(cè)[55, 105]，一般在已知真實(shí)的節(jié)點(diǎn)重要性排序時(shí)可計(jì)算其與預(yù)測(cè)的節(jié)點(diǎn)重要性排序之間的相關(guān)系數(shù)，從而評(píng)價(jià)識(shí)別方法的好壞。在此情況下，準(zhǔn)確率[106]也是常見(jiàn)的評(píng)價(jià)指標(biāo)。其表示預(yù)測(cè)的前 K個(gè)重要節(jié)點(diǎn)在真實(shí)排序中的數(shù)目占比。計(jì)算如下：

式中， PK和 RK為選取預(yù)測(cè)排序和真實(shí)排序的前 K點(diǎn)序列。準(zhǔn)確率越高，說(shuō)明節(jié)點(diǎn)識(shí)別方法的性能越好。

4 結(jié) 束 語(yǔ)

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

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

2) 時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別方法的內(nèi)在關(guān)系。

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

表1 時(shí)序網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)識(shí)別方法

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

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

本文研究還得到S-Tech 學(xué)術(shù)支持計(jì)劃?互聯(lián)網(wǎng)傳播學(xué)項(xiàng)目的資助，在此表示感謝。