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’s τ值较SAM方法在各时间层上平均提高, 最高为8.37%和2.99%. 且本文方法在算法复杂度上和SAM一样, 均为$o({n^2})$, 说明本文方法能更准确地辨识时序网络中的重要节点, 为时序网络建模提供了一种新的思路.

2.   时序网络相关概念

基于目前研究的复杂网络相关方法, 本文综述了时序网络定义; 同时, 为了时序网络表征研究更近一步的推广, 给出了时序网络向量范数、时序网络相容相似度系数、时序网络向量投影值、时序网络节点资源分配相似度系数以及时序网络层间逼近关系系数等定义.

2.1   时序网络定义

网络科学将复杂系统抽象为复杂网络, 动态时序网络是一个包含了个体、个体间交互作用及时间轴的复杂系统. 我们将个体视为节点, 则个体间的交互作用形成了节点间的连边, 边与边之间的交互作用形成了网络分块, 块与块的相互影响构成了整个复杂网络. 当节点间的关联关系随时间演化呈现出一定规律, 即发生关联点、关联边随时间先后增删的系统性变化, 我们把这样一个过程叫做时序网络演化过程. 通常一个网络可以定义为二元组G = (V, E), 所有节点构成节点集V = {v₁, v₂, ···, v_N}, 节点间的关系构成边集E = {e₁, e₂, ···, e_H}. 在时序网络中, 边集E中的元素可以用形如(i, j, t, δt)的四元组表示^[28], 表示节点i与节点j从t时刻开始产生交互并持续δt的时长. 如视频通话数据网络中, 用户A, B在t₁时刻开始视频通话, t₂时刻结束视频通话, 这个事件可以表示为(A, B, t₁, t₂–t₁), 所有这些四元组的序列构成了视频通话数据的时序网络. 如果省略时序网络中个体间发生事件的时长信息, 而只考虑两个体在某一时间窗内发生交互的初始时刻, 则可以用三元组(i, j, t)来表示节点i与节点j在t时刻发生交互. 将时序网络整个观察期[t, t + S] 分成T个时间窗口, 每个时间窗的大小为τ = S/T, 可以得到T个等间距、不重叠且连续的时间窗口{[t, t + τ), [t + τ, t + 2τ), ···, [t + (T- 1)τ, t + S)}, 则时序网络被分为T个离散有序的时间层网络G₁, G₂, ···, G_T.

2.2   时序网络层间逼近关系系数分析

定义1　时序网络向量范数. t时刻网络G_t有邻接矩阵A = (a_ij)∈R^{n × n} (i, j = 1, 2, ···, n), 在无向网络中, 显然有A^T = A, 即a_ij = a_ji. 邻接矩阵A可用向量表示为A = (a₁, a₂, ···, a_n)^T, 对于向量a_i(i = 1, 2, ···, n)∈Rⁿ, 与a_i对应的一个实值函数(并记为) ||a_i||称为Rⁿ上的一个向量范数, 且满足:

1) ||a_i|| ≥ 0, 其中||a_i|| = 0当且仅当a_i = 0;

2) ||αa_i|| = |α| ||a_i||, $\forall$α∈R;

3) ||a_i + a_k|| ≤ ||a_i|| + ||a_k||, $\forall$a_i, a_k∈Rⁿ.

于是有向量a_i = (a_i1, a_i2, ···, a_in)∈R范数一般定义

$$\begin{split} p-{\text{范数}}:\;&||{a_i}|{|_p} = \left(\sum\limits_{j = 1}^n |{a_{ij}}{|^p}\right)^{\frac{1}{p}}, ~i = 1,2, \cdots, n,\\ &\forall p \in [1, + \infty).\\[-12pt] \end{split}$$

(1)

当p→∞, 定义∞–范数:

$$||{a_i}|{|_\infty } = \mathop {\max }\limits_{1 \leqslant j \leqslant n} |{a_{ij}}|,~i = 1,2, \cdots, n.$$

(2)

定义2　时序相邻网络相容相似度系数. 考虑到时序相邻网络层上节点自身邻居的影响^[23], 即两个节点的共同邻居越多, 两节点越相似. 我们用Salton指标(Salton index, SAL)^[29]定义相邻网络相容相似度系数, 具体形式如下:

$$\begin{split} &c_i^{(t,t + {\rm{1}})} = \frac{{\displaystyle\sum\nolimits_j {{a_{ij}}(t){a_{ij}}(t + 1)} }}{{\sqrt {\left[ {\displaystyle\sum\nolimits_j {{a_{ij}}(t)} } \right]\left[ {\displaystyle\sum\nolimits_j {{a_{ij}}(t + 1)} } \right]} }},\\ &t = 1,2, \cdots, T - 1. \end{split}$$

(3)

相邻网络相容相似度系数描述了节点邻居关系以及节点间持续关联的层间同构率. 其中a_ij(t), a_ij(t + 1)对应相邻时间层网络G_t, G_t+1的邻接矩阵元素. 如果在任一时间层网络G_t中节点i与节点j之间存在连边, 则a_ij(t) = 1; 否则a_ij(t) = 0. 此外, 向量a_i在相邻时刻t, t + 1均为零向量(孤立节点)时, 规定c_i^{(t, t + 1)} = 1; 仅有一个时刻为零向量时, 规定c_i^{(t, t + 1)} = 0.

定义3 　时序跨层网络相容相似度系数. 时序网络中节点间的连边随时间动态增删, 仅仅考虑相邻网络间的同构率可能无法准确辨识时序网络的重要节点. 基于此, 我们提出了时序跨层网络相容相似度系数.

$$c_i^{(t,t + m)} = \frac{{\displaystyle\sum\nolimits_j {{a_{ij}}(t){a_{ij}}(t + 1) \cdots {a_{ij}}(t + m)} }}{{\sqrt[{p(m + 1)}]{{\left[ {\displaystyle\sum\nolimits_j {a_{ij}^p(t)} } \right]\left[ {\displaystyle\sum\nolimits_j {a_{ij}^p(t + 1)} } \right] \cdots \left[ {\displaystyle\sum\nolimits_j {a_{ij}^p(t + m)} } \right]}}}}.$$

(4)

例如, 跨一层网络相容相似度系数

$$c_i^{(t,t + 2)} = \frac{{\displaystyle\sum\nolimits_j {{a_{ij}}(t){a_{ij}}(t + 1){a_{ij}}(t + 2)} }}{{\sqrt[6]{{\left[ {\displaystyle\sum\nolimits_j {a_{ij}^2(t)} } \right]\left[ {\displaystyle\sum\nolimits_j {a_{ij}^2(t + 1)} } \right]\left[ {\displaystyle\sum\nolimits_j {a_{ij}^2(t + 2)} } \right]}}}},$$

(5)

跨两层网络相容相似度系数

$$c_i^{(t,t + 3)} = \frac{{\displaystyle\sum\nolimits_j {{a_{ij}}(t){a_{ij}}(t + 1){a_{ij}}(t + 2){a_{ij}}(t + 3)} }}{{\sqrt[{12}]{{\left[ {\sum\nolimits_j {a_{ij}^3(t)} } \right]\left[ {\displaystyle\sum\nolimits_j {a_{ij}^3(t + 1)} } \right]\left[ {\displaystyle\sum\nolimits_j {a_{ij}^3(t + 2)} } \right]\left[ {\displaystyle\sum\nolimits_j {a_{ij}^3(t + 3)} } \right]}}}}.$$

(6)

跨层网络相容相似度系数揭示了跨层网络间的同构率, 反映了在某一时间区间内网络的局部特征与局部链块的鲁棒性与稳定性的传承. 参数p随所跨网络层数的变化而改变, 即p = m; 当跨层数增加到无穷大的时候, 用∞-范数代替p-范数; m即网络G_t, G_t+m间的间隔层数, 只有节点j同时满足在m个时间层上都是节点i的邻居, 才有a_ij(t)a_ij(t + 1)···a_ij(t + m) = 1; 其他情况时a_ij(t)a_ij(t + 1)···a_ij(t + m) = 0. 向量a_i在时刻t, t + 1, ···, t + m均为零向量(孤立节点)时, 规定c_i^{(t, t + m)} = 1; 不全为零向量时, 规定c_i^{(t, t + m)} = 0.

定义4　时序网络向量投影值. 为描述向量在n维实数空间随时间演化的方向变化, 我们把相邻层网络向量之间的夹角叫做向量投影角, 投影角的余弦值定义为投影值. 邻接矩阵A可以由n个行向量(矢量)表示, 则向量a_i在两时间层t, t + m (t, m = 1, 2, ···, T–1)的投影值具体表示为:

(i) 时序相邻网络向量投影值(m = 1)

$$\begin{split} & d_{i}^{(t,t + 1)} = \cos {\theta _t} \\ =& \frac{{\displaystyle\sum\limits_{j = 1}^n {{a_{ij}}(t){a_{ij}}(t + 1)} }}{{\sqrt {\displaystyle\sum\limits_{j = 1}^n {a_{ij}^2(t)} } \sqrt {\displaystyle\sum\limits_{j = 1}^n {a_{ij}^2(t + 1)} } }},\\ &(i = 1,2, \cdots, n), \end{split}$$

(7)

其中, 0 ≤ d_i^{(t, t + 1)} ≤ 1, 投影值d_i^{(t, t + 1)}越大, 表示向量a_i在相邻时间层t, t + 1的方向一致性越高, 反映节点在时序演化过程中同构率越大. 向量a_i在相邻时间层t, t + 1均为零向量(孤立节点)时, 规定d_i^{(t, t + 1)} = 1; 仅在一个时间层为零向量时, 规定d_i^{(t, t + 1)} = 0.

(ii) 时序跨层网络向量投影值(m > 1)

$$\begin{split} & d_{i}^{(t,t + m)}= {\alpha \cdot {{\bar d}_i}}/{\sigma_i} \\ =& \dfrac{\alpha \cdot \dfrac{1}{m}\displaystyle\sum\limits_{t = 1}^m \cos \theta _t}{\sqrt{\dfrac1{m} \left\{\displaystyle\sum\limits_{t = 1}^m \bigg[\cos {\theta _t} - \Big(\dfrac{1}{m}\displaystyle\sum\limits_{t = 1}^m \cos {\theta _t}\Big)\bigg]^2\right\}}},\\ &(i = 1,2, \cdots, n). \end{split}$$

(8)

对于跨层网络向量投影值, 我们通过两两比较相邻层网络向量, 根据(7)式求出所有相邻层网络的投影值的平均值$\bar d$, 再计算投影值的标准差σ, 定义$\bar d/\sigma$为跨层网络向量投影值d_i^{(t, t + m)}, 其中参数$\alpha = \max\bigg\{ \dfrac{{{{\bar d}_1}}}{{{\sigma _1}}}, \dfrac{{{{\bar d}_2}}}{{{\sigma _2}}}, \cdots, \dfrac{{{{\bar d}_n}}}{{{\sigma _n}}}\bigg\}$, 保证$d_{_i}^{(t, t + m)} \in [0, 1]$. 该投影值越大, 表示向量a_i在时间段[t, t + m](m > 1)的方向一致性越高, 反映节点在时序演化过程中越稳定.

定义5　时序网络节点资源分配相似度系数. 静态网络中资源分配指标(resource allocation, RA)^[30]的思想是: 如果网络中两个节点没有直接相连, 可以将它们的共同邻居作为传递的媒介. 基于此, 我们提出了时序网络节点资源分配相似度系数, 具体如下:

(i) 时序相邻网络节点资源分配相似度系数

$$S_i^{(t,t + 1)} = \sum\limits_{z \in \varGamma \left({{i^t}} \right) \cap \varGamma \left({{i^{t + 1}}} \right)} {\frac{{2||\varGamma \left({{i^t}} \right) \cap \varGamma \left({{i^{t + 1}}} \right)||}}{{d{{(z)}^t} + d{{(z)}^{t + 1}}}}} ;$$

(9)

(ii) 时序跨层网络节点资源分配相似度系数

$$\begin{split} &S_i^{(t,t + m)} = \sum\limits_{z \in \varGamma \left({{i^t}} \right) \cap \varGamma \left({{i^{t + 1}}} \right) \cap \cdots \cap \varGamma \left({{i^{t + m}}} \right)} \\ &\times{\frac{{(m + 1)||\varGamma \left({{i^t}} \right) \cap \varGamma \left({{i^{t + 1}}} \right) \cap \cdots \cap \varGamma \left({{i^{t + m}}} \right)||}}{{d{{(z)}^t} + d{{(z)}^{t + 1}} + \cdots + d{{(z)}^{t + m}}}}} .\end{split}$$

(10)

例如, 跨一层网络节点资源分配相似度系数:

$$\begin{split} &S_i^{(t,t + 2)} = \sum\limits_{z \in \varGamma \left({{i^t}} \right) \cap \varGamma \left({{i^{t + 1}}} \right) \cap \varGamma \left({{i^{t + 2}}} \right)} \\ &\times{\frac{{3||\varGamma \left({{i^t}} \right) \cap \varGamma \left({{i^{t + 1}}} \right) \cap \varGamma \left({{i^{t + 2}}} \right)||}}{{d{{(z)}^t} + d{{(z)}^{t + 1}} + d{{(z)}^{t + 2}}}}}, \end{split}$$

(11)

其中$\varGamma \left({{i^t}} \right) \cap \varGamma \left({{i^{t + 1}}} \right)$表示节点i在相邻时间层的共同邻居, d(z)表示共同邻居节点的度值. 该系数反映了节点间的相似性不仅和共同邻居的数量有关, 还和邻居节点的质量(度值)有关. 节点共同邻居的数量越多、邻居节点的度值越小, 则时序相邻网络节点资源分配相似度系数越大.

定义6　时序网络层间逼近关系系数. 综合考虑两时间层网络相容相似度变化(标量变化)、向量间的投影值变化(矢量变化)以及节点资源分配情况, 我们提出时序网络层间逼近关系系数Z, Z = (Z₁, Z₂, ··· Z_N)^T. Z_i^{(t, t + m)}表示节点i在两时间层网络的同构率, 具体形式如下:

$$\begin{split} {Z}_{i}^{(t,t+m)}=\;&\beta {d}_{i}^{(t,t+m)}{c}_{i}^{(t,t+m)}\rm+(\rm{1-}\beta ){S}_{i}^{(t,t+m)},\\ &(t,~m= {1},{2},\cdots, T-1), \end{split}$$

(12)

其中$d_i^{(t, t + m)}c_i^{(t, t + m)}$反映节点邻居数量多少, $S_i^{(t, t + m)}$反映节点邻居质量优劣, β (β∈[0, 1])表示偏好系数. Z_i^{(t, t + m)}越大, 表示两时间层网络节点连接关系越紧密, 则节点在两时间层网络的同构率越高; 反之, 表示两时间层网络节点连接关系越稀疏, 则节点在两时间层网络的同构率越低.

3.   时序网络超邻接矩阵系统模型构建

经典时序网络建模时考虑用多层耦合网络分析的方法, 将时序网络按层间关系和层内关系建立超邻接矩阵, 但在表示不同时间层网络间关系中使用了相同的参数, 忽略了复杂网络中不同节点层间连接关系的差异性. 为此, 我们提出了改进时序网络建模方法, 在经典SAM模型的基础上, 给出时序网络层间逼近关系系数, 并提出改进的ISAM模型.

3.1   经典时序网络建模思想

文献[25]将时序网络通过层内连接关系和层间耦合关系来表示, 提出了经典的SAM时序网络模型, SAM为NT × NT的分块矩阵, 为构建时序网络提供了一种新思路. 我们把有序时间层网络集合定义为Γ = {G_t} (t = 1, 2, ···, T), T为切分的时间层总数, 则其SAM模型具体表示如下:

$${{A}} = \left[ {\begin{array}{*{20}{c}} {{{{A}}^{(1)}}}&{\omega {{I}}}&0& \cdots \\ {\omega {{I}}}&{{{{A}}^{(2)}}}&{\omega {{I}}}& \ddots \\ 0&{\omega {{I}}}&{{{{A}}^{(3)}}}& \ddots \\ \vdots & \ddots & \ddots & \ddots \end{array}} \right],$$

(13)

其中, 超邻接矩阵A表示经典的时序网络模型; A⁽¹⁾, A⁽²⁾, ···, A^(T)表示层内连接关系, 这里用等间距切分的T个时间层网络对应的邻接矩阵表示, 依次位于超邻接矩阵A的对角线上, 表示有序的时间层网络: 定义a_ij(t)为邻接矩阵A^(t)中的元素, 则a_ij(t) = 1表示在时间层网络G_t中节点i与节点j间有连边, a_ij(t) = 0表示无连边; ωI表示相邻层网络层间耦合关系, 其中ω为可调参数, 在lim ω → 0时, 层变得不耦合; 在lim ω → ∞时, 层之间的耦合非常强, I为N × N单位矩阵. 由于经典的SAM时序网络模型中仅考虑层的最近邻耦合关系, 所以超邻接矩阵A其他部分均用0表示.

3.2   改进时序网络建模分析

经典的SAM时序网络模型中, 相邻层间关系用同一参数ω来表示, 忽略了异质网络中不同节点的差异性, 为了更真实地反映相邻时间层网络连接的实际情况, 本文对SAM模型中的相邻层间关系做出改进, 并考虑了非相邻层间耦合关系.

时序网络相邻层间关系和节点在相邻网络间的连接关系与其在相邻层上的持续出现度及节点的邻居关系层间相似程度有关^[26], 考虑时序演化过程中节点邻居的数量和质量变化, 我们提出时序网络层间逼近关系系数Z. 改进的基于层间同构率的ISAM时序网络模型具体表示形式如下:

$${{{A}}}^{\prime }=\left[\begin{array}{cccc}{{{A}}}^{({1})}& {{{Z}}}^{({1}, {2})}& {{{Z}}}^{({1}, {3})}& \cdots \\ {{{Z}}}^{({1}, {2})}& {{{A}}}^{({2})}& {{{Z}}}^{({2}, {3})}& \ddots \\ {{{Z}}}^{({1}, {3})}& {{{Z}}}^{({2}, {3})}& {{{A}}}^{({3})}& \ddots \\ \vdots & \ddots & \ddots & \ddots \end{array}\right],$$

(14)

其中, Z^{(1, 2)}, Z^{(2, 3)}, ···表示相邻时间层之间的逼近关系, Z^{(1, 3)}, ··· 表示非相邻层之间的逼近关系; Z^{(1, 2)}为N × N的对角矩阵, 即Z^{(1, 2)} = diag (Z₁^{(1, 2)}, Z₂^{(1, 2)}, ···, Z_N^{(1, 2)}), 而Z_i^{(1, 2)}即为节点的层间逼近关系系数, 描述了节点i的层间同构率. 图1给出了该模型的算法流程图, 该模型的算法复杂度${T_{{\rm{ISAM}}}}(n) = o(k{n^2})$, 其中k是关于时间层数T的函数, 当$T \ll n$时, ${T_{{\rm{ISAM}}}}(n) = o({n^2})$.

图2给出了一个包含3个时间层和4个节点的时序网络及ISAM模型的构建, 其中黑色实线表示层内连接关系, 黑色虚线表示层间逼近关系.

图2对应的层内连接关系由各个时间层网络的邻接矩阵确定, 即(14)式的对角线矩阵块部分; 不同时间层网络的层间逼近关系则由各个节点的层间同构率, 即(12)式层间逼近关系系数计算得到. 图2的模型计算结果如下:

$${{A}}' = \left[ {\begin{array}{*{20}{c}} 0&0&1&1&{{{0}}{{.9}}}&0&0&0&{{{0}}{{.7137}}}&0&0&0 \\ 0&0&0&0&0&0&0&0&0&0&0&0 \\ 1&0&0&0&0&0&{{{0}}{{.75}}}&0&0&0&{{{0}}{{.6802}}}&0 \\ 1&0&0&0&0&0&0&{0.{{5}}}&0&0&0&0 \\ {{{0}}{{.9}}}&0&0&0&0&0&1&1&{{{0}}{{.5833}}}&0&0&0 \\ 0&0&0&0&0&0&0&1&0&{{{0}}{{.75}}}&0&0 \\ 0&0&{{{0}}{{.75}}}&0&1&0&0&0&0&0&{{{0}}{{.5833}}}&0 \\ 0&0&0&{{{0}}{{.5}}}&1&1&0&0&0&0&0&{{{0}}{{.6250}}} \\ {{{0}}{{.7137}}}&0&0&0&{{{0}}{{.5833}}}&0&0&0&0&0&1&0 \\ 0&0&0&0&0&{{{0}}{{.75}}}&0&0&0&0&0&1 \\ 0&0&{{{0}}{{.6802}}}&0&0&0&{{{0}}{{.5833}}}&0&1&0&0&1 \\ 0&0&0&0&0&0&0&{{{0}}{{.6250}}}&0&1&1&0 \end{array}} \right].$$

3.3   基于时序网络层间同构率的超邻接矩阵模型构建

本文针对动态时序网络的重要节点辨识问题提出了基于时序网络层间同构率的超邻接矩阵模型ISAM. 该模型对经典SAM进行了改进, 考虑时序网络节点随时间演化时向量的矢量、标量变化, 得到相邻、跨层网络间逼近关系; 结合每个时间层网络邻接矩阵, 最终得到时序网络超邻接矩阵模型.

图3给出了ISAM模型的结构示意图, 根据直接影响节点和间接影响节点把模型分成两个模块: 相邻模块和跨层模块. ISAM模型根据相邻、跨层网络中出现的新增关联关系, 得到与其直接关联、间接关联的节点集合, 使用节点关联关系动态更新对相邻、跨层网络中的节点进行节点表示更新, 然后通过相邻、跨层网络向量的矢量计算与标量计算, 得到了相邻、跨层网络间逼近关系系数; 结合整个时间段各个时间层网络的邻接矩阵, 最终得到超邻接矩阵模型.

考虑到模型的一般性, 令相邻时间层网络的时间间隔为τ, 则时序网络在整个观察期[t, t + S] 内的ISAM模型具体如下:

$${{A}}' = \left[ {\begin{array}{*{20}{c}} {{A^{(t)}}}&{{Z^{(t,t + \tau)}}}&{{Z^{(t,t + 2\tau)}}}& \cdots \\ {{Z^{(t,t + \tau)}}}&{{A^{(t + \tau)}}}&{{Z^{(t + \tau, t + 2\tau)}}}& \ddots \\ {{Z^{(t,t + 2\tau)}}}&{{Z^{(t + \tau, t + 2\tau)}}}&{{A^{(t + 2\tau)}}}& \ddots \\ \vdots & \ddots & \ddots & \ddots \end{array}} \right],$$

(15)

其中, Z^{(t, t+τ)}, Z^{(t+τ, t+2τ)}, ···表示相邻时间层之间的逼近关系, Z^{(t, t+2τ)}, Z^{(t+τ, t+3τ)}, ···表示非相邻层之间的逼近关系, 如Z^{(t, t+kτ)} (k = 1, 2, ···, T – 1)表示时间层网络G_t与时间层网络G_t+kτ之间的逼近关系; Z^{(t, t+kτ)}为N × N的对角矩阵, 即Z^{(t, t+kτ)} = diag (Z₁^{(t, t+kτ)}, Z₂^{(t, t+kτ)}, ···, Z_N^{(t, t+kτ)}), 而Z_i^{(t, t+kτ)}即为节点的层间逼近关系系数, 描述了节点i的层间同构率.

4.   基于时序网络多属性特征的超邻接矩阵建模仿真与分析

4.1   时序网络层间同构率特征动态演化分析

复杂网络中评价节点重要性的方法有很多, 如经典的度中心性, 考虑节点所在位置的介数中心性, 将节点的位置和层级联系在一起的K-核中心性等. 考虑到时序网络中节点与邻居间持续关联关系以及节点所在位置影响, 选取特征向量中心性作为本文的节点重要性排序方法. 节点重要性不仅体现在节点在网络中对信息的传播能力, 也可体现在节点被移除后对网络连通的破坏性, 时序全局效率的差值大小可以反映时序网络的连通性变化.

4.1.1   特征向量中心性

Gershgorin圆盘定理^[31]给出了矩阵特征值的估计方法, 本文构建的超邻接矩阵A′是实对称阵且对角线元素均为零, 矩阵所有特征值均在一个重合的圆盘内, 最大特征根及其特征向量几乎包含了矩阵的所有特征. 本文通过特征向量中心性对时序网络的节点重要性进行评估, 求出超邻接矩阵A′的主特征向量(最大特征值对应的特征向量)v = {v₁, v₂, ···, v_NT}^T. 则向量v的第N(t–1)+i (t = 1, 2, ···, T)项表示t时间层网络上节点i的特征向量中心性, 记为N × T的矩阵W = {w_it}_{N × T}, 则

$${w_{it}} = {v_N}_{{(t} - {1)}} + i,$$

(16)

其中, w_it为矩阵W的第i行第t列元素, 即为t时间层网络上节点i的特征向量中心性. 该指标不仅可以获得各时间层网络节点重要性的排序, 同时能够反映节点在每个时间层网络的重要性随时间变化的轨迹.

表1列出了图2中实例网络的特征向量中心性指标的结果, 并与文献[26]中改进的SSAM模型和文献[25]中经典SAM模型参数ω取0.5的特征向量中心性结果做对比. 从表1可以得到各时间层节点的重要性排序及节点在每个时间层网络的重要性随时间变化的轨迹, 就本文方法 (β取0.5) 结果来看, 第一时间层网络G1中节点重要性排序为1–3–4–2, 且1号节点在3个时间层网络的重要性排序随时间变化轨迹为1–1–2.

经典SAM模型中使用共同参数ω = 0.5来表示不同节点的层间连接关系, 忽略了节点的异质性, 强化孤立节点重要性程度的同时, 弱化了节点层间邻居同构率高的节点的重要性程度. 例如2号节点, 其在G₁中为孤立节点, 特征向量中心性指标w₂₁应接近于0, 而文献[25]中的方法高估了G₁中2号节点的重要性值; 对于G₁中的1号节点, 其层内邻接关系稳定, 虽然在上述方法中该节点均为网络G₁中最重要的节点, 但是在文献[25]的方法里1号节点的特征向量中心性指标w₁₁较小, 为0.2809, 文献[26]中为0.3739, 而本文方法里1号节点的特征向量中心性指标w₁₁最大, 为0.4119, 说明SAM模型弱化了1号节点的重要性值, 且本文方法相比文献[26]节点重要性值有所提升.

4.1.2   时序全局效率

网络平均效率^[32]表示网络中所有节点对之间距离倒数之和的平均值, 它用来表示静态网络信息流通的平均难易程度. 时序网络中, 为描述删除节点后网络连通性变化情况, 我们引入时序全局效率^[25], 其具体形式如下:

$$e = \frac{1}{{N(N - 1)}}\sum\limits_{ij} {\frac{1}{{{d_{ij}}}}},$$

(17)

其中, d_ij为时序网络中各节点之间的时序距离^[33]. 时序距离指的是时序最短路径, 和静态网络不同的是其需要遵从不同连边的时间先后顺序. 例如, 信息从节点i经过节点k最终传到节点j, 需要在时间维度上满足先发生节点i到k之间的有效连接, 再发生节点k到j之间的有效连接, 否则信息不能从节点i传到j.

以图2所示的时序网络为例, 假设有信息从t = 1时的1号节点开始传递, 且在每个时间层网络上只传递一步, 信息传递过程最终在t = 3时刻结束, 则整个过程的时序距离d_ij的结果如表2所列.

最后, 用删除节点后单位时间时序全局效率与原时序全局效率的差值作为节点重要性的验证方法. 首先, 依次删除各个时间层的节点后重新计算网络的时序全局效率, 得到一个N × T的矩阵E = {e_it}_{N × T}; 其次, 与原时序全局效率e做差值, 再除以等间距的时间窗τ, 最终得到删除节点后的单位时间内时序全局效率差值矩阵E′, 具体如下:

$${E'_{i,t}} = \frac{{{{|}}\Delta e{{|}}}}{\tau },$$

(18)

其中Δe = e_{i, t}–e, τ = S/T, E′_{i, t}为删除第t个时间层网络上的第i个节点后单位时间时序网络全局效率差值, 对应的值越大, 说明该被删除节点越重要.

4.1.3   肯德尔系数

为了更直观地检验本文方法的效果, 用肯德尔相关系数^[34](Kendall’s τ)对特征向量中心性矩阵W和单位时间内时序全局效率差值矩阵E′进行相关性分析. Kendall’s τ被用来测量两变量序列之间排序的相关性程度, 其取值范围为[–1, 1], 该值越大, 两序列相关性越强; 反之, 则两序列相关性越弱. 具体定义如下:

$${\rm{Kendall's}}\;\tau = \frac{{\sum\limits_{i < j} {{\rm{sgn}}[({x_i} - {x_j})({y_i} - {y_j})]} }}{{\sqrt {[n(n - 1)/2 - {n_1}][n(n - 1)/2 - {n_2}]} }}$$

(19)

其中X = (x₁, x₂, ···, x_n)^T, Y = (y₁, y₂, ···, y_n)^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为每个时间层节点数目, ${n_1} = \sum\limits_i {{u_i}({u_i} - 1)/2}$, ${n_2} = \sum\limits_j {v_j}({v_j} -$$1)/2$, 其中, u_i为X序列中第i个使得sgn(z) = 0的x_i值的个数, v_j为Y序列中第j个使得sgn(z) = 0的y_j值的个数.

4.2   时序网络模型相关数据统计

为了验证ISAM模型在时序网络节点重要性排序中的有效性, 本文选择两个具有代表性的公开实证网络数据集进行对比实验, Workspace及Email-eu-core数据集的基本统计信息如表3所列.

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 τ值在各个时间层差异不大, 说明了时序网络中相邻层间连接的贡献度占整个网络层间连接的贡献度最高.

图5给出ISAM方法不同偏好系数(β取[0.1, 0.2, ···, 1])下相对SAM方法在各时间层网络Kendall’s τ值的平均提高值变化情况.

从图5结果可以看出: Workspace及Email-eu-core数据的实验结果表明, 在不同网络规模下, 偏好系数β影响不同时间层网络间同构率的大小, 从而间接影响着不同节点的重要性辨识. 当偏好系数β从0.1变化到1时, ISAM方法不同偏好系数下相对SAM方法的Kendall’s τ值平均提高值在逐渐降低, 说明在时序演化过程中, 节点邻居数量对层间同构率的影响小于节点邻居质量的影响, Workspace数据中有个别时间层出现相反情况, 我们认为这是实际数据本身的影响造成的.

5.   结　论

动态时序网络中的重要节点辨识既是热点话题, 也是难点问题. 本文针对时序网络的演化建模, 提取时序网络层内连接关系和层间逼近关系对网络重要节点辨识综合贡献率大小, 给出基于节点层间同构率的时序网络超邻接矩阵建模方法. 该模型描述了直接相邻、跨层及间接相邻、跨层网络节点间关联关系随时间演化的综合逼近关系, 用特征向量中心性作为度量网络节点重要性的辨识工具, 用节点删除法, 推演计算删除节点前后单位时间时序网络全局效率差值, 结合矢量与标量计算, 来评测本文ISAM方法对节点重要性排序. 基于Workspace及Email-eu-core两组数据的仿真结果, 本文ISAM方法得到的Kendall’s τ值较SAM方法在各时间层上平均提高, 最高为8.37%和2.99%. 该方法有效降低网络层间耦合参数讨论的复杂度, 增强动态时序网络节点重要性辨识综合水平.

本文基于层间同构率的ISAM方法在进行时序网络切分时是用等间距的时间窗大小, 而在现实时序网络中, 节点间的交互强度往往不是按时间均匀分布的, 如何动态选取合适的时间窗大小是亟待解决的问题. 未来将使用规模更大的公开实证网络数据集, 对时序网络不同频率交互下多级跨层重要节点辨识进行偏好信息集结, 以便更加深刻地描述时序网络重要节点、区块的演化规律.