基于時(shí)序網(wǎng)絡(luò)層間同構(gòu)率動(dòng)態(tài)演化的重要節(jié)點(diǎn)辨識(shí)*

胡鋼 許麗鵬 徐翔

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

2) (國(guó)防科技大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室, 長(zhǎng)沙 410073)

時(shí)序網(wǎng)絡(luò)可以更加準(zhǔn)確地描述網(wǎng)絡(luò)節(jié)點(diǎn)在時(shí)空演化過(guò)程中的交互順序變化和交互關(guān)聯(lián)關(guān)系.為辨識(shí)時(shí)序網(wǎng)絡(luò)中的重要節(jié)點(diǎn), 本文提出基于時(shí)序網(wǎng)絡(luò)層間同構(gòu)率動(dòng)態(tài)演化的超鄰接矩陣建模的重要節(jié)點(diǎn)辨識(shí)方法.首先, 依托復(fù)雜網(wǎng)絡(luò)的層間時(shí)序關(guān)聯(lián)耦合關(guān)系, 定義了相鄰與跨層網(wǎng)絡(luò)綜合逼近關(guān)系系數(shù).其次, 依據(jù)層內(nèi)連接關(guān)系和層間逼近關(guān)系構(gòu)建時(shí)序網(wǎng)絡(luò)超鄰接矩陣.再次, 使用特征向量中心性方法對(duì)時(shí)序網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性排序, 分析計(jì)算時(shí)序全局效率差值, 通過(guò)肯德?tīng)栂嚓P(guān)系數(shù)驗(yàn)證.最后, 實(shí)證數(shù)據(jù)仿真顯示: 與經(jīng)典時(shí)序網(wǎng)絡(luò)模型相比, 本文模型所得Kendall’s t值在各時(shí)間層上平均提高, 最高為8.37%和2.99%, 結(jié)論表明時(shí)序網(wǎng)絡(luò)層間同構(gòu)率的度量方法科學(xué)有效.

1 引 言

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

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

上述方法僅僅考慮時(shí)序網(wǎng)絡(luò)各節(jié)點(diǎn)在每個(gè)時(shí)間切片上的連接關(guān)系, 為完整地表示時(shí)序網(wǎng)絡(luò)的動(dòng)力學(xué)過(guò)程和結(jié)構(gòu)演變特征, 還需要考慮時(shí)序網(wǎng)絡(luò)各節(jié)點(diǎn)在不同時(shí)間切片間的連接關(guān)系.郭強(qiáng)等[23]基于TOPSIS多屬性排序方法得出使用優(yōu)先鏈接指標(biāo)(PA)度量挖掘出的重要節(jié)點(diǎn)最準(zhǔn)確.邱路和黃國(guó)妍[24]提出時(shí)變狀態(tài)網(wǎng)絡(luò)模型, 分析不同時(shí)間狀態(tài)網(wǎng)絡(luò)的連接相似性.Taylor等[25]考慮用多層耦合網(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方法忽略了復(fù)雜網(wǎng)絡(luò)中不同節(jié)點(diǎn)層間連接關(guān)系的差異性, 楊劍楠等[26]將節(jié)點(diǎn)的層間連接關(guān)系用鄰居拓?fù)渲丿B系數(shù)表示, 提出了基于節(jié)點(diǎn)層間相似性的超鄰接矩 陣(similarity-based supra-adjacency matrix,SSAM)時(shí)序網(wǎng)絡(luò)構(gòu)建方法.朱義鑫等[27]針對(duì)相關(guān)系數(shù)的改進(jìn)問(wèn)題, 給出一個(gè)網(wǎng)絡(luò)演化速度指標(biāo); 同時(shí), 提出了一個(gè)具有非馬爾可夫性質(zhì)的時(shí)序網(wǎng)絡(luò)演化模型.但也只是表達(dá)相鄰網(wǎng)絡(luò)間的耦合關(guān)系, 基于此, 我們考慮了跨層網(wǎng)絡(luò)間的相容相似度, 并結(jié)合向量在n維實(shí)數(shù)空間上的投影值以及節(jié)點(diǎn)鄰居的貢獻(xiàn)值提出了時(shí)序網(wǎng)絡(luò)層間逼近關(guān)系系數(shù), 實(shí)現(xiàn)了信息的矢量計(jì)算和標(biāo)量計(jì)算, 通過(guò)信息的集結(jié)彌補(bǔ)了鄰居拓?fù)渲丿B系數(shù)的不足, 最后構(gòu)建了改進(jìn)的基于時(shí)序網(wǎng)絡(luò)層間同構(gòu)率動(dòng)態(tài)演化的超鄰接矩陣模型(isomorphism rate based supra-adjacency matrix, ISAM).Workspace及Email-eu-core數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示, 本文方法得到的Kendall’st值較SAM方法在各時(shí)間層上平均提高, 最高為8.37%和2.99%.且本文方法在算法復(fù)雜度上和SAM一樣, 均為o(n2) , 說(shuō)明本文方法能更準(zhǔn)確地辨識(shí)時(shí)序網(wǎng)絡(luò)中的重要節(jié)點(diǎn), 為時(shí)序網(wǎng)絡(luò)建模提供了一種新的思路.

2 時(shí)序網(wǎng)絡(luò)相關(guān)概念

基于目前研究的復(fù)雜網(wǎng)絡(luò)相關(guān)方法, 本文綜述了時(shí)序網(wǎng)絡(luò)定義; 同時(shí), 為了時(shí)序網(wǎng)絡(luò)表征研究更近一步的推廣, 給出了時(shí)序網(wǎng)絡(luò)向量范數(shù)、時(shí)序網(wǎng)絡(luò)相容相似度系數(shù)、時(shí)序網(wǎng)絡(luò)向量投影值、時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)資源分配相似度系數(shù)以及時(shí)序網(wǎng)絡(luò)層間逼近關(guān)系系數(shù)等定義.

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

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

2.2 時(shí)序網(wǎng)絡(luò)層間逼近關(guān)系系數(shù)分析

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

1) ||ai|| ≥ 0, 其中||ai|| = 0當(dāng)且僅當(dāng)ai= 0;

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

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

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

當(dāng)p→∞, 定義∞–范數(shù):

定義2時(shí)序相鄰網(wǎng)絡(luò)相容相似度系數(shù).考慮到時(shí)序相鄰網(wǎng)絡(luò)層上節(jié)點(diǎn)自身鄰居的影響[23], 即兩個(gè)節(jié)點(diǎn)的共同鄰居越多, 兩節(jié)點(diǎn)越相似.我們用Salton指標(biāo)(Salton index, SAL)[29]定義相鄰網(wǎng)絡(luò)相容相似度系數(shù), 具體形式如下:

相鄰網(wǎng)絡(luò)相容相似度系數(shù)描述了節(jié)點(diǎn)鄰居關(guān)系以及節(jié)點(diǎn)間持續(xù)關(guān)聯(lián)的層間同構(gòu)率.其中aij(t),aij(t+ 1)對(duì)應(yīng)相鄰時(shí)間層網(wǎng)絡(luò)Gt,Gt+1的鄰接矩陣元素.如果在任一時(shí)間層網(wǎng)絡(luò)Gt中節(jié)點(diǎn)i與節(jié)點(diǎn)j之間存在連邊, 則aij(t) = 1; 否則aij(t) = 0.此外, 向量ai在相鄰時(shí)刻t,t+ 1均為零向量(孤立節(jié)點(diǎn))時(shí), 規(guī)定僅有一個(gè)時(shí)刻為零向量時(shí), 規(guī)定

定義3時(shí)序跨層網(wǎng)絡(luò)相容相似度系數(shù).時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)間的連邊隨時(shí)間動(dòng)態(tài)增刪, 僅僅考慮相鄰網(wǎng)絡(luò)間的同構(gòu)率可能無(wú)法準(zhǔn)確辨識(shí)時(shí)序網(wǎng)絡(luò)的重要節(jié)點(diǎn).基于此, 我們提出了時(shí)序跨層網(wǎng)絡(luò)相容相似度系數(shù).

例如, 跨一層網(wǎng)絡(luò)相容相似度系數(shù)

跨兩層網(wǎng)絡(luò)相容相似度系數(shù)

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

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

(i) 時(shí)序相鄰網(wǎng)絡(luò)向量投影值(m= 1)

(ii) 時(shí)序跨層網(wǎng)絡(luò)向量投影值(m> 1)

對(duì)于跨層網(wǎng)絡(luò)向量投影值, 我們通過(guò)兩兩比較相鄰層網(wǎng)絡(luò)向量, 根據(jù)(7)式求出所有相鄰層網(wǎng)絡(luò)的投影值的平均值, 再計(jì)算投影值的標(biāo)準(zhǔn)差s,定義為跨層網(wǎng)絡(luò)向量投影值其中參數(shù)保證該投影值越大, 表示向量ai在時(shí)間段[t,t+m](m> 1)的方向一致性越高, 反映節(jié)點(diǎn)在時(shí)序演化過(guò)程中越穩(wěn)定.

定義5時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)資源分配相似度系數(shù).靜態(tài)網(wǎng)絡(luò)中資源分配指標(biāo)(resource allocation,RA)[30]的思想是: 如果網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)沒(méi)有直接相連, 可以將它們的共同鄰居作為傳遞的媒介.基于此, 我們提出了時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)資源分配相似度系數(shù), 具體如下:

(i) 時(shí)序相鄰網(wǎng)絡(luò)節(jié)點(diǎn)資源分配相似度系數(shù)

(ii) 時(shí)序跨層網(wǎng)絡(luò)節(jié)點(diǎn)資源分配相似度系數(shù)

例如, 跨一層網(wǎng)絡(luò)節(jié)點(diǎn)資源分配相似度系數(shù):Γ(it)∩Γ(it+1)

其中 表示節(jié)點(diǎn)i在相鄰時(shí)間層的共同鄰居,d(z)表示共同鄰居節(jié)點(diǎn)的度值.該系數(shù)反映了節(jié)點(diǎn)間的相似性不僅和共同鄰居的數(shù)量有關(guān),還和鄰居節(jié)點(diǎn)的質(zhì)量(度值)有關(guān).節(jié)點(diǎn)共同鄰居的數(shù)量越多、鄰居節(jié)點(diǎn)的度值越小, 則時(shí)序相鄰網(wǎng)絡(luò)節(jié)點(diǎn)資源分配相似度系數(shù)越大.

定義6時(shí)序網(wǎng)絡(luò)層間逼近關(guān)系系數(shù).綜合考慮兩時(shí)間層網(wǎng)絡(luò)相容相似度變化(標(biāo)量變化)、向量間的投影值變化(矢量變化)以及節(jié)點(diǎn)資源分配情況, 我們提出時(shí)序網(wǎng)絡(luò)層間逼近關(guān)系系數(shù)Z,Z=表示節(jié)點(diǎn)i在兩時(shí)間層網(wǎng)絡(luò)的同構(gòu)率, 具體形式如下:

3 時(shí)序網(wǎng)絡(luò)超鄰接矩陣系統(tǒng)模型構(gòu)建

經(jīng)典時(shí)序網(wǎng)絡(luò)建模時(shí)考慮用多層耦合網(wǎng)絡(luò)分析的方法, 將時(shí)序網(wǎng)絡(luò)按層間關(guān)系和層內(nèi)關(guān)系建立超鄰接矩陣, 但在表示不同時(shí)間層網(wǎng)絡(luò)間關(guān)系中使用了相同的參數(shù), 忽略了復(fù)雜網(wǎng)絡(luò)中不同節(jié)點(diǎn)層間連接關(guān)系的差異性.為此, 我們提出了改進(jìn)時(shí)序網(wǎng)絡(luò)建模方法, 在經(jīng)典SAM模型的基礎(chǔ)上, 給出時(shí)序網(wǎng)絡(luò)層間逼近關(guān)系系數(shù), 并提出改進(jìn)的ISAM模型.

3.1 經(jīng)典時(shí)序網(wǎng)絡(luò)建模思想

文獻(xiàn)[25]將時(shí)序網(wǎng)絡(luò)通過(guò)層內(nèi)連接關(guān)系和層間耦合關(guān)系來(lái)表示, 提出了經(jīng)典的SAM時(shí)序網(wǎng)絡(luò)模型, SAM為NT×NT的分塊矩陣, 為構(gòu)建時(shí)序網(wǎng)絡(luò)提供了一種新思路.我們把有序時(shí)間層網(wǎng)絡(luò)集合定義為G= {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)的鄰接矩陣表示,依次位于超鄰接矩陣A的對(duì)角線上, 表示有序的時(shí)間層網(wǎng)絡(luò): 定義aij(t)為鄰接矩陣A(t)中的元素,則aij(t) = 1表示在時(shí)間層網(wǎng)絡(luò)Gt中節(jié)點(diǎn)i與節(jié)點(diǎn)j間有連邊,aij(t) = 0表示無(wú)連邊;wI表示相鄰層網(wǎng)絡(luò)層間耦合關(guān)系, 其中為可調(diào)參數(shù), 在lim時(shí), 層變得不耦合; 在lim時(shí), 層之間的耦合非常強(qiáng),I為N×N單位矩陣.由于經(jīng)典的SAM時(shí)序網(wǎng)絡(luò)模型中僅考慮層的最近鄰耦合關(guān)系, 所以超鄰接矩陣A其他部分均用0表示.

3.2 改進(jìn)時(shí)序網(wǎng)絡(luò)建模分析

經(jīng)典的SAM時(shí)序網(wǎng)絡(luò)模型中, 相鄰層間關(guān)系用同一參數(shù)w來(lái)表示, 忽略了異質(zhì)網(wǎng)絡(luò)中不同節(jié)點(diǎn)的差異性, 為了更真實(shí)地反映相鄰時(shí)間層網(wǎng)絡(luò)連接的實(shí)際情況, 本文對(duì)SAM模型中的相鄰層間關(guān)系做出改進(jìn), 并考慮了非相鄰層間耦合關(guān)系.

時(shí)序網(wǎng)絡(luò)相鄰層間關(guān)系和節(jié)點(diǎn)在相鄰網(wǎng)絡(luò)間的連接關(guān)系與其在相鄰層上的持續(xù)出現(xiàn)度及節(jié)點(diǎn)的鄰居關(guān)系層間相似程度有關(guān)[26], 考慮時(shí)序演化過(guò)程中節(jié)點(diǎn)鄰居的數(shù)量和質(zhì)量變化, 我們提出時(shí)序網(wǎng)絡(luò)層間逼近關(guān)系系數(shù)Z.改進(jìn)的基于層間同構(gòu)率的ISAM時(shí)序網(wǎng)絡(luò)模型具體表示形式如下:

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

圖2給出了一個(gè)包含3個(gè)時(shí)間層和4個(gè)節(jié)點(diǎn)的時(shí)序網(wǎng)絡(luò)及ISAM模型的構(gòu)建, 其中黑色實(shí)線表示層內(nèi)連接關(guān)系, 黑色虛線表示層間逼近關(guān)系.

圖2對(duì)應(yīng)的層內(nèi)連接關(guān)系由各個(gè)時(shí)間層網(wǎng)絡(luò)的鄰接矩陣確定, 即(14)式的對(duì)角線矩陣塊部分;不同時(shí)間層網(wǎng)絡(luò)的層間逼近關(guān)系則由各個(gè)節(jié)點(diǎn)的層間同構(gòu)率, 即(12)式層間逼近關(guān)系系數(shù)計(jì)算得到.圖2的模型計(jì)算結(jié)果如下:

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

圖2 基于層間同構(gòu)率方法的時(shí)序網(wǎng)絡(luò)建模實(shí)例Fig.2.An example of ISAM model for temporal network.

3.3 基于時(shí)序網(wǎng)絡(luò)層間同構(gòu)率的超鄰接矩陣模型構(gòu)建

本文針對(duì)動(dòng)態(tài)時(shí)序網(wǎng)絡(luò)的重要節(jié)點(diǎn)辨識(shí)問(wèn)題提出了基于時(shí)序網(wǎng)絡(luò)層間同構(gòu)率的超鄰接矩陣模型ISAM.該模型對(duì)經(jīng)典SAM進(jìn)行了改進(jìn), 考慮時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)隨時(shí)間演化時(shí)向量的矢量、標(biāo)量變化,得到相鄰、跨層網(wǎng)絡(luò)間逼近關(guān)系; 結(jié)合每個(gè)時(shí)間層網(wǎng)絡(luò)鄰接矩陣, 最終得到時(shí)序網(wǎng)絡(luò)超鄰接矩陣模型.

圖3給出了ISAM模型的結(jié)構(gòu)示意圖, 根據(jù)直接影響節(jié)點(diǎn)和間接影響節(jié)點(diǎn)把模型分成兩個(gè)模塊:相鄰模塊和跨層模塊.ISAM模型根據(jù)相鄰、跨層網(wǎng)絡(luò)中出現(xiàn)的新增關(guān)聯(lián)關(guān)系, 得到與其直接關(guān)聯(lián)、間接關(guān)聯(lián)的節(jié)點(diǎn)集合, 使用節(jié)點(diǎn)關(guān)聯(lián)關(guān)系動(dòng)態(tài)更新對(duì)相鄰、跨層網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行節(jié)點(diǎn)表示更新, 然后通過(guò)相鄰、跨層網(wǎng)絡(luò)向量的矢量計(jì)算與標(biāo)量計(jì)算, 得到了相鄰、跨層網(wǎng)絡(luò)間逼近關(guān)系系數(shù); 結(jié)合整個(gè)時(shí)間段各個(gè)時(shí)間層網(wǎng)絡(luò)的鄰接矩陣, 最終得到超鄰接矩陣模型.

考慮到模型的一般性, 令相鄰時(shí)間層網(wǎng)絡(luò)的時(shí)間間隔為t, 則時(shí)序網(wǎng)絡(luò)在整個(gè)觀察期[t,t+S]內(nèi)的ISAM模型具體如下:

其中,Z(t,t+t),Z(t+t,t+2t), ···表示相鄰時(shí)間層之間的逼近關(guān)系,Z(t,t+2t),Z(t+t,t+3t), ···表示非相鄰層之間的逼近關(guān)系, 如Z(t,t+kt)(k= 1, 2, ···,T– 1)表示時(shí)間層網(wǎng)絡(luò)Gt與時(shí)間層網(wǎng)絡(luò)Gt+kt之間的逼近關(guān)系;Z(t,t+kt)為N×N的對(duì)角矩陣, 即Z(t,t+kt)=diag (Z1(t,t+kt),Z2(t,t+kt), ···,ZN(t,t+kt)), 而Zi(t,t+kt)即為節(jié)點(diǎn)的層間逼近關(guān)系系數(shù), 描述了節(jié)點(diǎn)i的層間同構(gòu)率.

圖3 基于時(shí)序網(wǎng)絡(luò)層間同構(gòu)率的超鄰接矩陣模型Fig.3.Super-adjacency matrix model based on inter-layer isomorphism rate in temporal networks.

4 基于時(shí)序網(wǎng)絡(luò)多屬性特征的超鄰接矩陣建模仿真與分析

4.1 時(shí)序網(wǎng)絡(luò)層間同構(gòu)率特征動(dòng)態(tài)演化分析

復(fù)雜網(wǎng)絡(luò)中評(píng)價(jià)節(jié)點(diǎn)重要性的方法有很多, 如經(jīng)典的度中心性, 考慮節(jié)點(diǎn)所在位置的介數(shù)中心性, 將節(jié)點(diǎn)的位置和層級(jí)聯(lián)系在一起的K-核中心性等.考慮到時(shí)序網(wǎng)絡(luò)中節(jié)點(diǎn)與鄰居間持續(xù)關(guān)聯(lián)關(guān)系以及節(jié)點(diǎn)所在位置影響, 選取特征向量中心性作為本文的節(jié)點(diǎn)重要性排序方法.節(jié)點(diǎn)重要性不僅體現(xiàn)在節(jié)點(diǎn)在網(wǎng)絡(luò)中對(duì)信息的傳播能力, 也可體現(xiàn)在節(jié)點(diǎn)被移除后對(duì)網(wǎng)絡(luò)連通的破壞性, 時(shí)序全局效率的差值大小可以反映時(shí)序網(wǎng)絡(luò)的連通性變化.

4.1.1 特征向量中心性

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

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

表1列出了圖2中實(shí)例網(wǎng)絡(luò)的特征向量中心性指標(biāo)的結(jié)果, 并與文獻(xiàn)[26]中改進(jìn)的SSAM模型和文獻(xiàn)[25]中經(jīng)典SAM模型參數(shù)w取0.5的特征向量中心性結(jié)果做對(duì)比.從表1可以得到各時(shí)間層節(jié)點(diǎn)的重要性排序及節(jié)點(diǎn)在每個(gè)時(shí)間層網(wǎng)絡(luò)的重要性隨時(shí)間變化的軌跡, 就本文方法 (b取0.5)結(jié)果來(lái)看, 第一時(shí)間層網(wǎng)絡(luò)G1中節(jié)點(diǎn)重要性排序?yàn)?–3–4–2, 且1號(hào)節(jié)點(diǎn)在3個(gè)時(shí)間層網(wǎng)絡(luò)的重要性排序隨時(shí)間變化軌跡為1–1–2.

經(jīng)典SAM模型中使用共同參數(shù)w= 0.5來(lái)表示不同節(jié)點(diǎn)的層間連接關(guān)系, 忽略了節(jié)點(diǎn)的異質(zhì)性, 強(qiáng)化孤立節(jié)點(diǎn)重要性程度的同時(shí), 弱化了節(jié)點(diǎn)層間鄰居同構(gòu)率高的節(jié)點(diǎn)的重要性程度.例如2號(hào)節(jié)點(diǎn), 其在G1中為孤立節(jié)點(diǎn), 特征向量中心性指標(biāo)應(yīng)接近于0, 而文獻(xiàn)[25]中的方法高估了G1中2號(hào)節(jié)點(diǎn)的重要性值; 對(duì)于G1中的1號(hào)節(jié)點(diǎn), 其層內(nèi)鄰接關(guān)系穩(wěn)定, 雖然在上述方法中該節(jié)點(diǎn)均為網(wǎng)絡(luò)G1中最重要的節(jié)點(diǎn), 但是在文獻(xiàn)[25]的方法里1號(hào)節(jié)點(diǎn)的特征向量中心性指標(biāo)較小, 為0.2809, 文獻(xiàn)[26]中為0.3739, 而本文方法里1號(hào)節(jié)點(diǎn)的特征向量中心性指標(biāo)最大, 為0.4119,說(shuō)明SAM模型弱化了1號(hào)節(jié)點(diǎn)的重要性值, 且本文方法相比文獻(xiàn)[26]節(jié)點(diǎn)重要性值有所提升.

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

4.1.2 時(shí)序全局效率

網(wǎng)絡(luò)平均效率[32]表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間距離倒數(shù)之和的平均值, 它用來(lái)表示靜態(tài)網(wǎng)絡(luò)信息流通的平均難易程度.時(shí)序網(wǎng)絡(luò)中, 為描述刪除節(jié)點(diǎn)后網(wǎng)絡(luò)連通性變化情況, 我們引入時(shí)序全局效率[25], 其具體形式如下:

其中,dij為時(shí)序網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的時(shí)序距離[33].時(shí)序距離指的是時(shí)序最短路徑, 和靜態(tài)網(wǎng)絡(luò)不同的是其需要遵從不同連邊的時(shí)間先后順序.例如, 信息從節(jié)點(diǎn)i經(jīng)過(guò)節(jié)點(diǎn)k最終傳到節(jié)點(diǎn)j, 需要在時(shí)間維度上滿足先發(fā)生節(jié)點(diǎn)i到k之間的有效連接,再發(fā)生節(jié)點(diǎn)k到j(luò)之間的有效連接, 否則信息不能從節(jié)點(diǎn)i傳到j(luò).

以圖2所示的時(shí)序網(wǎng)絡(luò)為例, 假設(shè)有信息從t= 1時(shí)的1號(hào)節(jié)點(diǎn)開(kāi)始傳遞, 且在每個(gè)時(shí)間層網(wǎng)絡(luò)上只傳遞一步, 信息傳遞過(guò)程最終在t= 3時(shí)刻結(jié)束, 則整個(gè)過(guò)程的時(shí)序距離dij的結(jié)果如表2所列.

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

最后, 用刪除節(jié)點(diǎn)后單位時(shí)間時(shí)序全局效率與原時(shí)序全局效率的差值作為節(jié)點(diǎn)重要性的驗(yàn)證方法.首先, 依次刪除各個(gè)時(shí)間層的節(jié)點(diǎn)后重新計(jì)算網(wǎng)絡(luò)的時(shí)序全局效率, 得到一個(gè)N×T的矩陣E= {eit}N×T; 其次, 與原時(shí)序全局效率e做差值,再除以等間距的時(shí)間窗t, 最終得到刪除節(jié)點(diǎn)后的單位時(shí)間內(nèi)時(shí)序全局效率差值矩陣E′, 具體如下:

其中De=ei,t–e,t=S/T,E′i,t為刪除第t個(gè)時(shí)間層網(wǎng)絡(luò)上的第i個(gè)節(jié)點(diǎn)后單位時(shí)間時(shí)序網(wǎng)絡(luò)全局效率差值, 對(duì)應(yīng)的值越大, 說(shuō)明該被刪除節(jié)點(diǎn)越重要.

4.1.3 肯德?tīng)栂禂?shù)

為了更直觀地檢驗(yàn)本文方法的效果, 用肯德?tīng)栂嚓P(guān)系數(shù)[34](Kendall’s)對(duì)特征向量中心性矩陣W和單位時(shí)間內(nèi)時(shí)序全局效率差值矩陣E′進(jìn)行相關(guān)性分析.Kendall’s被用來(lái)測(cè)量?jī)勺兞啃蛄兄g排序的相關(guān)性程度, 其取值范圍為[–1, 1], 該值越大, 兩序列相關(guān)性越強(qiáng); 反之, 則兩序列相關(guān)性越弱.具體定義如下:

其中X= (x1,x2, ···,xn)T,Y= (y1,y2, ···,yn)T,X表示特征向量中心性矩陣W中第t列向量,Y表示單位時(shí)間內(nèi)時(shí)序全局效率差值矩陣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為每個(gè)時(shí)間層節(jié)點(diǎn)數(shù)目,1)/2, 其中,ui為X序列中第i個(gè)使得sgn(z) = 0的xi值的個(gè)數(shù),vj為Y序列中第j個(gè)使得sgn(z) =0的yj值的個(gè)數(shù).

4.2 時(shí)序網(wǎng)絡(luò)模型相關(guān)數(shù)據(jù)統(tǒng)計(jì)

為了驗(yàn)證ISAM模型在時(shí)序網(wǎng)絡(luò)節(jié)點(diǎn)重要性排序中的有效性, 本文選擇兩個(gè)具有代表性的公開(kāi)實(shí)證網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn), Workspace及Email-eu-core數(shù)據(jù)集的基本統(tǒng)計(jì)信息如表3所列.

表3 實(shí)證網(wǎng)絡(luò)數(shù)據(jù)基本統(tǒng)計(jì)信息Table 3.Basic statistical features of Workspace and Email-eu-core.

Workspace[35]為法國(guó)某公司通過(guò)移動(dòng)射頻設(shè)備獲取的92位公司員工之間每天面對(duì)面交互產(chǎn)生的交互數(shù)據(jù), 時(shí)間從2013年6月24日到2013年7月3日, 按天切分?jǐn)?shù)據(jù).Email-eu-core[36]為斯坦福大學(xué)大型網(wǎng)絡(luò)數(shù)據(jù)集中的核心電子郵件時(shí)序網(wǎng)絡(luò)數(shù)據(jù), 986種匿名ID在歷時(shí)803天中產(chǎn)生的交互信息, 我們以30天為一個(gè)時(shí)間片段, 為縮減數(shù)據(jù), 取其中360天的數(shù)據(jù)子集進(jìn)行實(shí)驗(yàn)仿真.

4.3 時(shí)序網(wǎng)絡(luò)模型數(shù)據(jù)仿真結(jié)果分析

基于Workspace及Email-eu-core公開(kāi)實(shí)證網(wǎng)絡(luò)數(shù)據(jù), 通過(guò)計(jì)算ISAM方法(取0.5)、SSAM方法和SAM方法的特征向量中心性矩陣與刪除節(jié)點(diǎn)法的單位時(shí)序全局效率差值矩陣得到相應(yīng)時(shí)間層的Kendall’s值如圖4所示(其中SAM方法的參數(shù)取[0.1, 0.2, ···, 1.0]).圖4中橫坐標(biāo)表示時(shí)序網(wǎng)絡(luò)切分的各個(gè)時(shí)間層, 縱坐標(biāo)表示相應(yīng)時(shí)間層對(duì)應(yīng)的Kendall’s值.

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

圖4 特征向量中心性與單位時(shí)間時(shí)序全局效率差值的Kendall’s 結(jié)果.藍(lán)色菱形為ISAM方法, 紅色小正方形為SSAM方法, 其他為SAM方法取不同參數(shù)的結(jié)果 (a) Workspace數(shù)據(jù)基于層間同構(gòu)率的超鄰接矩陣方法和SSAM及經(jīng)典超鄰接矩陣方法不同參數(shù)的Kendall’s 結(jié)果; (b) Emaileu-core數(shù)據(jù)相應(yīng)的結(jié)果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方法不同偏好系數(shù)(取[0.1,0.2, ···, 1])下相對(duì)SAM方法在各時(shí)間層網(wǎng)絡(luò)Kendall’s值的平均提高值變化情況.

從圖5結(jié)果可以看出: Workspace及Emaileu-core數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明, 在不同網(wǎng)絡(luò)規(guī)模下,偏好系數(shù)影響不同時(shí)間層網(wǎng)絡(luò)間同構(gòu)率的大小,從而間接影響著不同節(jié)點(diǎn)的重要性辨識(shí).當(dāng)偏好系數(shù)從0.1變化到1時(shí), ISAM方法不同偏好系數(shù)下相對(duì)SAM方法的Kendall’st值平均提高值在逐漸降低, 說(shuō)明在時(shí)序演化過(guò)程中, 節(jié)點(diǎn)鄰居數(shù)量對(duì)層間同構(gòu)率的影響小于節(jié)點(diǎn)鄰居質(zhì)量的影響,Workspace數(shù)據(jù)中有個(gè)別時(shí)間層出現(xiàn)相反情況, 我們認(rèn)為這是實(shí)際數(shù)據(jù)本身的影響造成的.

圖5 ISAM方法不同偏好系數(shù)下相對(duì)SAM方法的Kendall’s值平均提高結(jié)果 (a) Workspace數(shù)據(jù)相應(yīng)的結(jié)果;(b) Email-eu-core數(shù)據(jù)相應(yīng)的結(jié)果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 結(jié) 論

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

本文基于層間同構(gòu)率的ISAM方法在進(jìn)行時(shí)序網(wǎng)絡(luò)切分時(shí)是用等間距的時(shí)間窗大小, 而在現(xiàn)實(shí)時(shí)序網(wǎng)絡(luò)中, 節(jié)點(diǎn)間的交互強(qiáng)度往往不是按時(shí)間均勻分布的, 如何動(dòng)態(tài)選取合適的時(shí)間窗大小是亟待解決的問(wèn)題.未來(lái)將使用規(guī)模更大的公開(kāi)實(shí)證網(wǎng)絡(luò)數(shù)據(jù)集, 對(duì)時(shí)序網(wǎng)絡(luò)不同頻率交互下多級(jí)跨層重要節(jié)點(diǎn)辨識(shí)進(jìn)行偏好信息集結(jié), 以便更加深刻地描述時(shí)序網(wǎng)絡(luò)重要節(jié)點(diǎn)、區(qū)塊的演化規(guī)律.