基于層間相似性的時序網(wǎng)絡(luò)節(jié)點重要性研究?

楊劍楠 劉建國 郭強

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

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

1 引 言

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

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

2 理論基礎(chǔ)

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

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

2.2 鄰居拓撲重疊系數(shù)

鄰居拓撲重疊系數(shù)源自文獻[12]提出的時序相關(guān)系數(shù),時序相關(guān)系數(shù)具體表示為

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

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

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

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

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

3 改進方法

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

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

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

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

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

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

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

3.2 特征向量中心性

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

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

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

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

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

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

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

為了檢驗SSAM方法對時序網(wǎng)絡(luò)節(jié)點重要性排序的效果,本文用了兩個實證網(wǎng)絡(luò)來進行實驗,分別為Workspace數(shù)據(jù)和Enrons數(shù)據(jù).Workspace[19]為法國某公司通過移動射頻設(shè)備獲取的公司員工之間面對面交互產(chǎn)生的交互數(shù)據(jù),時間從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)計特性具體描述如表2,其中N表示節(jié)點總數(shù),T表示切分的時間層網(wǎng)絡(luò)數(shù),C表示節(jié)點之間的總交互次數(shù),E表示整個聚合網(wǎng)絡(luò)的連邊數(shù),During為該數(shù)據(jù)記錄的時段.

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

4.2 評價方法

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

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

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

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

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

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

4.3 結(jié)果分析

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

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

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

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

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

5 結(jié) 論

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

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

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

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

[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)[劉建國,任卓明,郭強,汪秉宏2013物理學(xué)報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)[任卓明,邵鳳,劉建國,郭強,汪秉宏2013物理學(xué)報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計算機科學(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計算機應(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