基于節(jié)點(diǎn)相似性有偏游走的多層時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估

付艷君， 楊云云,2,3， 趙明明， 張俊麗， 謝 剛,2*

(1.太原理工大學(xué)電氣與動(dòng)力工程學(xué)院， 太原 030024； 2.太原科技大學(xué)山西省高級(jí)控制與裝備智能重點(diǎn)實(shí)驗(yàn)室， 太原 030024； 3.復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)學(xué)院， 上海 200433)

時(shí)序網(wǎng)絡(luò)能夠有效捕獲靜態(tài)網(wǎng)絡(luò)在許多方面都無(wú)法預(yù)測(cè)的時(shí)態(tài)變化[1]，進(jìn)而可以更加準(zhǔn)確地刻畫(huà)網(wǎng)絡(luò)如交通網(wǎng)、電力網(wǎng)及生態(tài)網(wǎng)等實(shí)際復(fù)雜系統(tǒng)的交互關(guān)系；而其中的關(guān)鍵節(jié)點(diǎn)挖掘?qū)τ诜治鼍W(wǎng)絡(luò)系統(tǒng)特征、理解網(wǎng)絡(luò)結(jié)構(gòu)和功能具有顯著的作用[2]。當(dāng)前，用于挖掘關(guān)鍵節(jié)點(diǎn)的算法大都集中于靜態(tài)網(wǎng)絡(luò)上，如基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的度中心性、半局部中心性[3]、緊密度中心性、PageRank[4]和hyperlink-induced topic search(HITS)算法等，基于節(jié)點(diǎn)移除和收縮建立的節(jié)點(diǎn)刪除的最短距離法等。在這些方面，任曉龍等[5]及劉建國(guó)等[6]對(duì)復(fù)雜網(wǎng)絡(luò)中具有代表性的關(guān)鍵節(jié)點(diǎn)挖掘算法做出了系統(tǒng)的闡述、比較和總結(jié)。盡管靜態(tài)網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的研究已經(jīng)取得了一系列可觀的成果，但由于時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)間的連邊會(huì)隨時(shí)間間斷性地出現(xiàn)和消失[7]，僅僅基于靜態(tài)網(wǎng)絡(luò)的研究將忽略時(shí)間變化的信息進(jìn)而影響節(jié)點(diǎn)識(shí)別的準(zhǔn)確性。因此，如何恰當(dāng)?shù)貙?duì)時(shí)序網(wǎng)絡(luò)建模并定義節(jié)點(diǎn)的中心性是一項(xiàng)重大挑戰(zhàn)。近些年來(lái)研究者們對(duì)時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)識(shí)別展開(kāi)了一系列的研究工作。Barrat[8]將時(shí)序網(wǎng)絡(luò)中隨時(shí)間變化的邊聚合成單個(gè)靜態(tài)圖形來(lái)研究，但這樣的建模方式一定程度上忽略了時(shí)序網(wǎng)絡(luò)中的時(shí)間屬性；Kempe等[9]提出了一個(gè)時(shí)序網(wǎng)絡(luò)模型作為靜態(tài)圖，其中每條邊都用交互發(fā)生的時(shí)間進(jìn)行標(biāo)記；Kim等[10]在構(gòu)建時(shí)序網(wǎng)絡(luò)時(shí)規(guī)定每條邊上發(fā)生的事件僅有一次，并將各個(gè)小網(wǎng)絡(luò)用有向邊連接，仍然轉(zhuǎn)化為靜態(tài)圖研究。Tang等[11]提出了基于時(shí)間路徑的時(shí)間度量方法(如，時(shí)序緊密度)以識(shí)別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)。Huang等[12]將節(jié)點(diǎn)的動(dòng)態(tài)索引引入到時(shí)序網(wǎng)絡(luò)中，以衡量節(jié)點(diǎn)的重要性。這些研究成果盡管考慮了時(shí)間窗口中網(wǎng)絡(luò)結(jié)構(gòu)的時(shí)變性，但缺乏不同時(shí)間窗口間的聯(lián)系，仍然未能涵蓋時(shí)間屬性的所有方面。

為完整揭示時(shí)序網(wǎng)絡(luò)的結(jié)構(gòu)演變及其動(dòng)力學(xué)過(guò)程，將時(shí)序網(wǎng)絡(luò)與多層網(wǎng)絡(luò)分析法相結(jié)合，按層內(nèi)和層間交互關(guān)系構(gòu)建多層時(shí)序網(wǎng)絡(luò)模型。此外，基于隨機(jī)游走的擴(kuò)散過(guò)程來(lái)評(píng)估不同節(jié)點(diǎn)的影響力。由于經(jīng)典隨機(jī)游走關(guān)注在鄰居節(jié)點(diǎn)間的無(wú)差別跳轉(zhuǎn)，忽略具有不同鏈接關(guān)系的節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的影響不同[13]，進(jìn)而造成節(jié)點(diǎn)識(shí)別的效率低、誤差性高。基于此，建立基于節(jié)點(diǎn)相似性的有偏隨機(jī)游走，并結(jié)合多層時(shí)序網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，將有偏隨機(jī)游走應(yīng)用于PageRank，根據(jù)層內(nèi)節(jié)點(diǎn)的有偏跳轉(zhuǎn)以及上層中節(jié)點(diǎn)對(duì)下層中副本節(jié)點(diǎn)的單向作用，提出一種集合層內(nèi)及層間雙重因素的節(jié)點(diǎn)排序算法multilayer temporal biased PageRank(MTB-PR)，可以獲取節(jié)點(diǎn)重要性隨時(shí)間變化的情況。隨后，引入偏差參數(shù)來(lái)調(diào)整節(jié)點(diǎn)對(duì)層內(nèi)及層間因素的依賴(lài)性。通過(guò)對(duì)該算法得出的節(jié)點(diǎn)排序與相應(yīng)的無(wú)偏方法中的結(jié)果比較驗(yàn)證該算法的合理性和有效性；并且可以通過(guò)適當(dāng)調(diào)整步行中的偏差來(lái)更準(zhǔn)確捕獲網(wǎng)絡(luò)中排名靠前的節(jié)點(diǎn)。

1 多層時(shí)序網(wǎng)絡(luò)構(gòu)建

時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)間的交互關(guān)系呈現(xiàn)時(shí)變性，隨時(shí)間變化可以獲得節(jié)點(diǎn)在不同時(shí)間層上的鏈接關(guān)系，同時(shí)考慮網(wǎng)絡(luò)的完整結(jié)構(gòu)演變，前后時(shí)間層間必然存在單向影響。因此，具有N個(gè)節(jié)點(diǎn)和時(shí)間長(zhǎng)度為T(mén)的時(shí)序網(wǎng)絡(luò)可以表示成多層拓?fù)浣Y(jié)構(gòu)(圖1)。多層網(wǎng)絡(luò)的層數(shù)通過(guò)對(duì)T的有效切分得到L=T/t，其中L表示多層時(shí)序網(wǎng)絡(luò)的層數(shù)，t表示每一層網(wǎng)絡(luò)所經(jīng)歷的時(shí)間。多層時(shí)序網(wǎng)絡(luò)是由多個(gè)子網(wǎng)絡(luò)按時(shí)間順序彼此間形成單向有序鏈接且相互作用的系統(tǒng)。其中相同的一組節(jié)點(diǎn)由同一類(lèi)型的相互作用所連接，連邊隨時(shí)間變化且具有時(shí)間先后順序。

圖1 時(shí)序網(wǎng)絡(luò)到多層時(shí)序網(wǎng)絡(luò)的映射圖Fig.1 Mapping from temporal network to multilayer temporal network

2 多層時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評(píng)判

本節(jié)對(duì)經(jīng)典隨機(jī)游走的擴(kuò)散過(guò)程進(jìn)行了改進(jìn)，提出了基于節(jié)點(diǎn)相似性的有偏隨機(jī)游走。基于多層時(shí)序網(wǎng)絡(luò)中不同時(shí)間層間存在的單向作用，將有偏隨機(jī)游走應(yīng)用于PageRank，提出了一種集合層內(nèi)及層間雙重因素的節(jié)點(diǎn)排序算法多層時(shí)序PageRank。

2.1 基于節(jié)點(diǎn)相似性的有偏隨機(jī)游走

隨機(jī)游走是描述復(fù)雜實(shí)體上發(fā)生擴(kuò)散過(guò)程的基本模型之一。在經(jīng)典擴(kuò)散過(guò)程中，隨機(jī)游走者通常以相等概率隨機(jī)跳轉(zhuǎn)到相鄰節(jié)點(diǎn)，一定程度忽略了節(jié)點(diǎn)的異質(zhì)性[14]。Ding等[15]在傳統(tǒng)的擴(kuò)散過(guò)程中引入了有偏游走的思想，使得某一時(shí)刻的隨機(jī)游走者強(qiáng)制性的偏向于跳轉(zhuǎn)到具有某些特殊屬性(例如度，強(qiáng)度或聚類(lèi))的鄰居節(jié)點(diǎn)。然而這些算法大多強(qiáng)調(diào)節(jié)點(diǎn)局部或全局的拓?fù)鋵傩裕雎粤斯?jié)點(diǎn)間相互作用對(duì)整個(gè)網(wǎng)絡(luò)的影響?，F(xiàn)考慮現(xiàn)實(shí)社交網(wǎng)絡(luò)中，人們更傾向于與自己關(guān)系更為相似的人建立親密關(guān)系，例如，朋友的朋友往往也會(huì)成為朋友。商業(yè)競(jìng)爭(zhēng)網(wǎng)絡(luò)中，兩個(gè)企業(yè)越相似，它們的競(jìng)爭(zhēng)就越激烈。即節(jié)點(diǎn)間的相似度越高，則彼此間的影響力越大。所以，引入節(jié)點(diǎn)間相似性指標(biāo)作為衡量節(jié)點(diǎn)局部重要性的標(biāo)志，給出節(jié)點(diǎn)相似性矩陣的定義如下：

定義1節(jié)點(diǎn)相似性矩陣S。具有N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中節(jié)點(diǎn)i與其鄰居節(jié)點(diǎn)j的相似性Sij為

(1)

式(1)中：α(i)與α(j)分別為節(jié)點(diǎn)i和j的鄰居節(jié)點(diǎn)集。

式(1)表明：①兩個(gè)節(jié)點(diǎn)之間擁有的共同鄰居數(shù)越多，則彼此之間越相似，這與現(xiàn)實(shí)世界相符合，擁有很多共同朋友的兩個(gè)人彼此之間成為朋友的概率更大；生物網(wǎng)中，物種之間生態(tài)需求越是一致則他們的形態(tài)越相似。②相鄰節(jié)點(diǎn)之間的相似性存在差異，即節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j的相似度不同于節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的相似度，鄰居節(jié)點(diǎn)數(shù)量較多的一方對(duì)另一方的影響力更大。這與直觀判斷相符，以生態(tài)競(jìng)爭(zhēng)網(wǎng)絡(luò)為例，食物相似的物種為爭(zhēng)奪食物,競(jìng)爭(zhēng)會(huì)相對(duì)更加激烈，而這個(gè)過(guò)程中，食物種類(lèi)較多的物種由于存在較多選擇，因而受到來(lái)自食物種類(lèi)較少的物種的競(jìng)爭(zhēng)壓力遠(yuǎn)遠(yuǎn)低于其本身對(duì)后者帶來(lái)的競(jìng)爭(zhēng)壓力。

基于上述分析，將節(jié)點(diǎn)相似性引入隨機(jī)游走過(guò)程，得出了基于節(jié)點(diǎn)相似性有偏隨機(jī)游走的跳轉(zhuǎn)概率。

(2)

2.2 多層時(shí)序有偏PageRank算法

PageRank算法是建立在經(jīng)典隨機(jī)游走模型基礎(chǔ)上的節(jié)點(diǎn)排序算法，它不僅考慮節(jié)點(diǎn)自身重要性，同時(shí)關(guān)注其鄰居節(jié)點(diǎn)的影響，具有較強(qiáng)的向多層網(wǎng)絡(luò)擴(kuò)展的優(yōu)勢(shì)。本節(jié)將有偏隨機(jī)游走應(yīng)用于PageRank，結(jié)合多層時(shí)序網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)節(jié)點(diǎn)進(jìn)行中心性度量?？紤]到多層時(shí)序網(wǎng)絡(luò)中層間鏈接呈現(xiàn)為時(shí)序相繼性的有向連邊，節(jié)點(diǎn)在上一時(shí)刻的狀態(tài)必然會(huì)影響其在下一時(shí)刻的重要性且這種影響只能通過(guò)時(shí)刻t影響時(shí)刻t+1的狀態(tài)，呈現(xiàn)單向性。所以，綜合考慮網(wǎng)絡(luò)中節(jié)點(diǎn)和層的雙重特性，在各層內(nèi)引入有偏隨機(jī)游走，評(píng)估相鄰節(jié)點(diǎn)間的相似性對(duì)節(jié)點(diǎn)的影響。與此同時(shí)，結(jié)合層間的單向有序聯(lián)系，進(jìn)一步深入分析上一時(shí)刻節(jié)點(diǎn)的中心性對(duì)下一時(shí)刻該節(jié)點(diǎn)中心性的影響。具體步驟如下：

(3)

式(3)中：σ是阻尼系數(shù)，根據(jù)經(jīng)驗(yàn)研究，取σ=0.85；指數(shù)η取值為0或1，當(dāng)η=0時(shí)，有偏PageRank恢復(fù)為無(wú)偏PageRank(CPR)，即節(jié)點(diǎn)i的CPR中心性為

(4)

(5)

需要注意的是，η=0時(shí)，多層時(shí)序有偏PageRank(MTB-PR)將恢復(fù)為無(wú)偏的情況，即為多層時(shí)序無(wú)偏PageRank(MTU-PR)。

(6)

節(jié)點(diǎn)的重要性最終取決于漫游者訪問(wèn)節(jié)點(diǎn)的頻率的大小。根據(jù)這些訪問(wèn)頻率得到的節(jié)點(diǎn)排名正好是多層時(shí)序PageRank中心度量產(chǎn)生的排序，反映了每個(gè)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中重要性。

3 數(shù)據(jù)建模與結(jié)果分析

3.1 數(shù)據(jù)收集與建模

本文數(shù)據(jù)集取自association for computing machinery(ACM)Hypertext 2009會(huì)議[16]期間大約2 d內(nèi)111名與會(huì)人員面對(duì)面交互的動(dòng)態(tài)過(guò)程。每個(gè)人都是一個(gè)節(jié)點(diǎn)，持續(xù)時(shí)間大于20 s的面對(duì)面互動(dòng)則構(gòu)建為邊。按時(shí)間相繼性將數(shù)據(jù)按天切分，構(gòu)建為兩層的多層時(shí)序網(wǎng)絡(luò)，層間相同節(jié)點(diǎn)創(chuàng)建時(shí)序相繼性的有向邊。其中各層為無(wú)向無(wú)權(quán)網(wǎng)絡(luò)。網(wǎng)絡(luò)基本統(tǒng)計(jì)特性如表1所示。

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

3.2.1 引入節(jié)點(diǎn)相似性對(duì)節(jié)點(diǎn)排名的影響

首先利用經(jīng)典PageRank(CPR)對(duì)網(wǎng)絡(luò)各層中的節(jié)點(diǎn)進(jìn)行排序，然后通過(guò)基于節(jié)點(diǎn)相似性的有偏PageRank(SBPR)對(duì)節(jié)點(diǎn)排名，兩者的排名結(jié)果如圖2所示。

圖2 通過(guò)經(jīng)典PageRank(CPR)和有偏PageRank(SBPR)算法所得的節(jié)點(diǎn)排名對(duì)比結(jié)果Fig.2 Comparison of node rankings obtained by classical PageRank (CPR) and node similarity-based biased PageRank (SBPR)

顯而易見(jiàn)，SBPR對(duì)作者排名的影響是非常顯著的，這可以從圖2中節(jié)點(diǎn)的分散分布得到證明。從圖2中的局部放大圖可以看到，節(jié)點(diǎn)顯著地分散在圖2中黑色直線的兩側(cè)，表明基于相似性的有偏PageRank(SBPR)克服了經(jīng)典PageRank以均勻概率游走忽略了節(jié)點(diǎn)異質(zhì)性的問(wèn)題，兩者結(jié)果之間的顯著差異進(jìn)一步證明考慮節(jié)點(diǎn)間相似性的重要性，因?yàn)槠湓诖_定與會(huì)者排名方面發(fā)揮了重要作用。

3.2.2 多層時(shí)序有偏PageRank與多層時(shí)序無(wú)偏PageRank所得節(jié)點(diǎn)重要性分析

在ACM Hypertext 2009網(wǎng)絡(luò)中應(yīng)用多層時(shí)序有偏PageRank(MTB-PR)算法，分別考慮η=0和η=1的情況，值得注意的是，η=0時(shí)，多層時(shí)序有偏PageRank恢復(fù)為無(wú)偏的情況。首先在層1和層2中使用無(wú)偏PageRank(CPR)(即經(jīng)典PageRank)對(duì)與會(huì)者排名，然后通過(guò)已有的層1中的PageRank在層2上計(jì)算多層時(shí)序無(wú)偏PageRank(MTU-PR)，以上對(duì)應(yīng)于η=0的情形。當(dāng)η=1時(shí)，與無(wú)偏的情況類(lèi)似，首先使用基于相似性的有偏PageRank(SBPR)來(lái)獲得層1與層2中與會(huì)者的中心性排名。再次，計(jì)算層2上節(jié)點(diǎn)的多層時(shí)序有偏PageRank(MTB-PR)。在這里，僅考慮偏差參數(shù)a=1、b=1的情況。如圖3所示，節(jié)點(diǎn)在兩層網(wǎng)絡(luò)中的排名(即散點(diǎn)圖分布)有很大差異，表明無(wú)偏或有偏的多層時(shí)序PageRank對(duì)與會(huì)者排名產(chǎn)生了顯著的影響，這種現(xiàn)象闡明了這樣一個(gè)事實(shí)：與MTU-PR相比，MTB-PR在隨機(jī)游走過(guò)程中加入了節(jié)點(diǎn)間相似性的影響，這導(dǎo)致MTB-PR找到排名靠前的節(jié)點(diǎn)的效率更高，進(jìn)而能夠更有效地探索多層時(shí)序網(wǎng)絡(luò)。

圖3 各層中通過(guò)CPR或SBPR所得節(jié)點(diǎn)排名分別與其相對(duì)應(yīng)的通過(guò)MTU-PR或MTB-PR所得排名的對(duì)比結(jié)果Fig.3 Comparison between nodes for CPR and SBPR in each layer with corresponding multilayer temporal MTU-PR and MTB-PR values

另外，節(jié)點(diǎn)在第一層中交流的方式和顯著性會(huì)影響其在下一層網(wǎng)絡(luò)中的顯著性，即無(wú)偏或有偏的多層時(shí)序PageRank可以提高第一層中重要性突出的節(jié)點(diǎn)在第二層中的中心性排名，如圖3(a)、圖3(b)與圖3(c)、圖3(d)的對(duì)比結(jié)果所示，在兩層網(wǎng)絡(luò)中排名都較高的與會(huì)者106獲得了更大的MTU-PR或MTB-PR。而在第二層中重要性較為顯著的與會(huì)者9受到第一層排名靠后的影響，其在MTU-PR或MTB-PR中重要性相比第二層都所有降低。

通過(guò)MTU-PR和MTB-PR所得到排名前40的與會(huì)者情況如圖4所示。在40個(gè)排名的前10名與會(huì)者中，第106位與會(huì)者由于在兩層網(wǎng)絡(luò)中都獲得了較高的CPR和SBPR，最終獲得了更大的MTU-PR和MTB-PR，因此在圖4(a)和圖4(b)中都排名第1。除此之外，其余9名與會(huì)者的排名在圖4(a)和圖4(b)中出現(xiàn)了明顯的差異，圖4(b)中新的與會(huì)者111和51排名進(jìn)入前10，而原先在圖4(a)中排名第2的與會(huì)者25則排名相對(duì)靠后，變?yōu)榈?2名。同時(shí)，圖4(a)和圖4(b)中同時(shí)位于前10的與會(huì)者排名位置也發(fā)生了顯著變化。產(chǎn)生的差異在于與有偏多層時(shí)序PageRank相關(guān)的漫游者在接收上層節(jié)點(diǎn)中心性影響的同時(shí)通過(guò)評(píng)估節(jié)點(diǎn)間的相似性?xún)?yōu)先訪問(wèn)與源節(jié)點(diǎn)相似度高的目標(biāo)節(jié)點(diǎn)，而無(wú)偏方法中的步行者僅以均勻概率隨機(jī)地移動(dòng)到目的地節(jié)點(diǎn)。上述結(jié)果表明，通過(guò)考慮節(jié)點(diǎn)間相互作用的影響，有偏多層時(shí)序PageRank通常優(yōu)于其無(wú)偏的情況，可以探索并識(shí)別ACM Hypertext 2009網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，并能更有效地找到一些最有影響力的與會(huì)者。

圖4 根據(jù)MTU-PR和MTB-PR得到的排名前40的節(jié)點(diǎn)Fig.4 Centrality values of the top 40 participants given by MTU-PR and MTB-PR

3.2.3 不同偏差參數(shù)下節(jié)點(diǎn)的排序結(jié)果分析

最后，通過(guò)改變偏差參數(shù)a、b生成多層時(shí)序有偏PageRank(MTB-PR)研究不同的偏差參數(shù)a、b如何影響與會(huì)者在超文本動(dòng)態(tài)聯(lián)系網(wǎng)絡(luò)中的中心性排名，結(jié)果如圖5所示。

圖5(a)對(duì)應(yīng)于參數(shù)a=1且b=1、3、5的情形，b越大，層內(nèi)因素即節(jié)點(diǎn)間相似度在漫游者選擇目標(biāo)節(jié)點(diǎn)優(yōu)先訪問(wèn)時(shí)所占權(quán)重越大，此時(shí)，節(jié)點(diǎn)中心性更多地受到層內(nèi)因素的影響。隨著b的增大，與會(huì)者50、88、109的中心性逐漸增加，表明他們?cè)诘诙又芯哂信e足輕重的作用。與會(huì)者59、75、106排名的降低則表明隨機(jī)游走過(guò)程中他們是與源節(jié)點(diǎn)相似度較小的節(jié)點(diǎn)。

如圖5(b)將偏差參數(shù)設(shè)置為a=1、3、5且b=1。此時(shí)，a>b，層間因素即來(lái)自于上層節(jié)點(diǎn)中心性的影響所占權(quán)重更大。這導(dǎo)致漫游者優(yōu)先訪問(wèn)在第一層具有高強(qiáng)度的節(jié)點(diǎn)。參數(shù)a、b的不同取值導(dǎo)致了圖5(a)和圖5(b)中節(jié)點(diǎn)中心性的不同分布。與會(huì)者25、52、59、106占據(jù)突出地位，而9、56、59卻有所降低，這表明前者得到來(lái)自上一層中節(jié)點(diǎn)中心性的增益更大。

上述分析證實(shí)了文中的假設(shè)，即由于各層拓?fù)浣Y(jié)構(gòu)的不同及層間的有序單向作用，多層時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性受到層內(nèi)和層間因素協(xié)同效應(yīng)的強(qiáng)烈影響。通過(guò)改變偏差參數(shù)值，MTB-PR可以有效捕獲這些效應(yīng)，又可以根據(jù)兩者影響權(quán)重的大小有針對(duì)性地挖掘有重要影響的與會(huì)者。

圖5 ACM Hypertext 2009網(wǎng)絡(luò)中不同參數(shù)值下節(jié)點(diǎn)的排名結(jié)果Fig.5 The ranking of nodes for different parameter values in the ACM Hypertext 2009 network

4 結(jié)論

從時(shí)序網(wǎng)絡(luò)和多層網(wǎng)絡(luò)相結(jié)合的角度出發(fā)，構(gòu)建了多層時(shí)序網(wǎng)絡(luò)模型，該模型完整揭示了時(shí)序網(wǎng)絡(luò)基于時(shí)間的結(jié)構(gòu)演變及其動(dòng)力學(xué)過(guò)程，能廣泛適用于實(shí)際問(wèn)題。提出一種基于節(jié)點(diǎn)相似性有偏游走的MTB-PR節(jié)點(diǎn)重要性評(píng)估算法，該算法考慮相鄰節(jié)點(diǎn)間相互作用以及層間因素對(duì)節(jié)點(diǎn)重要性的影響，并引入偏差參數(shù)用于調(diào)整節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的相對(duì)重要性對(duì)于層內(nèi)及層間因素的依賴(lài)程度，提高了時(shí)序網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)評(píng)估的準(zhǔn)確性。以ACM Hypertext 2009會(huì)議數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)，對(duì)節(jié)點(diǎn)重要性進(jìn)行分析和評(píng)價(jià)，驗(yàn)證了算法的可靠性和科學(xué)性。下一步，將針對(duì)時(shí)序網(wǎng)絡(luò)中一組關(guān)鍵節(jié)點(diǎn)進(jìn)行重要性評(píng)估。