楊劍楠 劉建國 郭強(qiáng)

1)(上海理工大學(xué)復(fù)雜系統(tǒng)科學(xué)研究中心,上海 200093)

2)(上海財(cái)經(jīng)大學(xué)金融科技研究院,上海 200433)

1 引 言

時(shí)序網(wǎng)絡(luò)考慮節(jié)點(diǎn)之間的交互關(guān)系和次序,可以更加準(zhǔn)確地刻畫手機(jī)通訊、社交等復(fù)雜系統(tǒng)的交互關(guān)系[1?5].節(jié)點(diǎn)重要性的評(píng)價(jià)方法有很多種,如度中心性、介數(shù)中心性、緊密度中心性、特征向量中心性、K-核中心性等,不同的評(píng)價(jià)方法其側(cè)重點(diǎn)也各有不同[6?8].劉建國等[6]分別從網(wǎng)絡(luò)結(jié)構(gòu)和傳播動(dòng)力學(xué)的角度,對(duì)現(xiàn)有的復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序方法進(jìn)行了系統(tǒng)的比較、歸納與總結(jié).Liu等[9]綜合網(wǎng)絡(luò)結(jié)構(gòu)和傳播動(dòng)力學(xué)特征進(jìn)行耦合分析,利用差分方程考察傳播過程,對(duì)節(jié)點(diǎn)重要性進(jìn)行排序.盡管對(duì)于節(jié)點(diǎn)重要性排序的研究在靜態(tài)網(wǎng)絡(luò)上已經(jīng)取得了一定進(jìn)展,但時(shí)序網(wǎng)絡(luò)不同于靜態(tài)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò),由于時(shí)間維度的引入,網(wǎng)絡(luò)的連邊隨時(shí)間會(huì)間斷性地出現(xiàn)和消失[5,10].所以,近些年人們開始對(duì)時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)重要性的研究方法進(jìn)行探究.Tang等[11,12]基于時(shí)間切片的網(wǎng)絡(luò),通過時(shí)序最短路徑定義了時(shí)序介數(shù)中心性和時(shí)序緊密度中心性等統(tǒng)計(jì)特性,并提出了節(jié)點(diǎn)重要性預(yù)測(cè)及網(wǎng)絡(luò)切片方法等.鄧冬梅等[13,14]基于節(jié)點(diǎn)邊貢獻(xiàn)值來評(píng)價(jià)節(jié)點(diǎn)重要性,考慮網(wǎng)絡(luò)時(shí)間屬性并定義事件相關(guān)節(jié)點(diǎn)感染方式,提出了時(shí)序社交網(wǎng)絡(luò)中節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)與排序算法.Kim和Anderson[15]在構(gòu)建時(shí)序網(wǎng)絡(luò)時(shí)規(guī)定每個(gè)時(shí)間切片上的事件僅有一次,并將切片間用有向邊連接,轉(zhuǎn)化為沿時(shí)間單向的有向靜態(tài)圖,從而定義了有向時(shí)序圖的度中心性、介數(shù)中心性和緊密度中心性.Huang和Yu[16]將文獻(xiàn)[9]中考慮動(dòng)力學(xué)指標(biāo)的重要節(jié)點(diǎn)識(shí)別方法引入時(shí)序網(wǎng)絡(luò)中,對(duì)節(jié)點(diǎn)重要性進(jìn)行度量.

但上述方法都只考慮時(shí)間切片上的連接關(guān)系,為了完整地表示時(shí)序網(wǎng)絡(luò)的結(jié)構(gòu)演變及其動(dòng)力學(xué)過程,還需要考慮不同時(shí)間切片之間的連接關(guān)系.Taylor等[17]考慮用多層耦合網(wǎng)絡(luò)分析的方法,將時(shí)序網(wǎng)絡(luò)按層間關(guān)系和層內(nèi)關(guān)系建立超鄰接矩陣(supra-adjacency matrix,SAM),并定義了基于特征向量的中心性指標(biāo)和節(jié)點(diǎn)重要性隨時(shí)間波動(dòng)的評(píng)判指標(biāo).然而,經(jīng)典的SAM方法中時(shí)序網(wǎng)絡(luò)的構(gòu)建,其層間關(guān)系為參數(shù)表示,忽略了不同節(jié)點(diǎn)層間連接關(guān)系的差異性.基于此,考慮到不同節(jié)點(diǎn)的層間連接關(guān)系應(yīng)不同,本文將節(jié)點(diǎn)的層間連接關(guān)系用鄰居拓?fù)渲丿B系數(shù)表示,提出了基于節(jié)點(diǎn)層間相似性的超鄰接矩陣(similarity-based supra-adjacency matrix,SSAM)時(shí)序網(wǎng)絡(luò)構(gòu)建方法,利用特征向量中心性指標(biāo),獲取節(jié)點(diǎn)在各個(gè)時(shí)間層上的重要性排序,并得到節(jié)點(diǎn)重要性隨時(shí)間變化的軌跡.通過節(jié)點(diǎn)刪除法判斷節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力,利用刪除節(jié)點(diǎn)后網(wǎng)絡(luò)效率的變化情況來評(píng)價(jià)節(jié)點(diǎn)的重要性排序,并與SAM方法的不同參數(shù)結(jié)果做比較.Workspace和Enrons數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示,相比于SAM方法,SSAM方法最終的Kendall’sτ值在各時(shí)間層上的平均提高,最高為17.72%和12.44%,說明SSAM方法由于避免了節(jié)點(diǎn)共用參數(shù)可能造成的高估或者低估節(jié)點(diǎn)的層間連接關(guān)系,所以可以更為恰當(dāng)?shù)孛枋鰰r(shí)序網(wǎng)絡(luò),從而更準(zhǔn)確地識(shí)別時(shí)序網(wǎng)絡(luò)中的重要節(jié)點(diǎn).

2 理論基礎(chǔ)

2.1 時(shí)序網(wǎng)絡(luò)描述

時(shí)序網(wǎng)絡(luò)是一個(gè)包含了個(gè)體及個(gè)體間按時(shí)間順序相互作用的系統(tǒng),將個(gè)體視為節(jié)點(diǎn),個(gè)體間的相互作用視為節(jié)點(diǎn)間的連邊,節(jié)點(diǎn)間連邊隨時(shí)間變化且具有時(shí)間先后順序.通常定義一個(gè)網(wǎng)絡(luò)G=(V,E),其中所有節(jié)點(diǎn)構(gòu)成節(jié)點(diǎn)集為V={v1,v2,···,vN},如果不考慮時(shí)序網(wǎng)絡(luò)中交互事件發(fā)生的時(shí)長(zhǎng),則時(shí)序網(wǎng)絡(luò)整個(gè)觀察期[0,m]內(nèi)的邊可以用三元組et=(i,j,t)來描述,表示節(jié)點(diǎn)i與節(jié)點(diǎn)j在t時(shí)刻發(fā)生了一次交互,故所有這樣的邊構(gòu)成邊集E={e1,e2,···,et}.可以將這樣的時(shí)序網(wǎng)絡(luò)整個(gè)觀察期[0,m]按一定時(shí)間間隔切分為T個(gè)時(shí)間窗口(其中時(shí)間間隔為m/T),則網(wǎng)絡(luò)被分為T個(gè)離散有序的時(shí)間層網(wǎng)絡(luò)G1,G2,···,GT.

2.2 鄰居拓?fù)渲丿B系數(shù)

鄰居拓?fù)渲丿B系數(shù)源自文獻(xiàn)[12]提出的時(shí)序相關(guān)系數(shù),時(shí)序相關(guān)系數(shù)具體表示為

其中aij(t),aij(t+1)分別為相鄰時(shí)間層網(wǎng)絡(luò)Gt,Gt+1對(duì)應(yīng)的鄰接矩陣中的元素,如果在網(wǎng)絡(luò)Gt中節(jié)點(diǎn)i與節(jié)點(diǎn)j之間有連邊,那么aij(t)=1;否則aij(t)=0.且只有節(jié)點(diǎn)j既是節(jié)點(diǎn)i在時(shí)間層Gt上的鄰居節(jié)點(diǎn)同時(shí)又是在時(shí)間層Gt+1上的鄰居節(jié)點(diǎn)時(shí),才有aij(t)aij(t+1)=1;其他情況時(shí)aij(t)aij(t+1)=0.

鄰居拓?fù)渲丿B系數(shù)描述了節(jié)點(diǎn)持續(xù)出現(xiàn)度及節(jié)點(diǎn)鄰居關(guān)系的層間相似性.該系數(shù)越大表示節(jié)點(diǎn)持續(xù)出現(xiàn)在兩個(gè)相繼時(shí)間層,且鄰接關(guān)系保持穩(wěn)定;反之,系數(shù)越小表示節(jié)點(diǎn)未持續(xù)出現(xiàn)在兩個(gè)相繼時(shí)間層或相鄰時(shí)間層上鄰接關(guān)系較不穩(wěn)定.

2.3 經(jīng)典的SAM時(shí)序網(wǎng)絡(luò)模型

為了更完整地構(gòu)建時(shí)序網(wǎng)絡(luò),文獻(xiàn)[17]將時(shí)序網(wǎng)絡(luò)通過層內(nèi)連接關(guān)系和層間連接關(guān)系來表示,提出了經(jīng)典的超鄰接矩陣SAM模型,SAM為NT×NT的分塊矩陣.其中層內(nèi)連接關(guān)系用相應(yīng)時(shí)間層網(wǎng)絡(luò)的鄰接關(guān)系A(chǔ)(1),A(2),···,A(T)表示,均為N×N的矩陣;層間連接關(guān)系用一個(gè)參數(shù)ω來表示,參數(shù)大小調(diào)節(jié)網(wǎng)絡(luò)層間連接關(guān)系的緊密程度.對(duì)于一個(gè)給定節(jié)點(diǎn)數(shù)為N的時(shí)序網(wǎng)絡(luò)Γ,其切分的有序時(shí)間層網(wǎng)絡(luò)集合為Γ={Gt}t=1,2,···,T,T為切分的時(shí)間層總數(shù),則其SAM具體表示如下:

其中,A表示經(jīng)典的時(shí)序網(wǎng)絡(luò)模型;A(1),A(2),···,A(T)表示層內(nèi)連接關(guān)系,這里用切分的T個(gè)時(shí)間層網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣表示,依次位于SAM的對(duì)角線上,表示有序的時(shí)間層網(wǎng)絡(luò):定義aij(t)為鄰接矩陣A(t)中的元素,則aij(t)=0表示在時(shí)間層網(wǎng)絡(luò)Gt中節(jié)點(diǎn)i與節(jié)點(diǎn)j間無連邊,aij(t)=1表示有連邊關(guān)系;ωI表示層間連接關(guān)系,其中ω為可調(diào)參數(shù),I為N×N單位矩陣.由于這里僅考慮同一節(jié)點(diǎn)在相鄰時(shí)間層間的連接關(guān)系,所以矩陣其他部分均為0.

3 改進(jìn)方法

3.1 基于層間相似性SSAM時(shí)序網(wǎng)絡(luò)模型

由于上述的超鄰接矩陣SAM中,層間關(guān)系的參數(shù)討論使時(shí)序網(wǎng)絡(luò)建模復(fù)雜化,且節(jié)點(diǎn)在相鄰時(shí)間層的連接關(guān)系用同一參數(shù)來表示,忽略了不同節(jié)點(diǎn)的差異性.實(shí)際上,不同節(jié)點(diǎn)對(duì)應(yīng)的層間連接關(guān)系應(yīng)做不同考慮,才能更真實(shí)地反映網(wǎng)絡(luò)連接的實(shí)際情況.基于以上考慮,本文對(duì)SAM的層間連接關(guān)系做了改進(jìn).

考慮到同一節(jié)點(diǎn)在相鄰時(shí)間層之間的連接關(guān)系與其在兩個(gè)時(shí)間層上的持續(xù)出現(xiàn)度及節(jié)點(diǎn)的鄰居關(guān)系層間相似程度有關(guān),所以我們用鄰居拓?fù)渲丿B系數(shù)((2)式)來確定層間連接關(guān)系,則改進(jìn)后基于層間相似性SSAM時(shí)序網(wǎng)絡(luò)模型具體表示形式如下:

其中,A′表示基于節(jié)點(diǎn)層間相似性的超鄰接矩陣SSAM;A(1),A(2),···,A(T)同樣表示層內(nèi)連接關(guān)系,這里用切分的T個(gè)切片網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣表示;C(1,2),C(2,3),···,C(t?1,t)分別表示相鄰時(shí)間層之間的連接關(guān)系,如C(1,2)表示時(shí)間層網(wǎng)絡(luò)G1與時(shí)間層網(wǎng)絡(luò)G2之間的連接關(guān)系.C(t?1,t)為N×N的對(duì)角矩陣,即C(t?1,t)=即為(2)式節(jié)點(diǎn)的鄰居拓?fù)渲丿B系數(shù),用來描述節(jié)點(diǎn)i的層間相似性,即節(jié)點(diǎn)i在時(shí)間層網(wǎng)絡(luò)Gt?1上與時(shí)間層網(wǎng)絡(luò)Gt上的共同鄰居數(shù)所占的比例.本文也只考慮同一節(jié)點(diǎn)在相鄰時(shí)間層之間的連接關(guān)系,所以SSAM矩陣的其他部分均為0.

圖1給出了一個(gè)包含4個(gè)節(jié)點(diǎn)和3個(gè)時(shí)間層的時(shí)序網(wǎng)絡(luò)及SSAM方法的具體表示,其中黑色實(shí)線表示層內(nèi)連接關(guān)系,黑色虛線表示層間連接關(guān)系.

圖1 基于層間相似性方法的時(shí)序網(wǎng)絡(luò)建模實(shí)例Fig.1.An example of SSAM model for temporal network.

則圖1對(duì)應(yīng)的基于層間相似性的矩陣表示如(5)式.具體地,層內(nèi)連接關(guān)系由各個(gè)時(shí)間層網(wǎng)絡(luò)的鄰接矩陣確定,即(5)式的對(duì)角線矩陣塊部分;相鄰時(shí)間層的層間連接關(guān)系則由各個(gè)節(jié)點(diǎn)的層間相似性,即(2)式鄰居拓?fù)渲丿B系數(shù)計(jì)算得到;最后,非相繼時(shí)間層的矩陣塊部分不做考慮,其元素均為0.

3.2 特征向量中心性

特征向量中心性是評(píng)估網(wǎng)絡(luò)節(jié)點(diǎn)重要性的一個(gè)重要指標(biāo)[6],其不僅考慮節(jié)點(diǎn)的重要性程度,同時(shí)綜合考慮鄰居節(jié)點(diǎn)的重要性程度.所以本文利用特征向量中心性,對(duì)時(shí)序網(wǎng)絡(luò)的節(jié)點(diǎn)重要性進(jìn)行度量,即對(duì)上文構(gòu)建的超鄰接矩陣A′求主特征向量(最大特征值對(duì)應(yīng)的特征向量)ν={υ1,υ2,···,υNT}T.這樣,向量ν的第N(t?1)+i個(gè)項(xiàng)即表示第t個(gè)時(shí)間層上的節(jié)點(diǎn)i的特征向量中心性,記為N×T的矩陣W={wit}N×T,則

其中,wit為矩陣W的第i行第t列元素,即為第t個(gè)時(shí)間層上節(jié)點(diǎn)i的特征向量中心性.該指標(biāo)可以獲得各時(shí)間層上節(jié)點(diǎn)重要性的排序,同時(shí)能夠得到節(jié)點(diǎn)在各個(gè)時(shí)間層網(wǎng)絡(luò)重要性隨時(shí)間變化的軌跡.

表1為圖1中實(shí)例網(wǎng)絡(luò)的特征向量中心性指標(biāo)的結(jié)果,并給出了SAM方法參數(shù)ω取0.5的特征向量中心性結(jié)果做對(duì)比.由表1結(jié)果可以得到各時(shí)間層節(jié)點(diǎn)的重要性排序及各個(gè)節(jié)點(diǎn)重要性隨時(shí)間層的變化軌跡,比如對(duì)于SSAM方法,第一時(shí)間層的G1中節(jié)點(diǎn)重要性排序?yàn)?-3-4-2,且可以看出1號(hào)節(jié)點(diǎn)重要性排序隨時(shí)間層變化軌跡為1-1-3.

表1 實(shí)例網(wǎng)絡(luò)中節(jié)點(diǎn)的特征向量中心性Table 1.Eigenvector centrality of nodes in temporal network of Fig.1.

結(jié)合圖1的時(shí)序網(wǎng)絡(luò)可以看到,用共同的參數(shù)0.5來表示不同節(jié)點(diǎn)的層間連接關(guān)系,弱化了持續(xù)出現(xiàn)且節(jié)點(diǎn)層間鄰居相似度高的節(jié)點(diǎn)的重要程度,而強(qiáng)化了孤立節(jié)點(diǎn)的重要程度.例如第一時(shí)間層網(wǎng)絡(luò)G1中的1號(hào)節(jié)點(diǎn),持續(xù)出現(xiàn)在相繼時(shí)間層且層內(nèi)的鄰接關(guān)系穩(wěn)定,雖然其在兩方法中均為該時(shí)間層網(wǎng)絡(luò)中最重要的節(jié)點(diǎn),但是在SAM方法里1號(hào)節(jié)點(diǎn)的重要性值較小為0.2809,而SSAM方法里1號(hào)節(jié)點(diǎn)的重要性值較大為0.3739,說明SAM方法弱化了1號(hào)節(jié)點(diǎn)的重要性值;對(duì)于2號(hào)節(jié)點(diǎn),其在G1中為孤立節(jié)點(diǎn),其重要性值應(yīng)接近于0,而SAM方法高估了G1中2號(hào)節(jié)點(diǎn)的重要性值.所以不難推出,SAM方法中,當(dāng)參數(shù)較大時(shí),更加強(qiáng)化了孤立節(jié)點(diǎn)和層間鄰居相似度低的節(jié)點(diǎn)的重要性;而參數(shù)較小時(shí),則更加弱化了持續(xù)出現(xiàn)且層間鄰居相似度高的節(jié)點(diǎn)的重要性.

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

4.1 數(shù)據(jù)描述

為了檢驗(yàn)SSAM方法對(duì)時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序的效果,本文用了兩個(gè)實(shí)證網(wǎng)絡(luò)來進(jìn)行實(shí)驗(yàn),分別為Workspace數(shù)據(jù)和Enrons數(shù)據(jù).Workspace[19]為法國某公司通過移動(dòng)射頻設(shè)備獲取的公司員工之間面對(duì)面交互產(chǎn)生的交互數(shù)據(jù),時(shí)間從2013年6月24日到2013年7月3日,數(shù)據(jù)按天切分;Enrons[20]為美國某公司員工的郵件往來數(shù)據(jù),數(shù)據(jù)從1999年到2002年,為縮減數(shù)據(jù),取其中2001年的數(shù)據(jù)子集,并按月切分.網(wǎng)絡(luò)基本統(tǒng)計(jì)特性具體描述如表2,其中N表示節(jié)點(diǎn)總數(shù),T表示切分的時(shí)間層網(wǎng)絡(luò)數(shù),C表示節(jié)點(diǎn)之間的總交互次數(shù),E表示整個(gè)聚合網(wǎng)絡(luò)的連邊數(shù),During為該數(shù)據(jù)記錄的時(shí)段.

表2 實(shí)證網(wǎng)絡(luò)基本統(tǒng)計(jì)特性Table 2.Basic statistical features of Workspace and Enrons networks.

4.2 評(píng)價(jià)方法

通常認(rèn)為,節(jié)點(diǎn)重要性不僅體現(xiàn)在節(jié)點(diǎn)在網(wǎng)絡(luò)中對(duì)信息的傳播能力[21?23],也可體現(xiàn)在節(jié)點(diǎn)被移除以后對(duì)網(wǎng)絡(luò)連通的破壞性[8].為進(jìn)一步檢驗(yàn)SSAM方法對(duì)節(jié)點(diǎn)重要性的排序效果,并與SAM方法做對(duì)比,文中通過刪除節(jié)點(diǎn)后網(wǎng)絡(luò)連通性的變化程度來評(píng)價(jià)節(jié)點(diǎn)重要性排序結(jié)果.通常認(rèn)為,刪除節(jié)點(diǎn)后,網(wǎng)絡(luò)連通性變化越大,則被刪除的節(jié)點(diǎn)在網(wǎng)絡(luò)中越重要;反之,則節(jié)點(diǎn)重要性相對(duì)較低.

時(shí)序網(wǎng)絡(luò)效率是評(píng)判時(shí)序網(wǎng)絡(luò)連通性的一個(gè)重要方法,其時(shí)序全局效率[17]的具體形式如下:

其中,dij為時(shí)序網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的時(shí)序距離[12].時(shí)序距離通過時(shí)序最短路徑計(jì)算,時(shí)序最短路徑不同于靜態(tài)網(wǎng)絡(luò)的最短路徑,時(shí)序路徑的有效連接都是臨時(shí)的,會(huì)在某個(gè)特定的時(shí)間點(diǎn)建立或者斷開,所以時(shí)序網(wǎng)絡(luò)中的時(shí)序最短路徑需要遵從于不同連邊的時(shí)間先后順序[4].信息從節(jié)點(diǎn)i經(jīng)過節(jié)點(diǎn)k最終傳到節(jié)點(diǎn)j,需要在時(shí)間維度上要求節(jié)點(diǎn)i到k之間的有效連接發(fā)生在節(jié)點(diǎn)k到j(luò)之前,否則信息不能從節(jié)點(diǎn)i傳到j(luò).

具體地,圖1所示的時(shí)序網(wǎng)絡(luò),假設(shè)有信息從t=1時(shí)的1號(hào)節(jié)點(diǎn)開始傳遞,并傳遞到最終t=3時(shí)刻結(jié)束,且每個(gè)時(shí)間層上只傳遞一步,則表3給出了最終時(shí)序最短路徑的時(shí)序距離dij的結(jié)果.

表3 圖1時(shí)序網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的時(shí)序距離Table 3.Temporal distance of nodes in temporal network of Fig.1.

最后,用刪除節(jié)點(diǎn)前后時(shí)序全局效率的差值作為節(jié)點(diǎn)重要性的驗(yàn)證方法.為了與特征向量中心性矩陣W對(duì)應(yīng),依次刪除各個(gè)時(shí)間層的節(jié)點(diǎn)后重新計(jì)算網(wǎng)絡(luò)的時(shí)序全局效率,得到一個(gè)N×T的矩陣E={eit}N×T,再與原時(shí)序全局效率e做差值,最終得到刪除節(jié)點(diǎn)的時(shí)序全局效率差值矩陣E′,其元素

4.3 結(jié)果分析

本文基于上述兩個(gè)實(shí)證網(wǎng)絡(luò)數(shù)據(jù),依據(jù)SSAM方法和SAM方法的不同參數(shù)取值計(jì)算時(shí)序網(wǎng)絡(luò)中的各時(shí)間層網(wǎng)絡(luò)上節(jié)點(diǎn)的特征向量中心性,分別得到了SSAM和SAM方法對(duì)實(shí)證網(wǎng)絡(luò)數(shù)據(jù)的節(jié)點(diǎn)重要性排序(其中SAM方法的參數(shù)ω取[0.1,0.2,···,1.0]).另外,為了更直觀地檢驗(yàn)SSAM方法的效果,用節(jié)點(diǎn)刪除法得到節(jié)點(diǎn)時(shí)序全局效率差值排序后,利用Kendall’sτ(肯德爾系數(shù))來評(píng)估排序相關(guān)性.具體而言,我們對(duì)特征向量中心性矩陣W和時(shí)序全局效率差值矩陣E′對(duì)應(yīng)的列分別計(jì)算Kendall’s tau,即得到相應(yīng)時(shí)刻上節(jié)點(diǎn)重要性排序同該時(shí)刻刪除節(jié)點(diǎn)后網(wǎng)絡(luò)效率差值排序的一致性程度.

Kendall’sτ[24]被用來測(cè)量?jī)尚蛄兄g排序的相關(guān)性程度,其取值范圍為[?1,1],該值越大,則兩序列相關(guān)性越強(qiáng),即說明節(jié)點(diǎn)重要性的排序方法更加精確.其中對(duì)于兩列數(shù)X={x1,x2,···,xn}和Y={y1,y2,···,yn}的Kendall’sτ-b[25]定義為

這里X表示特征向量中心性矩陣W中第t列的排序列表;Y表示通過刪除節(jié)點(diǎn)法得到的網(wǎng)絡(luò)全局效率差值矩陣E′中對(duì)應(yīng)第t列的排序列表(t=1,2,···,T);sgn(z)為一個(gè)分段函數(shù),當(dāng)z＞0時(shí),sgn(z)=+1,當(dāng)z＜0時(shí),sgn(z)=?1,當(dāng)z=0時(shí),sgn(z)=0,這里n為序列長(zhǎng)度,即節(jié)點(diǎn)總數(shù);其中,ti為X序列中第i個(gè)使得sgn(z)=0的xi值的個(gè)數(shù),uj為Y序列中第j個(gè)使得sgn(z)=0的yj值的個(gè)數(shù).

對(duì)Workspace數(shù)據(jù)和Enrons數(shù)據(jù)分別用SSAM方法和SAM方法的特征向量中心性矩陣與刪除節(jié)點(diǎn)法的網(wǎng)絡(luò)效率差值矩陣得到相應(yīng)時(shí)間層的Kendall’sτ值如圖2所示:圖2(a)為Workspace數(shù)據(jù)的結(jié)果,圖2(b)為Enrons數(shù)據(jù)的結(jié)果;圖2中橫坐標(biāo)表示時(shí)序網(wǎng)絡(luò)切分的各個(gè)時(shí)間層,縱坐標(biāo)表示相應(yīng)時(shí)間層對(duì)應(yīng)的Kendall’s tau值;其中黑色小正方形為SSAM方法,其他為SAM方法取不同參數(shù)的結(jié)果.

圖2 特征向量中心性與時(shí)序網(wǎng)絡(luò)效率差值的Kendall’s tau結(jié)果 (a)Workspace數(shù)據(jù)基于層間相似性的超鄰接矩陣方法和經(jīng)典超鄰接矩陣方法不同參數(shù)的Kendall’s τ結(jié)果;(b)Enrons數(shù)據(jù)相應(yīng)的結(jié)果Fig.2.Results of Kendall’s τ for eigenvector centrality and difference of temporal global efficiency:(a)result for Workspace by SSAM method and SAM method;(b)result for Enrons by SSAM method and SAM method.

由圖2中結(jié)果可以看到:1)對(duì)兩組數(shù)據(jù)的時(shí)序網(wǎng)絡(luò)構(gòu)建中,SAM方法不同參數(shù)下得到的Kendall’sτ結(jié)果大多相近,Enrons數(shù)據(jù)集的結(jié)果在這點(diǎn)尤為顯著,也就是不同的參數(shù)選擇對(duì)于節(jié)點(diǎn)的特征向量中心性在各個(gè)時(shí)間層的排序結(jié)果影響并不顯著,所以SAM方法中,層間連接關(guān)系以參數(shù)來討論使得時(shí)序網(wǎng)絡(luò)構(gòu)建復(fù)雜化,可以考慮用確切的數(shù)值來描述層間連接關(guān)系;2)SSAM方法得到的Kendall’sτ系數(shù)結(jié)果大部分比SAM方法的高,也就是基于層間相似性的SSAM方法考慮了不同節(jié)點(diǎn)的差異性,能更準(zhǔn)確地對(duì)時(shí)序網(wǎng)絡(luò)進(jìn)行描述,得到的節(jié)點(diǎn)重要性排序也更為準(zhǔn)確,且對(duì)于Enrons數(shù)據(jù)的結(jié)果尤為顯著,其中兩組實(shí)證數(shù)據(jù)SSAM方法的結(jié)果相比SAM方法和Kendall’sτ值在各時(shí)間層上的平均提高,最高為17.72%和12.44%;3)對(duì)于Workspace數(shù)據(jù)的個(gè)別時(shí)間層,如t=6,t=7和t=9上,SSAM方法略低于SAM方法,同時(shí)該時(shí)間層上SAM方法的不同參數(shù)結(jié)果差別也略大,我們認(rèn)為此結(jié)果是由于實(shí)際數(shù)據(jù)的影響所造成的.

5 結(jié) 論

識(shí)別網(wǎng)絡(luò)中的重要節(jié)點(diǎn)一直是復(fù)雜網(wǎng)絡(luò)的熱點(diǎn)問題,最近有不少工作開始考慮加入時(shí)間屬性來研究節(jié)點(diǎn)重要性的度量方法,而對(duì)于時(shí)序網(wǎng)絡(luò)的建模也各有不同.本文將時(shí)序網(wǎng)絡(luò)用層內(nèi)鄰接關(guān)系和層間連接關(guān)系共同來描述,并考慮不同節(jié)點(diǎn)的差異性及相繼時(shí)間層的時(shí)序相關(guān)性,用節(jié)點(diǎn)的鄰居拓?fù)渲丿B系數(shù)作為時(shí)序網(wǎng)絡(luò)的層間連接關(guān)系,提出了一種基于節(jié)點(diǎn)層間相似度的超鄰接矩陣建模方法(SSAM方法),同時(shí)利用特征向量中心性來度量節(jié)點(diǎn)的重要性.另外,本文利用節(jié)點(diǎn)刪除法,通過計(jì)算刪除節(jié)點(diǎn)前后網(wǎng)絡(luò)時(shí)序全局效率的變化情況,來評(píng)估SSAM方法對(duì)節(jié)點(diǎn)重要性排序的效果.

兩組實(shí)證數(shù)據(jù)的結(jié)果表明,SSAM方法得到的特征向量中心性排序結(jié)果大部分比SAM方法的好,且SSAM 方法兩組實(shí)驗(yàn)的Kendall’sτ值較SAM方法在各時(shí)間層上的平均提高,最高為17.72%和12.44%.SSAM方法一方面回避了參數(shù)討論,另一方面由于考慮了不同節(jié)點(diǎn)在相鄰時(shí)間層間連接關(guān)系的差異性,用基于節(jié)點(diǎn)的層間相似度構(gòu)建時(shí)序網(wǎng)絡(luò),避免了節(jié)點(diǎn)共用參數(shù)可能造成的高估或者低估節(jié)點(diǎn)的層間連接關(guān)系.綜上所述,本文提出了一種基于層間相似性的時(shí)序網(wǎng)絡(luò)構(gòu)建方法,該方法可以更為恰當(dāng)?shù)孛枋鰰r(shí)序網(wǎng)絡(luò),從而更準(zhǔn)確地識(shí)別時(shí)序網(wǎng)絡(luò)中的重要節(jié)點(diǎn).該工作對(duì)于時(shí)序網(wǎng)絡(luò)建模和對(duì)時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)重要性度量方法的研究具有重要意義.

然而,本文基于層間相似性的SSAM方法是考慮了最直觀的鄰居拓?fù)渲丿B系數(shù)作為相似性的度量指標(biāo),而其他相似性指標(biāo)對(duì)于該方法的應(yīng)用及效果是我們未來可以做進(jìn)一步討論和研究的問題.另外,本文只考慮同一個(gè)節(jié)點(diǎn)在相鄰時(shí)間層的關(guān)系,而實(shí)際中,節(jié)點(diǎn)之間的聯(lián)系不僅依賴于上一時(shí)間層內(nèi)的信息,還可依賴于之前多個(gè)時(shí)間片段內(nèi)的信息,并可影響之后多個(gè)時(shí)間片段,因此具有非馬爾可夫特性;且本文的方法只適用于小規(guī)模的數(shù)據(jù),這就需要新的更為準(zhǔn)確并能用于大規(guī)模數(shù)據(jù)的方法來描述時(shí)序網(wǎng)絡(luò).最后,如何進(jìn)行時(shí)序網(wǎng)絡(luò)的切分及時(shí)間窗大小的選擇一直是個(gè)困難的問題[5],不同的切分情況會(huì)導(dǎo)致不同的實(shí)驗(yàn)結(jié)果,因此如何結(jié)合時(shí)序網(wǎng)絡(luò)的全局結(jié)構(gòu)和網(wǎng)絡(luò)動(dòng)力學(xué)來對(duì)時(shí)序網(wǎng)絡(luò)進(jìn)行構(gòu)建,并識(shí)別出重要節(jié)點(diǎn)是未來需要深入研究的問題.

感謝上海理工大學(xué)復(fù)雜系統(tǒng)科學(xué)研究中心林堅(jiān)洪、楊凱、胡小軍和郭昕宇的交流與討論.參考文獻(xiàn)

[1]Holme P,Saram?ki J 2013Temporal Networks(Heidelberg:Springer)pp1–2

[2]Holme P,Saram?ki J 2012Phys.Rep.519 97

[3]Holme P 2015Eur.Phys.J.B88 234

[4]Liu J G,Ren Z M,Guo Q 2013Physica A392 4154

[5]Ren Z M,Zeng A,Chen D B,Liao H,Liu J G 2014EPL106 48005

[6]Liu J G,Ren Z M,Guo Q,Wang B H 2013Acta Phys.Sin.62 178901(in Chinese)[劉建國,任卓明,郭強(qiáng),汪秉宏2013物理學(xué)報(bào)62 178901]

[7]Lü L Y,Chen D B,Ren X L,Zhang Q M,Zhang Y C,Zhou T 2016Phys.Rep.650 1

[8]Ren Z M,Shao F,Liu J G,Guo Q,Wang B H 2013ActaPhys.Sin.62 128901(in Chinese)[任卓明,邵鳳,劉建國,郭強(qiáng),汪秉宏2013物理學(xué)報(bào)62 128901]

[9]Liu J G,Lin J H,Guo Q,Zhou T 2016Sci.Rep.6 21380

[10]Zhang Y Q,Cui J,Zhang S M,Zhang Q,Li X 2016Eur.Phys.J.B89 26

[11]Tang J,Musolesi M,Mascolo C,Latora V 2009Proceedings of the 2nd ACM Workshop on Online Social NetworksBarcelona,Spain,August 17–17,2009 p31

[12]Tang J,Scellato S,Musolesi M,Mascolo C,Latora V 2010Phys.Rev.E81 055101

[13]Deng D M,Zhu J,Chen D B,Gao H 2013Comput.Sci.40 26(in Chinese)[鄧冬梅,朱建,陳端兵,高輝2013計(jì)算機(jī)科學(xué)40 26]

[14]Deng D M 2014M.S.Dissertation(Chengdu:University of Electronic Science and Technology of China)(in Chinese)[鄧冬梅 2014碩士學(xué)位論文 (成都:電子科技大學(xué))]

[15]Kim H,Anderson R 2012Phys.Rev.E85 026107

[16]Huang D W,Yu Z G 2017Sci.Rep.7 41454

[17]Taylor D,Myers S A,Clauset A,Porter M A 2017Multiscale Model.Simul.15 537

[18]Zhu Y X,Zhang F L,Qin Z G 2014J.Comput.Appl.34 3184(in Chinese)[朱義鑫,張鳳荔,秦志光 2014計(jì)算機(jī)應(yīng)用34 3184]

[19]Génois M,Vestergaard C L,Fournet J,Panisson A 2015Network Sci.3 326

[20]Klimt B,Yang Y 2004Machine Learning:ECML2004 217

[21]Zhang Z K,Liu C,Zhan X X,Lu X,Zhang C X,Zhang Y C 2016Phys.Rep.651 1–34

[22]Liu C,Zhan X X,Zhang Z K,Sun G Q,Hui P M 2015New J.Phys.17 113045

[23]Liu C,Zhang Z K 2014Commun.Nonlinear Sci.Numerical Simulat.19 896

[24]Kendall M G 1938Biometrika30 81

[25]Agresti A 2010Analysis of Ordinal Categorical Data(2nd Ed.)(New York:John Wiley&Sons John Wiley&Sons)pp188–191