洪成　蔣沅　嚴(yán)玉為　余榮斌　楊松青

摘要： 為識別時(shí)序網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，提出基于層間鄰域信息熵的時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估方法。受明顯路徑流網(wǎng)絡(luò)模型的啟發(fā)，該方法通過引入?yún)?shù)ω，融合節(jié)點(diǎn)在相鄰時(shí)間快照的層間鄰域拓?fù)湫畔?，使用信息熵來刻畫網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性，并且兼顧了相鄰時(shí)間快照的全局拓?fù)湫畔?。通過使用SIR傳播模型、Kendall相關(guān)系數(shù)、以及Top-k指標(biāo)來驗(yàn)證該方法的有效性與適用性，在6個(gè)真實(shí)數(shù)據(jù)集上與其他6種評估方法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，提出的方法能夠更為有效的識別出時(shí)序網(wǎng)絡(luò)中的重要節(jié)點(diǎn)，同時(shí)對重要性排名靠前的節(jié)點(diǎn)的識別更為準(zhǔn)確；可根據(jù)時(shí)序網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)調(diào)整ω從而提升該方法的評估效果；該方法的時(shí)間復(fù)雜度僅為O（mn），適用于大型時(shí)序網(wǎng)絡(luò)。

關(guān)鍵詞： 時(shí)序網(wǎng)絡(luò)；層間鄰域；節(jié)點(diǎn)重要性；信息熵

中圖分類號： TP39;N94????? 文獻(xiàn)標(biāo)識碼： A

A Method of Evaluating Importance of Nodes in Temporal Networks Based on Inter-layer Neighborhood Information Entropy

HONG Cheng， JIANG Yuan， YAN Yuwei， YU Rongbin， YANG Songqing

（Institute of Information Engineering， Nanchang Hangkong University， Nanchang 330063， China）

Abstract：In order to identify important nodes in temporal networks， a node importance evaluation method is proposed in based on inter-layer neighborhood information entropy. Inspired by the directed flows model of temporal networks， the method introduces the parameter ω to fuse the inter-layer neighborhood topology information of node at adjacent snapshots， uses information entropy to describe the complexity of network structure， and also takes into account the global topological information. The effectiveness and applicability of the method is proved by using the SIR propagation model， Kendall correlation coefficient， Top-k metrics， and the proposed method is compared with six evaluation methods on six real datasets. The experimental results demonstrate that the method can more effectively identify the important nodes in the temporal network. Meanwhile， the identification of the nodes of with high importance is more accurate. In addition， the parameter ω can be adjusted to improve the evaluation effect of this method according to the topology of the temporal network. Last but not least， the time complexity of this method is O（mn）， which is suitable for large-scale temporal networks.

Keywords： temporal network; inter-layer neighborhood; node importance; information entropy

0 引言

網(wǎng)絡(luò)科學(xué)作為一門交叉學(xué)科，對許多領(lǐng)域的發(fā)展起著促進(jìn)作用，如物理、生物、金融，以及社交等 [13]。節(jié)點(diǎn)重要度識別作為復(fù)雜網(wǎng)絡(luò)研究的核心課題之一，有著廣泛的應(yīng)用前景，如市場營銷，流行病控制等[4]。最近關(guān)于靜態(tài)網(wǎng)絡(luò)重要節(jié)點(diǎn)識別的研究取得了一定的進(jìn)展[5]。然而，固定狀態(tài)的連邊與節(jié)點(diǎn)并不能表示動(dòng)態(tài)復(fù)雜系統(tǒng)，而時(shí)序網(wǎng)絡(luò)包含時(shí)間維度信息，其拓?fù)浣Y(jié)構(gòu)隨著時(shí)間發(fā)生變化，能夠更好地表征動(dòng)態(tài)復(fù)雜系統(tǒng)[6]。因此，時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)重要性的評估方法具有重要的研究意義。

時(shí)序網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識別相對靜態(tài)網(wǎng)絡(luò)更具有挑戰(zhàn)，因?yàn)槠渫負(fù)浣Y(jié)構(gòu)隨著時(shí)間變化，每個(gè)節(jié)點(diǎn)的重要性也隨時(shí)間而變化。在靜態(tài)網(wǎng)絡(luò)中，度中心性[7]是識別重要節(jié)點(diǎn)的一種直觀方法，Wang等[8]將之延伸至?xí)r序網(wǎng)絡(luò)，考慮各個(gè)網(wǎng)絡(luò)快照中節(jié)點(diǎn)的度中心的變化情況，提出度值偏差中心性對節(jié)點(diǎn)進(jìn)行排序，該方法計(jì)算復(fù)雜度低，但無法識別度值在快照中變化較小的重要節(jié)點(diǎn)。由于加入了時(shí)間維度，Kim與Anderson在文獻(xiàn)[9]中創(chuàng)建了路徑流時(shí)序網(wǎng)絡(luò)模型，定義了時(shí)序網(wǎng)絡(luò)的最短路徑，基于最短路徑提出接近中心性和介數(shù)中心性，用以識別時(shí)序網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。此類方法計(jì)算時(shí)間復(fù)雜度高，對大型時(shí)序網(wǎng)絡(luò)不適用。Taylor等[10]將靜態(tài)網(wǎng)絡(luò)的特征向量[11]識別推廣到時(shí)序網(wǎng)絡(luò)，通過結(jié)合多層網(wǎng)絡(luò)的思想構(gòu)建超中心矩陣，超中心矩陣的主特征向量對應(yīng)各時(shí)間層節(jié)點(diǎn)的重要程度。胡剛等[12]在此基礎(chǔ)上考慮時(shí)序網(wǎng)絡(luò)跨層間的耦合系數(shù)，對識別層內(nèi)重要節(jié)點(diǎn)都具有一定的提升。Jiang等[13]提出新的耦合系數(shù)計(jì)算方式并引入衰減因子來刻畫層間耦合關(guān)系的變化?；谔卣飨蛄孔R別的方法能夠展現(xiàn)時(shí)間層內(nèi)微觀重要性排序，而局限是不能對時(shí)序網(wǎng)絡(luò)整體的重要節(jié)點(diǎn)進(jìn)行識別。Qu等[14]基于節(jié)點(diǎn)重要性依賴于其鄰居節(jié)點(diǎn)重要性的觀點(diǎn)，提出了時(shí)序信息收集過程（TIC-process），對時(shí)序網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)進(jìn)行識別，該方法考慮了信息收集深度、距離矩陣、初始信息以及權(quán)重函數(shù)4個(gè)指標(biāo)，發(fā)現(xiàn)相對于時(shí)序最短路徑距離矩陣，最快到達(dá)路徑作為距離矩陣性能更好。該方法將時(shí)序節(jié)點(diǎn)重要度識別轉(zhuǎn)換為一個(gè)更一般的過程，能夠獲取最優(yōu)的指標(biāo)組合方式以識別重要節(jié)點(diǎn)，但對于不同的網(wǎng)絡(luò)，最優(yōu)的組合亦不一致。

熵可用于量化系統(tǒng)內(nèi)在混亂程度，被廣泛運(yùn)用于復(fù)雜網(wǎng)絡(luò)研究[15]。也有學(xué)者將熵從靜態(tài)網(wǎng)絡(luò)擴(kuò)展到時(shí)序網(wǎng)絡(luò)，如Luo等[16]考慮了不同節(jié)點(diǎn)之間的時(shí)空聯(lián)系，提出了結(jié)構(gòu)熵的中心性識別方法以保護(hù)計(jì)算機(jī)免受病毒攻擊，同時(shí)也考慮了病毒傳播的時(shí)間順序。Michalski 等[17]運(yùn)用熵來度量節(jié)點(diǎn)鄰居隨時(shí)間的變化，認(rèn)為節(jié)點(diǎn)鄰居隨時(shí)間變化越大的節(jié)點(diǎn)影響力越大，相較于其他啟發(fā)式算法，此方法時(shí)間復(fù)雜度更低。

受到上述研究工作的啟發(fā)，本文提出基于層間鄰域信息熵的時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估方法（INE）。以明顯路徑流網(wǎng)絡(luò)模型的視角引入?yún)?shù)ω，融合節(jié)點(diǎn)在相鄰快照的層間鄰域拓?fù)湫畔?，使用信息熵來刻畫網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性，最后以全局的視角對不同的層間節(jié)點(diǎn)的鄰域信息熵進(jìn)行賦權(quán)得出各節(jié)點(diǎn)的重要性。通過時(shí)間復(fù)雜度分析得該方法的時(shí)間復(fù)雜度僅為O（mn），適用于大型時(shí)序網(wǎng)絡(luò)。為證實(shí)本文所提出方法的有效性與適用性，本文在6個(gè)真實(shí)數(shù)據(jù)集上采用時(shí)序SIR模型作為評價(jià)模型，將INE與6個(gè)基準(zhǔn)評估方法作比較。利用Kendall相關(guān)系數(shù)與Top-k指標(biāo)證實(shí)了本文所提出方法的優(yōu)越性。最后探討了ω對該方法的影響，發(fā)現(xiàn)可根據(jù)時(shí)序網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)調(diào)整ω以提升INE的評估效果。

1 理論基礎(chǔ)

1.1 時(shí)序網(wǎng)絡(luò)定義

設(shè)GT=（V，ET）為在時(shí)間窗口［1，T］上觀測到的時(shí)序網(wǎng)絡(luò)，T=S/δ，S為總的交互時(shí)間時(shí)長，δ為時(shí)間窗口的大小，V為節(jié)點(diǎn)集，ET為時(shí)序交互事件集。每個(gè)交互et∈ET用四元組 （u，v，t，λ）表示，其中u，v∈V，t為起始時(shí)間，λ為持續(xù)時(shí)間，t+λ為結(jié)束時(shí)間，本文中令λ=0，即只考慮瞬時(shí)交互。對于每個(gè)時(shí)刻t∈［1，T］，用Gt表示t時(shí)間窗口下的圖，At為對應(yīng)的鄰接矩陣，若節(jié)點(diǎn)u與v在t時(shí)刻發(fā)生交互，Atu，v=1，否則Atu，v=0。即時(shí)序網(wǎng)絡(luò)可用離散有序的快照網(wǎng)絡(luò)G1，G2，…，GT表示。

1.2 時(shí)序接近中心性

時(shí)序接近中心性（TC）[9]是基于時(shí)序最短路徑的識別方法，TC越大表示與網(wǎng)絡(luò)其他節(jié)點(diǎn)越接近，節(jié)點(diǎn)越重要，其中Δt，T（v，u）為在時(shí)間間隔［t，T］內(nèi)從v到u的時(shí)序最短距離。

1.3 時(shí)序介數(shù)中心性

時(shí)序介數(shù)中心性（TB）[9]同樣是基于時(shí)序最短路徑的識別方法，表示作為“橋接”節(jié)點(diǎn)對網(wǎng)絡(luò)信息流的控制能力，TB越大表示通過該節(jié)點(diǎn)的時(shí)序最短路徑越多，式（2）中，σt，T（s，d）表示在時(shí)間間隔［t，T］內(nèi)從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的時(shí)序最短路徑數(shù)目，σt，T（s，d，v）為在時(shí)間間隔［t，T］內(nèi)從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的時(shí)序最短路徑中通過節(jié)點(diǎn)v的路徑數(shù)目。

1.4 時(shí)序度值偏差中心性

時(shí)序度值偏差中心性（TDD）[8]認(rèn)為節(jié)點(diǎn)在各個(gè)時(shí)間快照上度值變化越大，該節(jié)點(diǎn)就越重要，其中Dt（v）表示在時(shí)間快照t節(jié)點(diǎn)v的度，D（v）表示在所有時(shí)間快照的平均度。

1.5 時(shí)序k-核中心性

時(shí)序k-核中心性（TK）[18]將k-核引入時(shí)序網(wǎng)絡(luò)，同時(shí)考慮自身與鄰居節(jié)點(diǎn)的k-核值，kts（v）為節(jié)點(diǎn)v在時(shí)間快照t的k-核值，Γv為節(jié)點(diǎn)v的鄰居集。

1.6 時(shí)序動(dòng)力學(xué)敏感中心性

時(shí)序動(dòng)力學(xué)敏感中心性（TDC）[19]考慮了時(shí)序網(wǎng)絡(luò)的動(dòng)態(tài)特性，式（5）中，S為表示所有節(jié)點(diǎn)傳播影響力的向量，A（t）為在時(shí)間快照t的鄰接矩陣，I為單位矩陣，V0T表示元素全為1的列向量，β0和γ分別為感染概率與恢復(fù)概率。

1.7 基于熵的時(shí)序中心性

基于熵的時(shí)序中心性（TEC）[14]將信息論運(yùn)用到時(shí)序網(wǎng)絡(luò)中，并考慮了病毒傳播的時(shí)間特性。式（7）、（8）中Lti是t快照下節(jié)點(diǎn)i的鄰居數(shù)，該方法首先計(jì)算RTi然后歸一化為RTi，然后令 ITi= RTi，通過式（8）計(jì)算出第一個(gè)快照的I1i即為節(jié)點(diǎn)i的中心性大小，其中p為可調(diào)參數(shù)。

2 INE評估方法

2.1 方法構(gòu)造

如圖1時(shí)序網(wǎng)絡(luò)的兩種表示模型，圖1a表示時(shí)間快照模型，圖1b表示明顯路徑流模型，二者是同一時(shí)序網(wǎng)絡(luò)的不同表現(xiàn)形式，時(shí)間快照模型能夠清楚直觀反應(yīng)各個(gè)快照下拓?fù)淝闆r，而明顯路徑流模型表現(xiàn)的是網(wǎng)絡(luò)全局情況以及信息流向。

本文將兩種時(shí)序網(wǎng)絡(luò)模型對應(yīng)起來，圖1b中的虛線框中G1，G2，G3，G4對應(yīng)時(shí)間快照模型中的快照網(wǎng)絡(luò)。如在t∈［0～2］時(shí)段，包含兩個(gè)快照即G1，G2，在t∈［0～1］時(shí)段產(chǎn)生了G1，在t∈［1～2］時(shí)段產(chǎn)生了G2?？梢灾庇^看出，在t=1時(shí)通過節(jié)點(diǎn)的信息流承接了G1與G2的鄰域信息，而在以往的對時(shí)序網(wǎng)絡(luò)的研究里，卻未體現(xiàn)出時(shí)序網(wǎng)絡(luò)這一獨(dú)有的拓?fù)湫再|(zhì)，即以路徑流視角有效利用相鄰快照的層間拓?fù)湫畔?。鑒于此，結(jié)合信息熵將節(jié)點(diǎn)的信息輸出概率定義為

其中，kt（i）為節(jié)點(diǎn)i在時(shí)間快照t下的度值，t∈［1～T-1］，ω是本文引入可調(diào)參數(shù)，取值范圍為0，1，表示節(jié)點(diǎn)下一快照的鄰域拓?fù)湫畔⑴c層間鄰域拓?fù)湫畔⒌恼急?。pti表示信息從t快照流向t+1快照時(shí)通過節(jié)點(diǎn)i的概率，本文用該指標(biāo)表征節(jié)點(diǎn)在相鄰快照間的橋接作用?？紤]到節(jié)點(diǎn)鄰居對節(jié)點(diǎn)的重要性影響，本文引入信息熵刻畫節(jié)點(diǎn)鄰域的拓?fù)浣Y(jié)構(gòu)的復(fù)雜性，將節(jié)點(diǎn)信息熵定義為

其中，Γti表示節(jié)點(diǎn)i在時(shí)間快照t下的鄰居節(jié)點(diǎn)集，Hti的值越大，表示節(jié)點(diǎn)i在t快照與t+1快照間的拓?fù)浣Y(jié)構(gòu)越復(fù)雜，重要性也越高。考慮到時(shí)序網(wǎng)絡(luò)是由一系列時(shí)間快照構(gòu)成，而相鄰快照間的交互次數(shù)越多，說明該相鄰快照影響力越大。故將節(jié)點(diǎn)i的全局重要性定義為

式（11）INE的計(jì)算利用了時(shí)序網(wǎng)絡(luò)中的全局拓?fù)湫畔ⅲ渲蠩t為快照t中網(wǎng)絡(luò)連邊的交互次數(shù)。

2.2 計(jì)算流程及復(fù)雜性分析

本文所提出INE算法具體計(jì)算流程：

步驟1：輸入時(shí)序網(wǎng)絡(luò)G=G1，G2，…，GT，可調(diào)參數(shù)ω，初始化各節(jié)點(diǎn)INEi=0；

步驟2：根據(jù)式（7）計(jì)算信息輸出概率；

步驟3：根據(jù)式（8）計(jì)算節(jié)點(diǎn)信息熵；

步驟4：根據(jù)式（9）賦權(quán)節(jié)點(diǎn)信息熵，并將其累加至對應(yīng)的INEi；

步驟5：重復(fù)步驟2至步驟4，直至遍歷完所有的相鄰時(shí)間快照，輸出INEi。

該算法遍歷了所有的相鄰時(shí)間快照求出層間鄰域信息熵，故整個(gè)算法遍歷2*（m-1）個(gè)時(shí)間快照，m為時(shí)序網(wǎng)絡(luò)總的快照數(shù)，本文中m=T，在計(jì)算節(jié)點(diǎn)信息熵時(shí)，需要考慮鄰居節(jié)點(diǎn)信息，時(shí)間復(fù)雜度為O（n*k-），n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，k-為所有時(shí)間快照中節(jié)點(diǎn)的平均度?？芍疚奶岢龅乃惴◤?fù)雜度為O（2*m-1*n*k-），對一般網(wǎng)絡(luò)可化為O（m*n）。此外，表1列出了其他幾種評估方法的時(shí)間復(fù)雜度，可見本文提出的INE時(shí)間復(fù)雜度較低，適用于大型時(shí)序網(wǎng)絡(luò)。

2.3 有效性分析

為驗(yàn)證本文提出的INE方法的有效性，用對照方法與INE對圖1中所表示的時(shí)序網(wǎng)絡(luò)進(jìn)行重要性排序。該時(shí)序網(wǎng)絡(luò)包含4個(gè)時(shí)間快照與6個(gè)節(jié)點(diǎn)，TDC中β0=0.01，γ=0.1；INE中ω=0.5；TEC中p=0.5；排序結(jié)果如表2所示。

結(jié)合表2與圖1分析可知，INE具有較高分辨率，能夠區(qū)分所有節(jié)點(diǎn)的重要性。INE方法和其他方法排序的主要不同是對節(jié)點(diǎn)v5的排序，不難發(fā)現(xiàn)v5的影響力集中在最后一個(gè)時(shí)間快照G4，而從時(shí)間軸上來看，先前時(shí)段活躍的節(jié)點(diǎn)對后續(xù)節(jié)點(diǎn)影響更大，而INE方法考慮到層間鄰域的拓?fù)湫畔?，能夠?qū)⑦@種時(shí)序特征體現(xiàn)。即在第3個(gè)時(shí)間快照中，v1獲得了鄰居節(jié)點(diǎn)v5在最后一個(gè)時(shí)間快照的重要性，故v1節(jié)點(diǎn)排名第一。從明顯路徑流網(wǎng)絡(luò)模型的視角，節(jié)點(diǎn)層間鄰域的信息還能反應(yīng)節(jié)點(diǎn)的層間的橋接能力，v1在圖1a中t=1，t=2時(shí)層間橋接能力較強(qiáng)，在TB排序結(jié)果中也可以得出。v2與v4在G1與v1存在交互，v1作為鄰居節(jié)點(diǎn)，v1在層間的橋接能力也會(huì)影響鄰居節(jié)點(diǎn)的重要性，v2與v4同獲v1影響力，v2在第2個(gè)時(shí)間快照上影響力較大，v4在第3個(gè)時(shí)間快照上影響力較大，但G2與G3的網(wǎng)絡(luò)規(guī)模相對G3與G4?。ㄟB邊數(shù)為判斷），故INE將節(jié)點(diǎn)v4排第2，v2排第3。值的一提的是基準(zhǔn)方法TEC也運(yùn)用了信息熵理論，但其只在最后一個(gè)時(shí)間快照應(yīng)用信息熵理論，且未考慮到鄰域節(jié)點(diǎn)重要性帶來的影響，計(jì)算出的節(jié)點(diǎn)中心性僅為節(jié)點(diǎn)在初始快照的傳播能力，在此方法下v2的初始傳播能力最強(qiáng)。

綜合上述，本文所提出的INE方法融入層間鄰域拓?fù)湫畔⒑螅軌蚩紤]到信息在網(wǎng)絡(luò)中傳播的時(shí)序特征，同時(shí)也考慮節(jié)點(diǎn)層間的橋接能力以及層間網(wǎng)絡(luò)的規(guī)模，能夠有效區(qū)分時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)的重要度。

3 評估標(biāo)準(zhǔn)

3.1 SIR模型

本文使用基于傳播能力的評估方法，利用SIR傳播模型[20]來評價(jià)時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)的傳播影響力。在SIR傳播模型中有3種狀態(tài)，易感狀態(tài)S，感染狀態(tài) I，恢復(fù)狀態(tài)R。處于I的節(jié)點(diǎn)通過概率β感染其處于S的鄰居節(jié)點(diǎn)，每一個(gè)感染節(jié)點(diǎn)又可以通過概率μ變成恢復(fù)狀態(tài)R，處于R中的節(jié)點(diǎn)不再被感染。不同于靜態(tài)網(wǎng)絡(luò)，在時(shí)序網(wǎng)絡(luò)中，需要考慮到連邊交互先后順序，而每個(gè)節(jié)點(diǎn)可能在多個(gè)快照中產(chǎn)生交互，對每個(gè)節(jié)點(diǎn)，本文分別從其每次交互發(fā)生的時(shí)間進(jìn)行SIR傳播實(shí)驗(yàn)[14]，實(shí)驗(yàn)結(jié)果為1 000次取平均，將處于R中的節(jié)點(diǎn)數(shù)作為傳播影響力標(biāo)準(zhǔn)，為不失一般性，設(shè)μ=1，傳播概率β取0.01～0.20。

3.2 評估指標(biāo)

3.2.1 肯德爾相關(guān)系數(shù)

得到時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)傳播能力σ后，本文使用Kendalls τ（肯德爾相關(guān)系數(shù)）[21]來檢驗(yàn)INE和其余6種基準(zhǔn)方法與傳播能力的排序相關(guān)性。設(shè)x1，y1，x2，y2，…，（xn，yn）為序列X與序列Y一一對應(yīng)的新序列，Kendalls τ定義如式（12），τ∈［-1，1］，若τ=+1表示X與Y排序完全正相關(guān)，τ=0表示X與Y排序不相關(guān)，τ=-1表示X與Y排序完全負(fù)相關(guān)。

3.2.2 Top-k指標(biāo)

本文也使用Top-k[22]來評估7種方法對重要性排名靠前節(jié)點(diǎn)的識別能力。Top-k的評價(jià)指標(biāo)為命中率HR（Hitting Rates），其中C和L分別為評價(jià)方法節(jié)點(diǎn)重要性與SIR傳播模型節(jié)點(diǎn)傳播能力排名前k的節(jié)點(diǎn)集，k取時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的20%。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證INE的排序效果與適用性，本文選用了6個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，分別是Enron數(shù)據(jù)集[23]，Email-Eu-core數(shù)據(jù)集[24]，High school 2011 （2012）數(shù)據(jù)集[25]， Primary school數(shù)據(jù)集[26]，Workplace數(shù)據(jù)集[27]，表3為數(shù)據(jù)集統(tǒng)計(jì)特性，其中V為節(jié)點(diǎn)數(shù)，C為總的交互次數(shù)，E為時(shí)序網(wǎng)絡(luò)總的連邊數(shù)，T為快照數(shù)，δ為時(shí)間間隔。

4.2 實(shí)驗(yàn)分析

4.2.1 評估方法節(jié)點(diǎn)重要性與傳播能力σ的排序相關(guān)性實(shí)驗(yàn)

本節(jié)研究INE和6種基準(zhǔn)方法節(jié)點(diǎn)重要性與SIR節(jié)點(diǎn)傳播能力σ的排序相關(guān)性。采用上述的肯德爾相關(guān)系數(shù)進(jìn)行評估，若識別方法所得出的節(jié)點(diǎn)重要性與σ的τ越接近1，說明該方法越有效。在本小節(jié)的實(shí)驗(yàn)中， TDC中β0=0.01，γ=0.1，TEC中p=0.5，INE方法中的ω取值為0.5。

實(shí)驗(yàn)結(jié)果如圖2所示，可以直觀看出本文所提出的INE評估方法在多個(gè)數(shù)據(jù)集上與SIR模型得到的節(jié)點(diǎn)傳播能力有著顯著的相關(guān)性，而TEC的相關(guān)性最差。圖2中也可以看出，INE方法相關(guān)性曲線的變化趨勢與TC方法相關(guān)性曲線的變化趨勢相似，說明INE方法也考慮到了全局的拓?fù)湫畔?。對比其他幾種基準(zhǔn)評估方法，能夠發(fā)現(xiàn)在High school 2011，Primary school以及Workplace中INE評估方法與SIR模型在β取值的整個(gè)范圍相關(guān)性都是最高的。而在剩余的其他數(shù)據(jù)集中，INE評估方法只有在β較小的時(shí)候與SIR模型的相關(guān)性略低于TK方法，這是由于INE考慮的層間鄰域信息熵，考慮的是兩個(gè)時(shí)間快照的信息，TK方法考慮的只有單層網(wǎng)絡(luò)即單個(gè)時(shí)間快照的k-shell，當(dāng)傳播概率β較小時(shí)，傳播的路徑很短，往往不能感染到其他較遠(yuǎn)時(shí)間快照節(jié)點(diǎn)，感染只在局部發(fā)生，故TK方法在β較小時(shí)相關(guān)性會(huì)略高。但隨著β增大，能夠明顯看出，相比于其他方法，INE評估方法與SIR模型有著更好的相關(guān)性。因此INE方法能夠更為準(zhǔn)確地評估時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)的重要性。

4.2.2 各評估方法Top 20%重要節(jié)點(diǎn)命中率HR實(shí)驗(yàn)

除了研究各方法與SIR排序的相關(guān)關(guān)系外，本文考慮到實(shí)際應(yīng)用中常常關(guān)注的是排名靠前的節(jié)點(diǎn)，故本小節(jié)運(yùn)用Top-k的實(shí)驗(yàn)評價(jià)方法來檢驗(yàn)INE評估方法的有效性，其中INE方法的ω取值為0.5，TDC中β0=0.01，γ=0.1。

圖3為不同β下，7種評估方法的HR，從圖3可以看出，TEC雖然在上一節(jié)的實(shí)驗(yàn)中相關(guān)性都低于其他方法，但在HR實(shí)驗(yàn)中其效果并不是最差的，側(cè)面說明了本實(shí)驗(yàn)的必要性。本文提出的INE方法依然有著較高的命中率，在6個(gè)數(shù)據(jù)集中表現(xiàn)最差也能排到第3，且與另兩種方法之間差距很小，說明該方法能夠識別不同傳播概率β下的重要節(jié)點(diǎn)。對于TDC方法，在圖2c、f中具有不錯(cuò)的表現(xiàn)，但在d、f表現(xiàn)一般，說明TDC識別效果受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響較大，而INE方法的識別效果較為穩(wěn)定。在圖2a、d中可以看出在傳播概率β較小的情況下，TK方法與SIR的相關(guān)性是略高于INE方法與SIR的相關(guān)性的，但對于前20%重要節(jié)點(diǎn)的命中率HR，INE方法卻不低于TK，說明INE不僅能夠有效對所有節(jié)點(diǎn)進(jìn)行排序而且也能準(zhǔn)確識別出較為重要的節(jié)點(diǎn)。

4.2.3 INE方法中ω對評估性能的影響實(shí)驗(yàn)

為探索下一快照的鄰域信息與層間鄰域信息的占比ω對節(jié)點(diǎn)重要性評估的影響，本節(jié)研究INE方法的ω在0.1～0.9取值范圍內(nèi)與SIR模型的相關(guān)性，SIR模型的傳播概率β取值為0.04，0.08，0.12，0.16，0.20。

實(shí)驗(yàn)結(jié)果如圖4所示，從中可以看出對于同一數(shù)據(jù)集，傳播概率β不影響曲線的變化趨勢，其中相關(guān)系數(shù)τ隨ω變化趨勢比較典型的數(shù)據(jù)集為Email-Eu-core，High school 2012以及Primary school，變化趨勢分別為τ隨ω增大上升，τ隨ω先增大再減小，τ隨ω增大變化不明顯。對于Email-Eu-core網(wǎng)絡(luò)，該網(wǎng)絡(luò)的時(shí)間快照較多，且每個(gè)時(shí)間快照中連邊相對其他網(wǎng)絡(luò)密集，時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)之間的可達(dá)性較高，故下一快照鄰域信息占比增加會(huì)使得相關(guān)性提高。對于High school 2012以及Primary school網(wǎng)絡(luò)，影響τ隨ω變化的也是時(shí)序網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，當(dāng)時(shí)間快照中連邊稀疏，節(jié)點(diǎn)之間可達(dá)性低，ω的增加并不能提高與SIR的相關(guān)性，而時(shí)間快照中連邊介于稀疏與密集之間，ω只能對相關(guān)性τ產(chǎn)生很小的影響。值的一提的是，上述疏密性是指時(shí)序網(wǎng)絡(luò)的所有快照，而當(dāng)單個(gè)時(shí)間快照過于稀疏或密集時(shí)，τ隨ω變化的影響較小。由此可以根據(jù)時(shí)序網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)適當(dāng)調(diào)整INE方法中的ω以獲得更佳的識別效果。

5 結(jié)論

本文針對時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的識別問題，提出了INE方法，該方法能夠有效地對時(shí)序網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性進(jìn)行評估和排序。INE方法結(jié)合了節(jié)點(diǎn)層間鄰域的拓?fù)湫畔⑴c各個(gè)時(shí)間快照的全局拓?fù)湫畔ⅲ昧诵畔㈧囟攘烤W(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性。同時(shí)該方法以時(shí)序網(wǎng)絡(luò)明顯路徑流網(wǎng)絡(luò)模型視角將拓?fù)湫畔⒆畲蠡诰?，彌補(bǔ)以往研究中只包含單個(gè)時(shí)間快照拓?fù)湫畔⒌牟蛔?。另外本文使用SIR傳播模型來評估INE方法對節(jié)點(diǎn)重要性排序的結(jié)果。在6個(gè)真實(shí)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明，相較于其他基準(zhǔn)方法，INE能夠更為準(zhǔn)確地評估節(jié)點(diǎn)的重要性，對排名靠前節(jié)點(diǎn)的識別也更為有效，同時(shí)根據(jù)時(shí)序網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)改變INE中的ω還能提高該方法的評估準(zhǔn)確性。此外，INE的時(shí)間復(fù)雜度僅為O（mn）適用于大型時(shí)序網(wǎng)絡(luò)。

參考文獻(xiàn)：

[1]ALBERT R， BARABSI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics， 2002， 74（1）： 47.

[2]BARABSI A L， ALBERT R. Emergence of scaling in random networks[J]. Science， 1999， 286（5439）： 509－512.

[3]NEWMAN M E J. The structure and function of complex networks[J]. SIAMReview， 2003， 45（2）： 167－256.

[4]MORONE F， MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature， 2015， 524（7563）： 65－68.

[5]楊松青，蔣沅，童天馳，等.基于Tsallis熵的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評估方法[J].物理學(xué)報(bào)，2021，70（21）：273－284.

YANG S Q， JIANG Y， TONG T C，et al. A method of evaluating importance of nodes in complex network based on Tsallis entropy[J]. Acta Physica Sinica，2021，70（21）：273－284.

[6]HOLME P， SARAMKI J. Temporal networks[J]. Physics Reports， 2012， 519（3）： 97－125.

[7]BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology， 1972， 2（1）： 113－120.

[8]WANG Z， PEI X， WANG Y， et al. Ranking the key nodes with temporal degree deviation centrality on complex networks[C]//2017 29th Chinese Control And Decision Conference （CCDC）. Piscataway，NJ： IEEE， 2017： 1484－1489.

[9]KIM H， ANDERSON R. Temporal node centrality in complex networks[J]. Physical Review E， 2012， 85（2）： 026107.

[10] TAYLOR D， MYERS S A， CLAUSET A， et al. Eigenvector-based centrality measures for temporal networks[J]. Multiscale Modeling & Simulation， 2015，15（1）： 537－574.

[11] STEPHENSON K， ZELEN M. Rethinking centrality： methods and examples[J]. Social Networks， 1989， 11（1）：1－37.

[12] 胡鋼，許麗鵬，徐翔.基于時(shí)序網(wǎng)絡(luò)層間同構(gòu)率動(dòng)態(tài)演化的重要節(jié)點(diǎn)辨識[J].物理學(xué)報(bào)，2021，70（10）：355－366.

HU G， XU L P，XU X. Identification of important nodes based on dynamic evolution of inter-layer isomorphism rate in temporal networks[J]. Acta Physica Sinica， 2021，70（10）：355－366.

[13] JIANG J L， FANG H， LI S Q， et al. Identifying important nodes for temporal networks based on the ASAM model[J]. Physica A： Statistical Mechanics and Its Applications， 2022， 586： 126455.

[14] QU C， ZHAN X， WANG G， et al.Temporal information gathering process for node ranking in time-varying networks[J]. Chaos： an Interdisciplinary Journal of Nonlinear Science， 2019， 29（3）： 033116.

[15] OMAR Y M， PLAPPER P. A survey of information entropy metrics for complex networks[J]. Entropy， 2020， 22（12）： 1417.

[16] LUO L， TAO L， XU H， et al. An information theory based approach for identifying influential spreaders in temporal networks[C]//International Symposium on Cyberspace Safety and Security. Berlin： Springer， 2017： 477－484.

[17] MICHALSKI R， JANKOWSKI J， PAZURA P. Entropy-based measure for influence maximization in temporal networks[C]//International Conference on Computational Science. Amsterdam： Springer， Cham， 2020： 277－290.

[18] YE Z， ZHAN X， ZHOU Y，et al. Identifying vital nodes on temporal networks： an edge-based k-shell decomposition[C]//2017 36th Chinese Control Conference （CCC）. Piscataway，NJ： IEEE， 2017： 1402－1407.

[19] LIU J G， LIN J H， GUO Q， et al. Locating influential nodes via dynamics-sensitive centrality[J]. Scientific Reports， 2016， 6（1）： 1－8.

[20] PASTOR-SATORRAS R， VESPIGNANI A. Epidemic spreading in scale-free networks[J]. Physical Review Letters， 2001， 86（14）： 3200.

[21] KENDALL M G. A new measure of rank correlation[J]. Biometrika， 1938， 30（1/2）： 81－93.

[22] YU E Y， FU Y， CHEN X， et al. Identifying critical nodes in temporal networks by network embedding[J]. Scientific Reports， 2020， 10（1）： 1－8.

[23] KLIMT B， YANG Y. The enron corpus： a new dataset for email classification research[C]//European Conference on Machine Learning. Berlin， Heidelberg： Springer，? 2004： 217－226.

[24] PARANJAPE A， BENSON A R， LESKOVEC J. Motifs in temporal networks[C]//Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. New York： ACM， 2017： 601－610.

[25] FOURNET J， BARRAT A. Contact patterns among high school students[J]. PloS one， 2014， 9（9）： e107878.

[26] GEMMETTO V， BARRAT A， CATTUTO C. Mitigation of infectious disease at school： targeted class closure vs school closure[J]. BMC Infectious Diseases， 2014， 14（1）： 1－10.

[27] GNOIS M， VESTERGAARD C L， FOURNET J， et al. Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers[J]. Network Science， 2015， 3（3）： 326－347.

（責(zé)任編輯 李 進(jìn)）

收稿日期： 2022－04－28；修回日期：2022－06－06

基金項(xiàng)目： 國家自然科學(xué)基金（61663030， 61663032）；南昌航空大學(xué)研究生創(chuàng)新專項(xiàng)基金（YC2021-043）

第一作者： 洪成（1997－），男，貴州畢節(jié)人，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)動(dòng)力學(xué)。

通信作者： 蔣沅（1982－），男，浙江金華人，博士，副教授，主要研究方向復(fù)雜網(wǎng)絡(luò)的建模與優(yōu)化算法。