基于時序網絡層間同構率動態演化的重要節點辨識*

胡鋼 許麗鵬 徐翔

1) (安徽工業大學管理科學與工程學院, 馬鞍山 243032)

2) (國防科技大學信息系統工程重點實驗室, 長沙 410073)

時序網絡可以更加準確地描述網絡節點在時空演化過程中的交互順序變化和交互關聯關系.為辨識時序網絡中的重要節點, 本文提出基于時序網絡層間同構率動態演化的超鄰接矩陣建模的重要節點辨識方法.首先, 依托復雜網絡的層間時序關聯耦合關系, 定義了相鄰與跨層網絡綜合逼近關系系數.其次, 依據層內連接關系和層間逼近關系構建時序網絡超鄰接矩陣.再次, 使用特征向量中心性方法對時序網絡中的節點重要性排序, 分析計算時序全局效率差值, 通過肯德爾相關系數驗證.最后, 實證數據仿真顯示: 與經典時序網絡模型相比, 本文模型所得Kendall’s t值在各時間層上平均提高, 最高為8.37%和2.99%, 結論表明時序網絡層間同構率的度量方法科學有效.

1 引 言

動態時序網絡研究節點間的時空交互關聯關系和節點重要性動態分類、排序等演化次序辨識,可以更加準確地刻畫手機通訊、社交等復雜系統的交互關系[1].節點重要性的評價方法有很多種, 如度中心性[2]、介數中心性[3]、緊密度中心性[4]、特征向量中心性[5]、K-核中心性[6]等, 不同的評價方法考慮的網絡特征也各有不同.胡鋼等[7]選取了七個代表性指標進行網絡重要性節點貢獻率排序, 研究網絡節點不同重要性指標對節點的影響程度.傳統的節點重要性排序方法多從單獨的指標或因素進行分析, 使得評價結果缺乏全局性與合理性, 于會等[8]提出了基于多屬性決策的復雜網絡節點重要性綜合評價方法.胡鋼等[9]根據解釋結構模型對網絡鄰接矩陣進行級位劃分, 得到網絡的遞階有向圖, 確定節點的重要性.王凱莉等[10]基于網絡中節點自身殼值及其多階鄰居的殼值, 提出了多階鄰居殼數向量中心性方法.Li等[11]從傳播動力學的角度, 提出了一種新的分類鄰居算法來量化節點傳播能力, 進而區分不同節點的影響.

復雜網絡重要節點辨識的研究在靜態網絡上已取得一定進展, 但是在時序網絡(節點間關聯關系隨時間動態變化的網絡)的情況下仍缺乏系統理論方法用于識別時序網絡中的重要節點[12].Tang等[13]通過時序最短路徑定義時序介數中心性和時序緊密度中心性等網絡結構特性, 提出節點重要性預測及網絡切片方法.Zhao等[14]將空氣質量系統創新地抽象為復雜的網絡, 在量化區域動態相互聯系和相互作用的基礎上, 提出一種建模方法來挖掘不同區域之間的關系.Li等[15]提出一種新算法來檢測由網絡中的主要領導者驅動的團簇結構, 并應用于電子商務系統.代萌等[16]基于31年滑動窗口研究了時序空間上干旱多屬性風險的動態特征, 對干旱動態演變的驅動力進行了探究.Qu等[17]提出了用于時序網絡的時序信息收集(TIG)過程, 并探索時序信息對節點重要性的影響.為了利用現有信息來恢復不確定的復雜網絡的拓撲結構和系統參數, Wang等[18]提出了一種基于自適應預期同步的方法來識別存在噪聲的不確定時變時滯復雜網絡的未知系統參數和網絡拓撲結構.Tang等[19]基于拓撲-時間規律的組合提出了一個基于熵率的框架, 用于量化時序網絡的可預測性.Yang等[20]提出一種基于節點相似度的社會網絡模糊化方法,并對網絡模糊密度與模糊中心勢進行預測, 實現模糊網絡的度量預測.Schaub等[21]基于復雜網絡動力學以及多元微分方程, 提出一種復雜網絡的多尺度動態嵌入技術.李志宇等[22]構建針對新增節點的動態特征學習方法, 使得模型可以提取大規模社會網絡在動態變化過程中的結構特征.

上述方法僅僅考慮時序網絡各節點在每個時間切片上的連接關系, 為完整地表示時序網絡的動力學過程和結構演變特征, 還需要考慮時序網絡各節點在不同時間切片間的連接關系.郭強等[23]基于TOPSIS多屬性排序方法得出使用優先鏈接指標(PA)度量挖掘出的重要節點最準確.邱路和黃國妍[24]提出時變狀態網絡模型, 分析不同時間狀態網絡的連接相似性.Taylor等[25]考慮用多層耦合網絡分析的方法, 將時序網絡按層間關系和層內關系建立超鄰接矩陣(supra-adjacency matrix, SAM),并定義了基于特征向量的中心性指標和節點重要性隨時間波動的評判指標.經典的SAM方法忽略了復雜網絡中不同節點層間連接關系的差異性, 楊劍楠等[26]將節點的層間連接關系用鄰居拓撲重疊系數表示, 提出了基于節點層間相似性的超鄰接矩 陣(similarity-based supra-adjacency matrix,SSAM)時序網絡構建方法.朱義鑫等[27]針對相關系數的改進問題, 給出一個網絡演化速度指標; 同時, 提出了一個具有非馬爾可夫性質的時序網絡演化模型.但也只是表達相鄰網絡間的耦合關系, 基于此, 我們考慮了跨層網絡間的相容相似度, 并結合向量在n維實數空間上的投影值以及節點鄰居的貢獻值提出了時序網絡層間逼近關系系數, 實現了信息的矢量計算和標量計算, 通過信息的集結彌補了鄰居拓撲重疊系數的不足, 最后構建了改進的基于時序網絡層間同構率動態演化的超鄰接矩陣模型(isomorphism rate based supra-adjacency matrix, ISAM).Workspace及Email-eu-core數據集上的實驗結果顯示, 本文方法得到的Kendall’st值較SAM方法在各時間層上平均提高, 最高為8.37%和2.99%.且本文方法在算法復雜度上和SAM一樣, 均為o(n2) , 說明本文方法能更準確地辨識時序網絡中的重要節點, 為時序網絡建模提供了一種新的思路.

2 時序網絡相關概念

基于目前研究的復雜網絡相關方法, 本文綜述了時序網絡定義; 同時, 為了時序網絡表征研究更近一步的推廣, 給出了時序網絡向量范數、時序網絡相容相似度系數、時序網絡向量投影值、時序網絡節點資源分配相似度系數以及時序網絡層間逼近關系系數等定義.

2.1 時序網絡定義

網絡科學將復雜系統抽象為復雜網絡, 動態時序網絡是一個包含了個體、個體間交互作用及時間軸的復雜系統.我們將個體視為節點, 則個體間的交互作用形成了節點間的連邊, 邊與邊之間的交互作用形成了網絡分塊, 塊與塊的相互影響構成了整個復雜網絡.當節點間的關聯關系隨時間演化呈現出一定規律, 即發生關聯點、關聯邊隨時間先后增刪的系統性變化, 我們把這樣一個過程叫做時序網絡演化過程.通常一個網絡可以定義為二元組G=(V,E), 所有節點構成節點集V= {v1,v2, ···,vN},節點間的關系構成邊集E= {e1,e2, ···,eH}.在時序網絡中, 邊集E中的元素可以用形如(i,j,t,dt)的四元組表示[28], 表示節點i與節點j從t時刻開始產生交互并持續dt的時長.如視頻通話數據網絡中, 用戶A, B在t1時刻開始視頻通話,t2時刻結束視頻通話, 這個事件可以表示為(A, B,t1,t2–t1), 所有這些四元組的序列構成了視頻通話數據的時序網絡.如果省略時序網絡中個體間發生事件的時長信息, 而只考慮兩個體在某一時間窗內發生交互的初始時刻, 則可以用三元組(i,j,t)來表示節點i與節點j在t時刻發生交互.將時序網絡整個觀察期[t,t+S] 分成T個時間窗口, 每個時間窗的大小為t=S/T, 可以得到T個等間距、不重疊且連續的時間窗口則時序網絡被分為T個離散有序的時間層網絡G1,G2, ···,GT.

2.2 時序網絡層間逼近關系系數分析

定義1時序網絡向量范數.t時刻網絡Gt有鄰接矩陣A= (aij)∈Rn×n(i,j= 1, 2, ···,n), 在無向網絡中, 顯然有AT=A, 即aij=aji.鄰接矩陣A可用向量表示為A= (a1,a2, ···,an)T, 對于向量ai(i= 1, 2, ···,n)∈Rn, 與ai對應的一個實值函數(并記為) ||ai||稱為Rn上的一個向量范數,且滿足:

1) ||ai|| ≥ 0, 其中||ai|| = 0當且僅當ai= 0;

2) ||aai|| = |a| ||ai||,?a∈R;

3) ||ai+ak|| ≤ ||ai|| + ||ak||,?ai,ak∈Rn.

于是有向量ai= (ai1,ai2, ···,ain)∈R范數一般定義

當p→∞, 定義∞–范數:

定義2時序相鄰網絡相容相似度系數.考慮到時序相鄰網絡層上節點自身鄰居的影響[23], 即兩個節點的共同鄰居越多, 兩節點越相似.我們用Salton指標(Salton index, SAL)[29]定義相鄰網絡相容相似度系數, 具體形式如下:

相鄰網絡相容相似度系數描述了節點鄰居關系以及節點間持續關聯的層間同構率.其中aij(t),aij(t+ 1)對應相鄰時間層網絡Gt,Gt+1的鄰接矩陣元素.如果在任一時間層網絡Gt中節點i與節點j之間存在連邊, 則aij(t) = 1; 否則aij(t) = 0.此外, 向量ai在相鄰時刻t,t+ 1均為零向量(孤立節點)時, 規定僅有一個時刻為零向量時, 規定

定義3時序跨層網絡相容相似度系數.時序網絡中節點間的連邊隨時間動態增刪, 僅僅考慮相鄰網絡間的同構率可能無法準確辨識時序網絡的重要節點.基于此, 我們提出了時序跨層網絡相容相似度系數.

例如, 跨一層網絡相容相似度系數

跨兩層網絡相容相似度系數

跨層網絡相容相似度系數揭示了跨層網絡間的同構率, 反映了在某一時間區間內網絡的局部特征與局部鏈塊的魯棒性與穩定性的傳承.參數p隨所跨網絡層數的變化而改變, 即p=m; 當跨層數增加到無窮大的時候, 用∞-范數代替p-范數;m即網絡Gt,Gt+m間的間隔層數, 只有節點j同時滿足在m個時間層上都是節點i的鄰居, 才有aij(t)aij(t+ 1)···aij(t+m) = 1; 其 他 情 況 時aij(t)aij(t+ 1)···aij(t+m) = 0.向量ai在時刻t,t+ 1, ···,t+m均為零向量(孤立節點)時, 規定不全為零向量時, 規定

定義4時序網絡向量投影值.為描述向量在n維實數空間隨時間演化的方向變化, 我們把相鄰層網絡向量之間的夾角叫做向量投影角, 投影角的余弦值定義為投影值.鄰接矩陣A可以由n個行向量(矢量)表示, 則向量ai在兩時間層t,t+m(t,m= 1, 2, ···,T–1)的投影值具體表示為:

(i) 時序相鄰網絡向量投影值(m= 1)

(ii) 時序跨層網絡向量投影值(m> 1)

對于跨層網絡向量投影值, 我們通過兩兩比較相鄰層網絡向量, 根據(7)式求出所有相鄰層網絡的投影值的平均值, 再計算投影值的標準差s,定義為跨層網絡向量投影值其中參數保證該投影值越大, 表示向量ai在時間段[t,t+m](m> 1)的方向一致性越高, 反映節點在時序演化過程中越穩定.

定義5時序網絡節點資源分配相似度系數.靜態網絡中資源分配指標(resource allocation,RA)[30]的思想是: 如果網絡中兩個節點沒有直接相連, 可以將它們的共同鄰居作為傳遞的媒介.基于此, 我們提出了時序網絡節點資源分配相似度系數, 具體如下:

(i) 時序相鄰網絡節點資源分配相似度系數

(ii) 時序跨層網絡節點資源分配相似度系數

例如, 跨一層網絡節點資源分配相似度系數:Γ(it)∩Γ(it+1)

其中 表示節點i在相鄰時間層的共同鄰居,d(z)表示共同鄰居節點的度值.該系數反映了節點間的相似性不僅和共同鄰居的數量有關,還和鄰居節點的質量(度值)有關.節點共同鄰居的數量越多、鄰居節點的度值越小, 則時序相鄰網絡節點資源分配相似度系數越大.

定義6時序網絡層間逼近關系系數.綜合考慮兩時間層網絡相容相似度變化(標量變化)、向量間的投影值變化(矢量變化)以及節點資源分配情況, 我們提出時序網絡層間逼近關系系數Z,Z=表示節點i在兩時間層網絡的同構率, 具體形式如下:

3 時序網絡超鄰接矩陣系統模型構建

經典時序網絡建模時考慮用多層耦合網絡分析的方法, 將時序網絡按層間關系和層內關系建立超鄰接矩陣, 但在表示不同時間層網絡間關系中使用了相同的參數, 忽略了復雜網絡中不同節點層間連接關系的差異性.為此, 我們提出了改進時序網絡建模方法, 在經典SAM模型的基礎上, 給出時序網絡層間逼近關系系數, 并提出改進的ISAM模型.

3.1 經典時序網絡建模思想

文獻[25]將時序網絡通過層內連接關系和層間耦合關系來表示, 提出了經典的SAM時序網絡模型, SAM為NT×NT的分塊矩陣, 為構建時序網絡提供了一種新思路.我們把有序時間層網絡集合定義為G= {Gt} (t= 1, 2, ···,T),T為切分的時間層總數, 則其SAM模型具體表示如下:

其中, 超鄰接矩陣A表示經典的時序網絡模型;A(1),A(2), ···,A(T)表示層內連接關系, 這里用等間距切分的T個時間層網絡對應的鄰接矩陣表示,依次位于超鄰接矩陣A的對角線上, 表示有序的時間層網絡: 定義aij(t)為鄰接矩陣A(t)中的元素,則aij(t) = 1表示在時間層網絡Gt中節點i與節點j間有連邊,aij(t) = 0表示無連邊;wI表示相鄰層網絡層間耦合關系, 其中為可調參數, 在lim時, 層變得不耦合; 在lim時, 層之間的耦合非常強,I為N×N單位矩陣.由于經典的SAM時序網絡模型中僅考慮層的最近鄰耦合關系, 所以超鄰接矩陣A其他部分均用0表示.

3.2 改進時序網絡建模分析

經典的SAM時序網絡模型中, 相鄰層間關系用同一參數w來表示, 忽略了異質網絡中不同節點的差異性, 為了更真實地反映相鄰時間層網絡連接的實際情況, 本文對SAM模型中的相鄰層間關系做出改進, 并考慮了非相鄰層間耦合關系.

時序網絡相鄰層間關系和節點在相鄰網絡間的連接關系與其在相鄰層上的持續出現度及節點的鄰居關系層間相似程度有關[26], 考慮時序演化過程中節點鄰居的數量和質量變化, 我們提出時序網絡層間逼近關系系數Z.改進的基于層間同構率的ISAM時序網絡模型具體表示形式如下:

其中,Z(1,2),Z(2,3), ···表示相鄰時間層之間的逼近關系,Z(1,3), ··· 表示非相鄰層之間的逼近關系;為N×N的對角矩陣, 即即為節點的層間逼近關系系數, 描述了節點i的層間同構率.圖1給出了該模型的算法流程圖, 該模型的算法復雜度TISAM(n)=o(kn2), 其中k是關于時間層數T的函數, 當T?n時,TISAM(n)=o(n2).

圖2給出了一個包含3個時間層和4個節點的時序網絡及ISAM模型的構建, 其中黑色實線表示層內連接關系, 黑色虛線表示層間逼近關系.

圖2對應的層內連接關系由各個時間層網絡的鄰接矩陣確定, 即(14)式的對角線矩陣塊部分;不同時間層網絡的層間逼近關系則由各個節點的層間同構率, 即(12)式層間逼近關系系數計算得到.圖2的模型計算結果如下:

圖1 ISAM算法流程圖Fig.1.Algorithm flowchart of ISAM model.

圖2 基于層間同構率方法的時序網絡建模實例Fig.2.An example of ISAM model for temporal network.

3.3 基于時序網絡層間同構率的超鄰接矩陣模型構建

本文針對動態時序網絡的重要節點辨識問題提出了基于時序網絡層間同構率的超鄰接矩陣模型ISAM.該模型對經典SAM進行了改進, 考慮時序網絡節點隨時間演化時向量的矢量、標量變化,得到相鄰、跨層網絡間逼近關系; 結合每個時間層網絡鄰接矩陣, 最終得到時序網絡超鄰接矩陣模型.

圖3給出了ISAM模型的結構示意圖, 根據直接影響節點和間接影響節點把模型分成兩個模塊:相鄰模塊和跨層模塊.ISAM模型根據相鄰、跨層網絡中出現的新增關聯關系, 得到與其直接關聯、間接關聯的節點集合, 使用節點關聯關系動態更新對相鄰、跨層網絡中的節點進行節點表示更新, 然后通過相鄰、跨層網絡向量的矢量計算與標量計算, 得到了相鄰、跨層網絡間逼近關系系數; 結合整個時間段各個時間層網絡的鄰接矩陣, 最終得到超鄰接矩陣模型.

考慮到模型的一般性, 令相鄰時間層網絡的時間間隔為t, 則時序網絡在整個觀察期[t,t+S]內的ISAM模型具體如下:

其中,Z(t,t+t),Z(t+t,t+2t), ···表示相鄰時間層之間的逼近關系,Z(t,t+2t),Z(t+t,t+3t), ···表示非相鄰層之間的逼近關系, 如Z(t,t+kt)(k= 1, 2, ···,T– 1)表示時間層網絡Gt與時間層網絡Gt+kt之間的逼近關系;Z(t,t+kt)為N×N的對角矩陣, 即Z(t,t+kt)=diag (Z1(t,t+kt),Z2(t,t+kt), ···,ZN(t,t+kt)), 而Zi(t,t+kt)即為節點的層間逼近關系系數, 描述了節點i的層間同構率.

圖3 基于時序網絡層間同構率的超鄰接矩陣模型Fig.3.Super-adjacency matrix model based on inter-layer isomorphism rate in temporal networks.

4 基于時序網絡多屬性特征的超鄰接矩陣建模仿真與分析

4.1 時序網絡層間同構率特征動態演化分析

復雜網絡中評價節點重要性的方法有很多, 如經典的度中心性, 考慮節點所在位置的介數中心性, 將節點的位置和層級聯系在一起的K-核中心性等.考慮到時序網絡中節點與鄰居間持續關聯關系以及節點所在位置影響, 選取特征向量中心性作為本文的節點重要性排序方法.節點重要性不僅體現在節點在網絡中對信息的傳播能力, 也可體現在節點被移除后對網絡連通的破壞性, 時序全局效率的差值大小可以反映時序網絡的連通性變化.

4.1.1 特征向量中心性

Gershgorin圓盤定理[31]給出了矩陣特征值的估計方法, 本文構建的超鄰接矩陣A′是實對稱陣且對角線元素均為零, 矩陣所有特征值均在一個重合的圓盤內, 最大特征根及其特征向量幾乎包含了矩陣的所有特征.本文通過特征向量中心性對時序網絡的節點重要性進行評估, 求出超鄰接矩陣A′的主特征向量(最大特征值對應的特征向量)v= {v1,v2, ···,vNT}T.則向量v的第N(t–1)+i(t=1, 2, ···,T)項表示t時間層網絡上節點i的特征向量中心性, 記為N×T的矩陣W= {wit}N×T, 則

其中,wit為矩陣W的第i行第t列元素, 即為t時間層網絡上節點i的特征向量中心性.該指標不僅可以獲得各時間層網絡節點重要性的排序, 同時能夠反映節點在每個時間層網絡的重要性隨時間變化的軌跡.

表1列出了圖2中實例網絡的特征向量中心性指標的結果, 并與文獻[26]中改進的SSAM模型和文獻[25]中經典SAM模型參數w取0.5的特征向量中心性結果做對比.從表1可以得到各時間層節點的重要性排序及節點在每個時間層網絡的重要性隨時間變化的軌跡, 就本文方法 (b取0.5)結果來看, 第一時間層網絡G1中節點重要性排序為1–3–4–2, 且1號節點在3個時間層網絡的重要性排序隨時間變化軌跡為1–1–2.

經典SAM模型中使用共同參數w= 0.5來表示不同節點的層間連接關系, 忽略了節點的異質性, 強化孤立節點重要性程度的同時, 弱化了節點層間鄰居同構率高的節點的重要性程度.例如2號節點, 其在G1中為孤立節點, 特征向量中心性指標應接近于0, 而文獻[25]中的方法高估了G1中2號節點的重要性值; 對于G1中的1號節點, 其層內鄰接關系穩定, 雖然在上述方法中該節點均為網絡G1中最重要的節點, 但是在文獻[25]的方法里1號節點的特征向量中心性指標較小, 為0.2809, 文獻[26]中為0.3739, 而本文方法里1號節點的特征向量中心性指標最大, 為0.4119,說明SAM模型弱化了1號節點的重要性值, 且本文方法相比文獻[26]節點重要性值有所提升.

表1 實例網絡中節點的特征向量中心性Table 1.Eigenvector centrality of nodes in temporal network of Fig.2.

4.1.2 時序全局效率

網絡平均效率[32]表示網絡中所有節點對之間距離倒數之和的平均值, 它用來表示靜態網絡信息流通的平均難易程度.時序網絡中, 為描述刪除節點后網絡連通性變化情況, 我們引入時序全局效率[25], 其具體形式如下:

其中,dij為時序網絡中各節點之間的時序距離[33].時序距離指的是時序最短路徑, 和靜態網絡不同的是其需要遵從不同連邊的時間先后順序.例如, 信息從節點i經過節點k最終傳到節點j, 需要在時間維度上滿足先發生節點i到k之間的有效連接,再發生節點k到j之間的有效連接, 否則信息不能從節點i傳到j.

以圖2所示的時序網絡為例, 假設有信息從t= 1時的1號節點開始傳遞, 且在每個時間層網絡上只傳遞一步, 信息傳遞過程最終在t= 3時刻結束, 則整個過程的時序距離dij的結果如表2所列.

表2 圖2時序網絡中各節點之間的時序距離Table 2.Temporal distance of nodes in temporal network of Fig.2.

最后, 用刪除節點后單位時間時序全局效率與原時序全局效率的差值作為節點重要性的驗證方法.首先, 依次刪除各個時間層的節點后重新計算網絡的時序全局效率, 得到一個N×T的矩陣E= {eit}N×T; 其次, 與原時序全局效率e做差值,再除以等間距的時間窗t, 最終得到刪除節點后的單位時間內時序全局效率差值矩陣E′, 具體如下:

其中De=ei,t–e,t=S/T,E′i,t為刪除第t個時間層網絡上的第i個節點后單位時間時序網絡全局效率差值, 對應的值越大, 說明該被刪除節點越重要.

4.1.3 肯德爾系數

為了更直觀地檢驗本文方法的效果, 用肯德爾相關系數[34](Kendall’s)對特征向量中心性矩陣W和單位時間內時序全局效率差值矩陣E′進行相關性分析.Kendall’s被用來測量兩變量序列之間排序的相關性程度, 其取值范圍為[–1, 1], 該值越大, 兩序列相關性越強; 反之, 則兩序列相關性越弱.具體定義如下:

其中X= (x1,x2, ···,xn)T,Y= (y1,y2, ···,yn)T,X表示特征向量中心性矩陣W中第t列向量,Y表示單位時間內時序全局效率差值矩陣E′中對應的第t列向量(t= 1, 2, ···,T); sgn(z)為一個分段函數, 當z> 0時, sgn(z) = +1, 當z< 0時,sgn(z) = –1, 當z= 0時, sgn(z) = 0;n為每個時間層節點數目,1)/2, 其中,ui為X序列中第i個使得sgn(z) = 0的xi值的個數,vj為Y序列中第j個使得sgn(z) =0的yj值的個數.

4.2 時序網絡模型相關數據統計

為了驗證ISAM模型在時序網絡節點重要性排序中的有效性, 本文選擇兩個具有代表性的公開實證網絡數據集進行對比實驗, Workspace及Email-eu-core數據集的基本統計信息如表3所列.

表3 實證網絡數據基本統計信息Table 3.Basic statistical features of Workspace and Email-eu-core.

Workspace[35]為法國某公司通過移動射頻設備獲取的92位公司員工之間每天面對面交互產生的交互數據, 時間從2013年6月24日到2013年7月3日, 按天切分數據.Email-eu-core[36]為斯坦福大學大型網絡數據集中的核心電子郵件時序網絡數據, 986種匿名ID在歷時803天中產生的交互信息, 我們以30天為一個時間片段, 為縮減數據, 取其中360天的數據子集進行實驗仿真.

4.3 時序網絡模型數據仿真結果分析

基于Workspace及Email-eu-core公開實證網絡數據, 通過計算ISAM方法(取0.5)、SSAM方法和SAM方法的特征向量中心性矩陣與刪除節點法的單位時序全局效率差值矩陣得到相應時間層的Kendall’s值如圖4所示(其中SAM方法的參數取[0.1, 0.2, ···, 1.0]).圖4中橫坐標表示時序網絡切分的各個時間層, 縱坐標表示相應時間層對應的Kendall’s值.

由圖4中的結果可以看到: 1) 對Workspace及Email-eu-core數據集的時序網絡構建中, SAM方法使用固定參數表示層間同構率, 在不同的參數下得到的Kendall’s結果大多相近, 說明參數的改變對于節點的特征向量中心性在各個時間層的排序結果影響并不顯著, 可以考慮用層內連接關系的動態演化來表示層間連接關系的變化; 2) ISAM方法得到的Kendall’s結果大部分高于SAM方法, 在Email-eu-core數據的結果中更明顯, 說明基于層間同構率的ISAM方法考慮了時序網絡不同節點的差異性, 能更準確地描述時序網絡的動態演化過程, 得到的節點重要性排序也更可靠; 3) 從不同網絡大小的公開實證數據的結果來看, ISAM方法比SAM方法的Kendall’s值在各個時間層平均提高, 最高為8.37%和2.99%, 但也存在個別層, 如Workspace數據的t= 6和t= 7上, ISAM方法的計算結果劣于SAM方法, 我們認為此結果是由于實際數據本身的影響造成的; 4) ISAM方法和SSAM方法的Kendall’s值在各個時間層差異不大, 說明了時序網絡中相鄰層間連接的貢獻度占整個網絡層間連接的貢獻度最高.

圖4 特征向量中心性與單位時間時序全局效率差值的Kendall’s 結果.藍色菱形為ISAM方法, 紅色小正方形為SSAM方法, 其他為SAM方法取不同參數的結果 (a) Workspace數據基于層間同構率的超鄰接矩陣方法和SSAM及經典超鄰接矩陣方法不同參數的Kendall’s 結果; (b) Emaileu-core數據相應的結果Fig.4.Results of Kendall’s for eigenvector centrality and difference of temporal global efficien- cy.The blue diamond is the ISAM method, the red square is the SSAM method,and the others are the results of the SAM method with different parameters: (a) Result for Workspace by ISAM,SSAM and SAM method; (b) result for Email-eu-core by ISAM, SSAM and SAM method.

圖5 給出ISAM方法不同偏好系數(取[0.1,0.2, ···, 1])下相對SAM方法在各時間層網絡Kendall’s值的平均提高值變化情況.

從圖5結果可以看出: Workspace及Emaileu-core數據的實驗結果表明, 在不同網絡規模下,偏好系數影響不同時間層網絡間同構率的大小,從而間接影響著不同節點的重要性辨識.當偏好系數從0.1變化到1時, ISAM方法不同偏好系數下相對SAM方法的Kendall’st值平均提高值在逐漸降低, 說明在時序演化過程中, 節點鄰居數量對層間同構率的影響小于節點鄰居質量的影響,Workspace數據中有個別時間層出現相反情況, 我們認為這是實際數據本身的影響造成的.

圖5 ISAM方法不同偏好系數下相對SAM方法的Kendall’s值平均提高結果 (a) Workspace數據相應的結果;(b) Email-eu-core數據相應的結果Fig.5.Results of average increase of Kendall’s for ISAM method under different preference coe- fficients compared with SAM method: (a) Result for Workspace; (b) result for Email-eu-core.

5 結 論

動態時序網絡中的重要節點辨識既是熱點話題, 也是難點問題.本文針對時序網絡的演化建模,提取時序網絡層內連接關系和層間逼近關系對網絡重要節點辨識綜合貢獻率大小, 給出基于節點層間同構率的時序網絡超鄰接矩陣建模方法.該模型描述了直接相鄰、跨層及間接相鄰、跨層網絡節點間關聯關系隨時間演化的綜合逼近關系, 用特征向量中心性作為度量網絡節點重要性的辨識工具, 用節點刪除法, 推演計算刪除節點前后單位時間時序網絡全局效率差值, 結合矢量與標量計算, 來評測本文ISAM方法對節點重要性排序.基于Workspace及Email-eu-core兩組數據的仿真結果, 本文ISAM方法得到的Kendall’st值較SAM方法在各時間層上平均提高, 最高為8.37%和2.99%.該方法有效降低網絡層間耦合參數討論的復雜度, 增強動態時序網絡節點重要性辨識綜合水平.

本文基于層間同構率的ISAM方法在進行時序網絡切分時是用等間距的時間窗大小, 而在現實時序網絡中, 節點間的交互強度往往不是按時間均勻分布的, 如何動態選取合適的時間窗大小是亟待解決的問題.未來將使用規模更大的公開實證網絡數據集, 對時序網絡不同頻率交互下多級跨層重要節點辨識進行偏好信息集結, 以便更加深刻地描述時序網絡重要節點、區塊的演化規律.