时序网络中关键节点的识别方法研究进展

陈 诗，任卓明，刘 闯*，张子柯,2

(1.杭州师范大学阿里巴巴复杂科学研究中心 杭州 311121；2.移动健康管理系统教育部工程研究中心 杭州 311121)

时序网络是拓扑结构随时间不断变化的网络，其中拓扑结构变化表现为节点或连边的增加或减少。现实社会中，随时间不断变化的网络无处不在[1-2]：在线社交网络、通信网络、合作网络、科研网络；经济网络、交通网络、电力网络；基因调控网络、脑神经网络等等。随着蓝牙、可穿戴设备、传感器等的普及，用于构建时序网络的带时间戳的数据的获取逐渐变得容易，基于时序网络开展的研究成果也逐渐丰富。文献[1-2]总结了时序网络的类型、时序网络拓扑结构的测度、时序网络的模型以及时序网络的传播动力学等；文献[3]用时序图分析时序数据，提出了关于时序图路径的测度；文献[4]总结了时序网络相对静态网络的优势，发现时序网络中从初始状态到最终状态，到达过程更快，需求的控制能量和控制轨迹数量级较小。此外，文献[5]对进化的复杂系统中的排序方法进行总结时，提及了时序网络中的节点重要性排序方法。相对静态网络，时序网络增加了时间维度，考虑了节点间的交互顺序，从而可以更准确地刻画真实系统[6-11]。因此，时序网络模型的构建及其相关理论和应用研究，已经成为网络科学的一个重要研究方向。

关键节点一般是在整个网络中处于核心位置的节点，对整个网络的结构或者功能具有较大的影响力[5, 12-14]。网络中关键节点的确定，可以获得有关实体重要性的先验知识从而预测事情的发展进程，如预测关键元件以防止电网或互联网中的灾难性故障、预测成功的科学家或流行的科学出版物等；可以有效调控传播过程，如精准投放电子商务产品广告以实施产品推广、控制流行病爆发或抑制谣言传播等。关键节点的识别方法之所以能在不同领域中得到应用，一方面取决于方法本身的判别价值，另一方面则是因为信息过载时代大众的多方需求，现如今不论个人还是组织都希望以更低的成本获取实现目的最相关的信息。因此，在网络科学研究中，设计有效的关键节点识别方法，并提出合理的评价模型，有着很强的理论研究和实践意义。

目前，时序网络中的关键节点识别这一问题越来越受到学者的关注。以往对于关键节点的挖掘研究大多是将现实系统抽象成点边相连的静态网络，再依据网络的拓扑结构和动力学特征获得表征节点重要性的度量指标，这些关于网络中节点重要性的研究工作主要集中于网络的静态结构和理论分析上[15-20]。而真实的复杂系统随时间不断进化，个体间的交互呈现出典型的间歇性和阵发性，这使得过去基于静态网络的研究在相当程度上制约了研究成果在实际系统中应用的效果和可靠性。因此，有必要从不同角度总结时序网络中关键节点挖掘的研究进展，并对未来可能的研究方向进行探讨。

本文按如下思路展开：首先分析现有的时序网络建模，再基于时序网络模型从网络的拓扑结构、随机游走动力学以及机器学习的视角概括时序网络中节点的排序测度或中心性指标；然后从网络性能变化、传播动力学以及预测性能三个方面介绍时序网络中关键节点的评价方法；最后在总结和展望部分指出了当前面临的问题和可能的发展方向。

1 时序网络建模

时序网络模型的构建是探索时序网络中关键节点识别方法的基础。这里我们所研究的时序网络模型具有一个共同的特征：均不考虑时序网络中节点的增加和移除，而只考虑连边的出现和消失，即所构建的时序网络模型中节点数目保持不变，连边随时间动态变化。其所依赖的数据记录一般以三元组(i,j,t)的 形式呈现，其中i 和 j表示两个相关的实体(即网络中的节点)，t表示两实体发生作用的时间(即在时间t， 节点i 点 j之间出现连边)。目前，主要的时序网络模型大致可分为三类：基于静态图的时序网络模型，基于快照的时序网络模型和基于明显路径流的时序网络模型[21]。

1.1 基于静态图的时序网络模型

基于静态图的时序网络模型，也叫时间聚合以连边 (B ,D)为例，时间聚合图1 上的序列为[1,2,6]含交互的具体时间，对应表示节点B 和节点D 在时间 t=1、 t=2和 t=6时发生交互。此类模型在传统静态网络的基础上增加了时间信息，使其能更真实展示现实系统的演化，但在一定程度上不够直观，且不易用矩阵方式存储和计算。图(time aggregated graphs)，是在静态网络拓扑结构的基础上，把节点间交互的时间信息存放在边上的时序网络模型。图1 是常见的时间聚合图模型。

关于此类时序网络模型的研究，文献[22]最早提出并将其用于研究时序网络的连通性和推理问题。之后，文献[23]将模型中的连边建为有向边，研究了社会沟通网络中的信息路径结构；文献[21]将连边上具体的时间信息转化为相应时间的边对应的有和无两种状态，探索了时序网络中中心性测度的计算方法；文献[24]也对时间聚合图提出了改进，其假设连边有向且一对节点之间可能存在带有不同时间戳的多条连边，探索了时序网络中的时序PageRank 的表示与计算。此外，文献[1-2]也表示通过静态图表征时序网络可以研究时序网络的时序属性和拓扑属性，并对相关的静态图进行了简单介绍。

1.2 基于快照的时序网络模型

基于快照(snapshots)的时序网络模型，实际可以看作基于静态图的时序网络模型的拓展，在一定程度上展示了事件的演变过程[25-26]。此类模型的核心在于将研究的整个时间段 [0, T]切分成连续的长度为 ω的 m个 快照 N1,N2,···,Nm(m=T/ω)。每个快照可以包含在特定时间瞬间发生的所有事件，也可以是在特定时间窗口内发生的所有事件的静态聚合。根据模型中是否展现快照间的关系，可以将基于快照的时序网络模型分成两类。

1.2.1 时间窗图模型

最常见的基于快照的时序网络模型是如图2 所示的时间窗图模型。该模型将快照依次表示为时间聚合图，快照的时间间隔即为时间窗口的大小。图2b 中时间窗大小为 ω= 1，图2c 中时间窗大小为ω=2。快照中的事件根据快照的时间间隔而定。

文献[25]首先提出将动态图视为一系列的静态图。在此基础上，不少学者将此类模型作为设计时序网络中关键节点识别方法的基础，提出了时序网络中识别节点重要性或影响力的测度[4, 27-38]。此外，文献[39]在探索动态网络中的中心性测度时，将每个时间窗中的连边定义为有向；文献[40]在设计时序网络的随机游走中心性时，为每个时间窗中的连边赋予权重，其中第t个快照中节点对之间的连边权重用时间 (t − 1)ω 到时间 tω间该节点对的接触次数表示。应注意，快照时间间隔的选取(即时间窗大小的选择)目前仍是无定论的问题[41-42]。当使用时间窗图模型表示时序网络时，有必要进一步探测模型中不同大小的时间窗口对研究结果的影响。

1.2.2 多层图时序网络模型

在时间窗图模型的基础上，学者提出了如图3所示的多层图时序网络模型。该模型实质上也是基于快照的时序网络模型，一般由层内关系和层间关系共同定义：层内关系对应一个快照，可理解为时间窗图模型中的一个时间窗图，表征节点间的交互作用；层间关系则表征相邻时间窗中对应节点间的关系，且只有节点自身的连接。就层间关系而言，目前常用的思想有两种，即采用固定的常数和采用相邻时间快照间节点的相似性关系。图3 中的 ωi即是对层间关系的表征。

关于此建模方法，文献[43]对其进行了详细的讨论；文献[44]将特征向量中心性推广到时序网络时用到该结构，并采用固定常数表示层间关系；文献[14]则采用基于相邻时间快照间的相似性关系定义层间关系，并基于该模型探索了不同时间层不同节点的特征向量。此外，文献[46]针对层间耦合关系的度量方法进行了分析研究，通过计算不同层间相似性指标值与正理想解和负理想解之间的欧氏距离对度量方法进行排名，发现用优先链接指标度量时序网络时间层的耦合关系，所挖掘出的重要节点准确率最高。

1.3 基于明显路径流的时序网络模型

基于明显路径流的时序网络模型，是基于快照的时序网络模型在时间维度上的进一步细化。模型中每个实体对应的节点根据交互信息跨时间复制，而表示潜在信息流的边则用有向边表示并按时间顺序添加。图4 是该模型的具体展示，其中水平轴表示时间尺度，竖直轴表示网络中的节点，网络节点的交互只发生在横轴两个相邻的时间层之间，每个节点在前后时间层始终与自身相连。该建模方法已被文献[47]用来研究时序网络的节点重要性评估。文献[3]在2009 年也提出了其近似模型，并表明是完全保留原始数据时间信息的时序图模型。之后，文献[48]将其用于时序网络中覆盖中心性的探测，发现大多数的高中心性节点位于某特定时间附近较小的时间窗内，从而获知时序网络中的大量信息只经过少量重要的时序节点传送，且该传送过程发生的时间存在对应的瓶颈期。

此外，文献[49]基于小世界网络和无标度网络 拟 合 Susceptible-Infected-Susceptible(SIS)、Susceptible-Infected-Recovered(SIR)传播模型，建立了基于明显路径流的时序网络模型。当确定初始感染源时，每个时间层节点的状态以及相邻时间层节点间的连边可以完全确定，即整个传播过程生成的时序网络模型固定。应注意，该模型层间不同节点间交互的发生存在激活概率，而不是与所有的邻居节点都存在连边。图5 是确定初始传播源，采用SIR 模型，根据节点交互情况和状态变化生成的时序网络模型。其中，红色的节点表示感染状态I，绿色的节点表示易感状态S，白色的节点表示恢复状态R；红色的边和绿色的边均表示拟合SIR 模型时节点间连边在相应的时间被激活而发生交互，其中红色的边表示t 时刻的感染节点致使t 时刻的易感节点变成 t+1时刻的感染节点，绿色的边则表示t 时刻的易感节点与t的感染节点或易感节点发生交互而在 t+1时刻仍然保持易感状态；灰色的边则表示层间节点状态的传递，其中感染状态I 以一定概率成为恢复状态R。

1.4 其他时序网络模型

除了以上三类时序网络模型，也有学者对时序网络的建模及相关特征进行了专门研究。例如，文献[50]除了考虑事件瞬时发生的情况，还考虑事件会持续一段时间的情况，从而在改进时序网络模型的基础上定义了时序平均距离；文献[51]从进化的系统出发，提出了时间窗口大小不等的时间窗图模型，其中时间窗口大小依据事件进化中事件相似性的最大值而确定；文献[52]通过考虑一个与时间有关的哈密顿量，构造了一个随时间变化的网络的虚时间演化算子，从而通过函数解释时序网络模型中的动态变化；文献[53]基于聚合时间图和时间窗图，在每个快照中加入节点和连边的定量属性及方向信息等，然后将t时刻的在线社交网络表示为 Gt=(Vt,Et,FVt,FEt,t)， Vt是时间t时刻在线社交网络中的节点集， Et是 时间t时刻在线社交网络中连边的集合， FVt是 按特征向量 fv定量描述节点v ∈Vt属性的 |Vt|×|fv|维 矩阵， FEt是按特征向量 fe描述连边 e ∈ Et属 性的 |Et|×|fe|维矩阵，从而识别大规模时序在线社交网络中的活跃节点；文献[54]提出高阶聚集网络研究时序网络的路径结构，并对静态网络中的介数中心性、接近中心性和可达中心性进行了拓展。该模型背后的思想是每一个 k阶连边(v,w)表 示底层时序网络中长度为 k的时序路径存在的可能性。具体地，将 k−阶静态聚合网络表示为G(k)=(V(k),E(k))， 其中 V(k)⊆Vk是 k个节点组成的元组的集合， E(k)⊆V(k)×V(k)是连边的集合。简化处理，设置v = (v1−v2−···−vk)∈V(k),vi∈V 以及w=(w1−w2−···−wk)∈V(k),wi∈V 是 k阶静态聚合图中的节点， e= (v,w)∈E(k)是 k阶静态聚合图中的连边，连边 e存在的条件为两个 k阶静态聚合图中的节点 v和w 恰好有k −1个 元素重合，即有vi+1=wi,i=1,2,···,k −1。此外，文献[55]将时序网络拓展到二分网络，通过简单将其划分为过去的时间窗和未来的时间窗，构建了用户-商品时序二分网络，并基于此提出了商品的流行性和时序新颖性。这些其他时序网络模型有的额外考虑了时序网络的属性和特征，有的直接将模型通过数值形式表征，都为进一步研究时序网络中的节点重要性奠定了基础。

2 时序网络中关键节点的识别方法

时序网络中关键节点识别方法的主要思路是基于时序数据构建时序网络模型，然后通过时序网络的拓扑结构或动力学特征，采用网络节点排序算法，识别关键节点。下面主要从网络的拓扑结构、动力学以及机器学习方法三个方面介绍。

2.1 基于拓扑结构的识别方法

节点的重要性很大程度上是由节点在网络上的结构所决定的，依据网络的拓扑结构设计节点的排序指标，是时序网络中关键节点识别的一类重要方法。目前，这些方法的提出多基于静态拓扑指标，如度中心性[56]、介数中心性[57]、接近中心性[58]、kshell 值[59]等。

2.1.1 基于度中心性的识别方法

静态网络中，节点中心性最直接的度量是度中心性[56]，即一个节点的度越大意味着这个节点越重要。在时序网络，基于度中心性的时序节点中心性指标也同样是最直接的识别重要节点的依据。

文献[47]基于明显路径流的时序网络模型，首先提出了在一段时间 [i,j]内 节点 v ∈ V的时序度值

式中， Dt(v)表 示时间t时 节点 v 的度，忽视从 vt−1到vt的自边 (t= i+1,···,j)。节点的时序度值越大，节点越重要，该节点成为关键节点的可能性也越大。

文献[37]基于时间窗图模型，对各个时间窗内的时序度中心性值取标准差，提出了时序度中心性偏差值对节点重要性进行排序。具体计算公式如下：

基于度中心性的识别方法包括了时序度中心性以及时序度中心性偏差值，两者均聚焦于时序网络中随时间变化节点度值的波动性。其中，时序度中心性通过取不同时间节点度的均值的方式对度值的波动性予以处理，而时序度偏差中心性则在时序度中心性的基础上通过求标准差进一步体现出度值的波动性特征。因此，时序网络中基于度中心性的识别方法优于静态网络的度中心性，但在判断过程中都遵循，所提出的表征节点重要性的指标值越大，节点越重要。此外，一个值得注意的潜在问题是，一个时间序列的中心性指标的均值越大，相应的方差也越大[60]。

2.1.2 基于最短路径的识别方法

静态网络中，介数中心性[57]和接近中心性[58]是基于最短路径刻画节点重要性的典型指标。其中，介数中心性考量经过某节点的最短路径的数目，刻画该节点作为中介对信息沿着最短路径传输的控制能力；接近中心性考量每个节点到其它节点的最短路径的平均长度，刻画节点传输信息的速度。

时序网络中，由于路径受连边产生时间和产生顺序的影响，呈现出不同于静态网络中路径的特征[29, 54, 61]，主要包括路径的不对称性，未连通的节点更多，消息传递中的滞留或失效等。基于此，许多学者对时序网络中的路径、最短路径以及距离重新进行了考量，定义了时序路径、时序最短路径以及时序距离，并在此基础上提出改进后的时序介数中心性、时序接近中心性以及其他基于时序最短路径的相关指标。

文献[27]以时间窗图模型拟合时序网络，分别从局部和全局的视角出发考虑网络的演化，提出新的时序距离指标，量化和比较了信息扩散过程的速度；然后基于时序路径和时序距离，提出了研究关键节点的时序中心性指标，研究了时序网络中的小世界现象，并将时序中心性指标用于恶意软件的检测[27-29, 62-63]。关于时序路径和时序距离，文献[27]进行了如下定义：

表示同一时间窗内最大跳跃数为 h的条件下，从 t1时 间的节点 n1出 发在时间 tk到达节点 nk的时序路径，其中 tmin⩽tk−1⩽tk⩽tmax。假设是节点i和节点 j间所有时序路径的集合，若时序路径不存在，则，说节点i和 节点 j是不连通的节点对，并设定距离

则节点i和 节点 j间的所有最短时序路径集合为

基于此，文献[28]从静态网络中的介数中心性和接近中心性出发，提出了时序介数中心性和时序接近中心性的计算方法。关于时序介数中心性，不仅需要考虑通过节点的最短路径的数目，同时需要考虑最短路径中节点在将信息传递给下一个节点前保留信息的时长。因此先计算节点i 在时间t 的时序介数中心性如下：

式中， w 表示时间窗的大小； m表示时序网络中时间窗的总数目。

关于时序接近中心性，直接扩展静态网络中的计算公式得到时序接近中心性的计算如下：

所计算的节点的时序介数中心性和时序接近中心性的值越大，表明节点越重要。但是，这两个时序节点重要性评价指标并不总是适用于任何场景。文献[62-63]将所提出的时序指标用于选取关键节点用于阻断恶意软件传播，便发现时序介数中心性与静态指标的效果不显著，但通过选取时序接近中心性高的节点则有显著效果，因为时序接近中心性高的节点可以很快到达大多数节点。

式中， ∆t,j(v,u)是 时间间隔 [t,j]内 节点 v 到节点u 的时序最短路径距离，以路径中的连边数表示。当节点v 和节点u 之 间不存在时序路径时， ∆t,j(v,u)=∞。以Sx,y(s,d) 表示在时间间隔 [x,y]内 ，从节点 s到节点d的时序最短路径的集合， Sx,y(s,d,v)是路径中包含节点 v 的 Sx,y(s,d) 的子集。定义时间间隔 [i,j]内节点v ∈V标准化的时序介数中心性计算如下：

文献[50]考虑到事件从发生到结束的耗时以及时序路径的不同开始时间等影响，将整个网络视为一个整体，研究了对有限周期内无穷距离的处理方法，并提出了节点对间的平均时序距离计算公式：

发现当且仅当节点间有唯一时序路径时，平均时序距离独立于路径的开始时间，也独立于观测时间窗口的时间顺序设置。在此基础上，结合静态网络中的接近中心性公式定义了时序接近中心性：

该时序接近中心性与静态网络的接近中心性类似，值越大，则表明节点越重要。

文献[33]发现时序网络中基于路径的节点重要性评估指标的研究，大多基于数据集起始时间开始的路径，或虽考虑整个数据集时间跨度内的所有路径但多计算单一的静态指标，于是开放地考虑路径的起始时间(即考虑开始于数据集时间间隔内任意时间为起始时间的所有路径)，并将静态网络中的接近中心性拓展为随时间不断进化的时序接近中心性指标，从而用于评估任意给定时间任意节点的重要性。具体方法如下：

定义动态网络中从节点 u0到 节点 vk开始于时间ts的时序路径为连边序列：

该序列满足：

1)对所有i， i= 0,1···,k −1,ui+1=vi；

2) 对所有i， i= 0,1···,k −1,ti

3) t0ts。

那么该时序路径的间隔时间为 tk− ts，且该间隔时间最短的路径为最短时序路径。定义从时间t开始节点 u到 节点 v的距离为最短时序路径的间隔时间，用 dt( u,v)表 示；当路径不存在时 dt( u,v)=∞。在此基础上，定义时间t节 点u 的时序接近中心性如下：

实验结果发现，节点重要性随时间变化，捕捉节点全局重要性的聚合指标可能无用，但所提出的时序接近中心性有助于识别整个网络时间间隔内一直很重要的节点，即节点在任意时间的时序接近中心性值都较大，则可以认定该节点在研究的时间间隔内一直很重要。

文献[48]基于时序节点(节点索引和时间的组合)的最快时序路径，提出了两个时序节点在特定时间的中心性测度，并发现这两个中心性测度对于时间标度的变化具有鲁棒性。具体计算如下：令v=(v,τ),u=(u,τldt(v,u)),w=(w,τeat(v,w))。根据静态网络中的覆盖率定义了时序网络中的覆盖率。如果满足以下两个条件，则时序节点 v覆盖了节点对(u,w)：

1) τeat(u,w)=τeat(v,w)，即如果顺便经过时序节点v，从时序节点u 出 发到达 w的最早时间不变；

2) τldt(w,u)=τldt(v,u)，即如果顺便经过时序节点v，到达时序节点 w 从u 出发的最晚时间不变。

基于时序覆盖率的定义，定义了时序覆盖中心性(TCC)，即时序节点 v= (v,τ)所覆盖的节点对(u,w)∈V×V ( V是网络中的所有节点)的比例。如果时序节点 v的TCC 的值越接近1，说明该节点覆盖的节点对越多，则其越中心。

由于即使移除TCC 值大的时序节点，也不能总是使 τeat(v,w)更 大或者 τldt(w,u)更小，所以在时序覆盖率的基础上加入额外的标准定义了边界覆盖率。如果满足一下条件，就说时序节点 v在边界上覆盖了节点对 (u, w)： 1) (u, w)被 时序节点 v覆盖；2)τeat(u,v)=τ 以及 τldt(w,v)=τ。

在此基础上，定义时序边界覆盖中心性(TBCC)，即时序节点 v= (v,τ)在边界上所覆盖的节点对(u,w)∈V×V ( V是网络中的所有节点)的比例。与时序覆盖中心性相似，如果时序节点 v的TBCC 的值越接近1，说明该节点覆盖的节点对越多，则其越中心。实验结果表明真实时序网络中的大量高中心性节点位于特定时间的很窄的时间窗内，而且大量信息会在短时间内通过少量重要的时序节点。

最近，文献[64]基于明显路径流的时序网络模型和节点重要性依赖于其邻居重要性的观点，提出了一个时序信息聚集过程(TIG-process)以识别时序网络中的关键节点。基于时序信息聚集过程，作者对比了最快到达路径和最短时序路径在节点重要性识别中的区别，并结合时序信息聚集深度、不同距离邻居的重要性以及节点的初始信息分别给出了依据两种最短路径对节点重要性进行排序的tig-分数。经实验验证发现，在利用最快到达路径评价节点间距离时可以获得更好的识别性能，且可得到最优的信息聚集深度，因为最快到达路径可以聚集更多的时序信息。

基于时序最短路径的指标是时序网络中关键节点识别的一类重要方法，此类方法的重要区别在于定义时序最短路径，是否考虑了如下诸多因素并对其做了何种处理，具体包括路径的起始时间和终止时间、无穷路径的处理方式、信息随时间和距离的衰减，以及最短路径究竟定义为途径节点数目最少的路径还是花费时间最少的路径等。其优势在于通过对时序路径和时序距离的定义，可以更好地捕获时序网络中的时间特性，但同时也存在计算复杂度提高、时间成本增加等问题。

应注意，节点的最短路径数并不总是测量某节点中心性的最好方式，最短路径也并不总是和相应的过程相关，比如疾病总是通过任意路径随机传播，谣言总是沿着长于最短路径的路径进行传播[30]。因此考虑随机游走而不是最短路径的节点识别方法也同样重要，后文将在基于动力学的识别方法中讨论时序网络中基于随机游走的识别方法。

2.1.3 基于K-核分解的识别方法

K-核分解用于静态网络中的关键节点识别和节点重要性指标设计，早已得到普遍认可和实践。其中文献[59]于2010 年首次运用K-核分解获得的节点重要性的排序指标(k-shell)，以及在此基础上不少学者进行的相关拓展。比如文献[65]进行加权网络中的K-核分解，提出了加权网络中的ks 指标；文献[66]综合考虑目标节点自身K-核的信息和与网络最大K-核的距离，提出新的度量节点重要性的指标；文献[67]基于最小K-核节点邻居集合中最大ks 值，提出了更深度的指标。在时序网络的研究中，文献[38]进行了时序网络中基于边的k-shell 分解，提出了同时考虑自身和邻居的时序k-core 值的表征时序网络中节点重要性的时序指标。其具体的分解方法和节点重要性计算指标如下：

1) 网络快照创建：设置时序网络的时间窗口大小为 T ，得到快照网络序列 N1,N2,···Nm；

2) 快照中边权计算：在每个快照网络Nt(t=1,2,···,m)中，按照最初的k-shell 分解方法求得节点的k-shell 值，节点 i在 快照 Nt中的k-shell 值记为。对快照Nt，连边( i,j)的 权值定义为=min

与此同时，为验证同时考虑节点自身和邻居的时序k-core 值的时序指标 TK (i)的优越性，作者基于K-核分解提出3 个对比时序指标：

1) SK：静态k-shell 值表征时序网络中的核值；

2) TKD：同时考虑节点自身和邻居的时序kcore 值的时序指标 TK (i)除以节点在静态网络中的度k(i)

以上4 个指标( TK ,SK,TKD,ASK)，均满足节点对应的指标值越大越重要的规律。

基于K-核分解的识别方法除了考虑节点的位置属性随时间的变化，同时也考虑了随时间变化节点间的连边关系。通过在不同时间快照中进行K-核分解，初步获得节点的瞬时核值；然后再将节点的瞬时核值映射到静态图的边，并通过边的核值获得节点的全局时序核值。目前在时序网络关键节点识别的研究中，这种从点到边再到点的重要性传递方法尚不常见。

2.1.4 基于特征向量的识别方法

静态网络中的特征向量中心性[68]、PageRank[69-70]、枢纽值与权威值(即HITS)分数[71]以及特征因子[72]等基于特征向量的中心性测度，它们作为特征值问题的解决方案出现，常常通过计算中心性矩阵的主特征向量的元素获得，是一类简单且重要的节点重要性排序方法。

将此类方法推广到时序网络，文献[44]提出了一种在有序多层图表示的时序网络中基于特征向量的中心性测度的泛化方法，该方法通过在超中心矩阵( NT ×NT维矩阵)中耦合时间层中心性矩阵(以权重 ω最相近的时间层间相同节点的耦合)实现。超中心矩阵用权重 ω表 示为 C( ω)，经转换ε=1/ω变 成超中 心矩阵 C(ε)。 C(ε)的主特征向量v(ε)表 示 所 有 节 点-时 间 层 对 (i,t)的 联 合 中 心 性(jointly centrality)，即表示时间层 t节 点 i的中心性，长度为 NT ，其中 N为节点数，T 为时序网络中的时间层数。具体计算公式如下：

在联合中心性的基础上，将特征向量 v(ε)映射为 N× T 维矩阵W ，其中Wit=vN(t−1)+i(ε)，定义边际节点中心性 xi( MNC)和边际时间层中心性 yt(MLC)，分别反映节点和时间层的重要性。计算公式分别如下：

考虑特定的时间层t，有节点-时间层对 (i,t)的条件中心性 Zit，表示时间层t上 节点i相对于其他节点的重要性。计算公式如下：

实验结果证明，所提的条件中心性和边际中心性确实有效，通过这些中心性测度可以动态识别不同时间的重要节点，且中心性测度的值越大，节点越重要。

文献[45]在文献[44]的基础上提出了改进，认为时序网络建模中层间关系的参数表示忽略了不同节点层间连接关系的差异性。受文献[29]对时序相关系数以及文献[32]对时序网络中邻居拓扑重叠系数研究的启发，文中将节点的层间连接关系用邻居拓扑重叠系数表示，提出了基于节点层间相似性的超邻接矩阵时序网络构建方法。利用特征向量中心性指标，获取节点在各个时间层上的重要性排序，从而研究节点重要性随时间变化的轨迹。实验证明，改进后的模型获得的结果优于文献[44]的结果。

基于特征向量的识别方法与前三种基于拓扑结构的识别方法不同，其获得的往往不是全局的节点重要性排序，而多用于获得对应时间快照上的节点重要性排序以及不同时间快照上的重要性排序，因此结果相对而言更微观且更真实，但难以实现全局上节点重要性的判断。

2.2 基于动力学的识别方法

除了网络结构之外，节点在网络动力学行为中的影响力也常常被用来作为节点重要性的评判标准。目前，基于网络动力学的识别方法可以粗略的分为基于随机游走和传播动力学两类。

2.2.1 基于随机游走的识别方法

过去基于随机游走的方法，如Katz 中心性[73]、PageRank[74]、LeaderRank[75]等，已经很好评估了静态网络中的节点重要性。由于基于随机游走的排序算法结合了网络的拓扑属性和动力学属性，且不受网络中信息多少的限制，这使得对随机游走过程的研究以及对网络中基于随机游走的重要节点识别方法的研究逐渐拓展到时序网络。关于时序网络中的随机游走过程：文献[76]研究了时序网络的可达性及连通性，并提出了一种与静态网络中随机游走的谱间隔类似的结构测度表征时序网络的连通性；文献[77]分析了基于时序网络数据的随机游走模型的覆盖率和平均首次通过时间，提出了时间最快的路径和距离最短的路径，发现时序网络中的扩散相对静态图更慢；文献[42]则将时序网络数据和随机游走的稳定状态概率结合起来。关于时序网络中基于随机游走的重要节点识别方法，部分研究是基于静态指标的改进，另有部分研究则是基于时序网络和随机游走的特征，或是基于具体的随机游走过程而提出的全新的指标。

静态图中基于随机游走的经典例子是Katz 中心性[78]。其基本观点是节点i和 节点 j沟通的倾向性可以根据从节点i到 节点 j 的长度为 ℓ= 1,2,3,···的随机游走路径数目决定，长度 ℓ较长的随机游走路径更重要，因此最初的想法是选择适当的参数 α对长度为 ℓ的游走路径按照 αℓ进行缩放。节点i和节点j之间长度为 ℓ的游走路径数目对应邻接矩阵 ℓ次幂的元素。因此矩阵 S= I+αA+α2A2+···的元素sij测 量了节点i和 节点 j 沟通的倾向性。当 α< ρ(A)邻接矩阵的谱半径时，矩阵S 可以收敛至 (I − αA)−1。那么，节点i的Katz 中心性为矩阵 S 第i行的和，计算如下：

文献[79]建立时间窗图模型，通过类似的原理将Katz 中心性拓展到时序网络。以 A(t)表示第t个时间窗对应的邻接矩阵，那么任意长度 k的时序游走路径的计数按如下形式获得：

当 α< mintmρ(A(tm))，则有沟通性矩阵：

根据沟通性矩阵Q，定义传播中心性以及接收沟通性，具体计算分别如下

文献[80]则基于文献[79]提出的时序网络中的沟通性矩阵 Q，对文献[81]和文献[82]提出的基于随机游走的沟通介数(communicability betweenness)和分解介数(resolvent betweenness)进行了相关拓展，并提出了基于随机游走的时序网络中节点 v的介数。具体计算如下：

对于时序网络中PageRank 值的研究，大多仍然是融入时间因素的静态PageRank 值。其中比较典型的是PageRank 值计算时加入与时间相关的衰减因子[83-86]，或结合不同类型网络(如引文网络[87-88]、体育社会网络[89]、社交网络[93]等)随时间变化的特征改进转移矩阵从而计算静态PageRank 值。但是，文献[24]则明确将时序网络表示为基于静态图的时序网络模型(连边上的时间戳表示相应的到达时间)，并基于时序网络中的随机游走，结合时间信息和网络动力学提出时序网络中的时序PageRank，以此估计任何时间t节 点u 的重要性。具体计算方法如下：

首先，定义时序网络 G中时间相关的随机游走，即时序随机游走为如下边序列：

其中 ti⩽ ti+1(1 ⩽i ⩽j−1)。

其次，对节点u 在静态网络中的PageRank 得分π(u)进行调整(如下公式)，使得计算只考虑时序游走而不是所有的游走。

调整过程如下：假设 ZT(v,u|t)是 从节点 v出发在时间t前到达节点 u的所有时序游走的集合，那么某特定的时序游走 z ∈ ZT(v,u|t)的概率

式中， c(z|t)是 所有从节点 v 出发在时间t前到达节点u的时序路径的数目，分母表示所有从节点v 出发的与时序游走z 路径长度相等的时序游走数。

结合上述两个公式，节点 u在 时间t的时序PageRank 分数的计算公式为：

同时，由于上述时序PageRank，时序随机游走开始的节点是u 的 概率与从节点 u开始的边的数目成正比。假设向量 h′表示游走开始概率向量，即包含所有节点作为游走开始节点概率的向量。则对于节点u， 向量 h′中 的元素满足对于所有节点v ∈ V，有h′(u)=(u,v,t)∈E/|E|。此外，给定个性化的特征向量h∗，可得个性化的时序PageRank 值的计算公式为：

该个性化的时序PageRank 值越大，表明节点越重要。在此基础上，文献[24]提出了一个计算该时序PageRank 值的算法，并证明算法可以收敛，且当边分布是静态时可以收敛到静态网络的PageRank 值。真实数据上的结果也验证了该方法的合理性，并表明其是一个灵活的测度，可以根据网络随时间的变化而调整。

文献[40]提出的TempoRank 是基于随机游走的时序网络的中心性测度。该测度是基于明确路径流的时序网络模型在时间周期边界条件下随机游走的固定密度(即达到稳态时可在节点中找到游走者的概率)，其与时序网络对应的静止加权有向网络中的节点连入强度高度相近。具体求解过程如下：

1) 定义每个快照中节点对i 和j 之间的转移概率(以第t个快照为例， ωij(t)表 示该快照中节点i与节点 j间的接触次数，则第t个快照对应的邻接矩阵为 ω(t )=(ωij(t)))

式中，当 i=j 时 δij=1， 否则 δij=0； q表 示节点i为非孤立节点时，不转移到其他某一邻居节点的概率； si(t) 表示在第t个 快照中节点i的所有连边数量之和(即节点i的强度)，且有

当 si( t)=0 时表示节点i是 孤立点，当 si( t)1表示节点i是非孤立点；

2) 定义时序网络一个周期的转移矩阵为

式中， r表示一个周期内的所有快照的数目，B(t)=(Bij(t))是 第t个 快照的转移矩阵。定义 Ptp的左侧主特征向量(对应的特征值为1)为

文献[39]从时间窗图模型出发，规定每个时间窗为连边不可变的有向图快照Gt，定义其对应的邻接矩阵为 A(t)。基于“如果动态网络中的一个节点经过一段时间对另一个节点产生影响，那么在不同的时间存在一条可以通过中介连接起点和终点的路径”的思想，提出了新的节点中心性测度。考虑未来快照网络Gtk+1的状态除了依赖于当前快照网络Gtk的状态，是否还依赖于之前的状态，将时序网络中的信息传播建模为无记忆的动力学过程和有记忆的动力学过程，分别如下。

令 ∆1,n是 信息从时间 tk的任意节点i传递到时间tn的节点 j 的时间间隔 {t1,t2···,tn},(1 ⩽k ⩽n)。那么在给定的时间间隔 ∆1,n内从节点i到 达节点 j的累积期望信息量由下面累积动态中心性矩阵的 (i,j)位置元素给定：

2) 有记忆的动力学过程，未来快照网络Gtk+1的状态依赖于之前所有快照网络 Gti(i ⩽k)的状态。除了上述的衰减因子 α 和 β，该过程定义了保留概率γ(0 ⩽γ ⩽1)和 保 留 时长 m( m ∈1,2,···n)，保 留 概率γ表示节点保留在时间 tk接收到的信息直到时间tk+1的概率。那么，依赖于之前时间邻接矩阵的时间 tn的保留邻接矩阵 R(tn)如下：

保留动态中心性矩阵为：

时间间隔 ∆1,n内的保留累积动态中心矩阵为：

文献[34]针对动态时序网络，提出了一种实时性消息传播过程中识别“最近较活跃”节点的方法。该方法扩展静态网络中基于通路(walk，即点边交替出现的序列)的节点中心性分析方法到随时间动态演化的网络中，将消息传播路径分解到时间-空间两个维度上，并利用两个衰减因子分别刻画消息的效用随传播路径长度衰减及随时间推移衰减这两种自然特性，利用节点的历史相遇信息，得到了节点传播能力的量化分析函数，以此刻画节点对时效性消息的相对传播能力。基于快照的时序网络模型，具体方法如下：

1) 定义动态通路为在一个非递减的离散时间序列 t1⩽ t2⩽···⩽tr⩽···⩽tk(t1,tk∈T)上的顶点与连边的序列 vie1v1e2···vmervm+1···ewvj构 成节点i到节点j 的长度为 w的动态通路，当且仅当第r 个快照的邻接矩阵满足

2) 从空间维度和时间维度出发，将动态通路明确分为空间通路(在某单一静态快照中形成的通路)和时间通路(由若干个连续或不连续快照的通路组成)。

3) 考虑所有动态通路的组合，按照“长步长通路赋予较小权重，短步长通路赋予较大权重”的原则，计算动态时序网络的动态中心性指标矩阵Dt，有

展开式中，在节点的动态通路加权公式中加上n×n维 矩阵I，表示节点把消息传递给自己。同时，可以发现在同一拓扑快照内长度为 w的通路按照 βw/w!的方式衰减，利用不同拓扑快照完成的长度为 w的通路按照 βw/(l1!l2!···lr!)的方式衰减，其中w=l1+l2+···+lr表示跨越了 r个拓扑快照完成了长度为 w的通路，并在第 r 个快照中完成了 w中的lr步。

4) 由于上述衰减方式只按照通路长度对时间通路与空间通路进行衰减，并未体现节点之间产生影响的先后顺序或消息的实时性，即未考虑动态通路产生的时间先后顺序。因此考虑节点之间消息(影响)的实时性，基于“节点之间的影响强度或消息效用往往随时间推移而递减”的原则，提出了传播实时消息的关键节点发现的迭代计算公式：

式中， ∆tk+1=tk+1−tk， tk(k ∈N)表 示第 k个快照中产生的动态通路的发生时刻，值越大表示距当前时刻越近，那么该时刻的影响越重要，该时刻产生的动态通路受到较少的衰减； Qk∈n×n维矩阵表示截止到第 k个快照时动态时序网络中节点的影响力矩阵， Q0=0； Ak表示第 k个快照网络对应的邻接矩阵；α为时间衰减因子，表示对时间因素按照自然指数方式衰减； e−α∆t表示对不同静态快照中的通路按照快照产生的先后顺序进行衰减，并保证同一个静态快照中不同长度的空间通路在时间维度上的衰减程度相同。另外， Qt+11、 (Qt+1)T1分别表示节点传播、获取实时性消息的关键程度，其中1 是n×1维 向量1 = (1,1,···,1)T。应用于移动P2P 社会网络的实验结果验证了该方法的可行性，且可以明显观察到利用该方法选出来的关键节点作为消息传播的起始节点，网络消息的覆盖速率明显提升。

所述的基于随机游走的识别方法，主要有3 类：1)基于Katz 中心性的时序拓展指标，分别有传播中心性(衡量节点传递消息给其他节点的程度)、接收沟通性(衡量节点接收其他节点传递消息的程度)以及时序介数中心性(节点作为沟通网络中中介的倾向性)，该类指标主要可用于沟通网络或信息传播网络中起重要传播作用的关键节点识别；2)基于PageRank 值的时序拓展指标，除了考虑时间衰减和网络的特征的静态PageRank 值，还有一类通过将静态PageRank 的随机游走拓展到时序随机游走获得的时序PageRank 值。该时序PageRank 更能反映网络中真实的信息流动，且考虑到边分布的变化能造成节点重要性的变化，估计的是任何时间t 节点u 的重要性，同时该时序指标也很好地实现了与静态网络中PageRank 值的契合，即当网络生命周期中边分布不变时，时序PageRank 值等于静态PageRank 值；3)基于时序网络中随机游走的时序指标，此类指标脱离了静态网络中对节点重要性判断的指标，仅仅通过时序随机游走便可估计节点的重要性，其中的关键在于时序网络随机游走中转移概率、衰减因子的设定。在此基础上，计算游走达到稳态时到达对应节点的概率，以及以节点作为消息传播的起点，通过随机游走查看消息覆盖的速率，从而可获得节点的重要性衡量指标。相对基于最短路径的识别方法，基于随机游走的识别方法所考虑的信息传播路径范围不再受限于时序最短路径，也无需再考虑用路径长度最短还是时间间隔最短定义时序最短路径。

2.2.2 基于传播动力学的识别方法

目前，大多数网络传播动力学相关研究主要基于经典的流行病传播动力学模型[91-92]。真实世界中的观点、消息、疾病、恶意软件等的传播都可以建模成网络中的传染过程[93-96]，传染过程可以用于研究网络的结构特性及其组成部分的相对重要性[31]。从该角度出发，提出时序网络中表征节点传播影响力的指标，是基于网络拓扑结构识别方法的重要延伸和拓展。

文献[97]从网络结构的拓扑特征和动力学属性出发，提出了可以直接用于静态网络中有影响力传播者定位的对动力学敏感的中心性(dynamicssensitive centrality)指标，并通过在4 个真实网络中进行SIR 传播模型和SI 传播模型的拟合，发现该指标优于度中心性、k-shell 指标以及特征向量中心性。具体方法如下：

对 t>1，有

式中，I 为单位矩阵。令 H =βA+(1−µ)I，则：

因此，在时间1 和t之间节点被感染的累积概率近似为：

定义 Si(t) 为在时间t节 点i的传播影响，以节点i为初始感染节点时其他所有节点感染概率的总和表示。若 ei= (0,···,0,1,0,···,0)T是只有第i个元素为1 的 n×1维 向量，则在时间1 和t之间节点被感染的累积概率 x(t)可表示为

由此可知，以节点i为初始感染节点， x(t)实际为 βA ,βAH,···,βAHt−1的 第i列 元 素 之 和。因 为x(0)=ei且 Si(t) 是 x(t)的所有元素之和，故：

式中， L= (1,1,···,1)T是 所有元素为1 的 n×1维向量。由于 AT=A， HT=H ， AH =HA，故所有节点的传播影响可写为：

在SI 传播模型中， µ= 0时 若 t → ∞， 则 S(t)也将无穷大。

在此基础上，文献[98]将该指标拓展到时序网络，基于时间窗图模型拟合SIR 传播模型，提出了时序网络中有影响力传播者定位的时序对动力学敏感的 中 心 性 (temporal dynamic-sensitive centrality)指标，并通过在3 个真实时序网络和一个理论时序网络拟合SIR 传播模型，发现其结果优于利用静态和时序的度中心性、接近中心性、介数中心性的结果。该方法的改进在于，该指标的计算基于时间窗图模型，传播过程中的邻接矩阵是时间窗图模型中各个快照对应的邻接矩阵，而不始终是简单无向连通图对应的邻接矩阵A。具体方法如下：

用邻接矩阵 A(t)表 示第t个时间窗的快照网络，仍然假设 x(t)表 示不超过时间t节点被感染的累积概率， P(t )=x(t)−x(t −1) 表示节点在时间步t被感染的概率，其中 P(0 )=x(0)表示初始状态；假定SIR 传播模型中易感节点与感染节点接触的感染概率为β，感染节点康复的恢复概率为µ。假设只有唯一的初始感染节点i， 那么 xi( 0)=1，则有

用数学归纳法求解可得：

Si(t)表 示传播影响，即在时间t节 点i 的感染概率的总和

因为 A( t)T=A(t)， [H(t)]T=H∗(t)，所以有

式中， V= (1,1,···,1)T； S(t)即为本文所提出测量节点在时序网络中传播影响的指标。该指标值越大，说明节点的传播影响越大，则节点越重要。

基于传播动力学的关键节点识别方法并不常见，但其往往作为测量标准，评价其他识别方法的好坏。后面在时序网络中关键节点识别方法的评价指标中将进一步说明。

2.3 基于机器学习的识别方法

目前，机器学习结合复杂网络的研究逐渐增多，基于网络的机器学习算法的应用越来越广泛[99]，包括理论研究中网络的社区检测[100]、动态网络中的链路预测[101]或网络中的动态链路预测[102]，以及现实社会中水电气等供应网络中的可达性[103]，城市运输网络中的交通预测[104]等。

将机器学习方法用于网络中关键节点的挖掘也引起了大量学者的关注。如文献[105]将社会网络分析引入机器学习模型来预测P2P 行业的用户违约，首先基于知名互联网金融公司闪银所提供的大规模脱敏数据，从复杂网络的视角加以分析，然后将分析结果转化为机器学习的输入特征，用支持向量机的方法挖掘其内在的关联，从而实现利用用户的社会网络结构性质预测用户的信用情况。

此外，文献[106]也通过机器学习的方法预测了社会网络中最有力的说服者，其以时间T 为界，以在此之前的数据作为训练数据，剩余的数据作为测试数据，探索了一种基于机器学习的预测关键节点的间接方式——首先基于社会网络理论，提出社会影响 Ik、 实体相似 Rk及结构等效 Mk这3 个影响实体说服能力的影响因素；然后以此3 因素为特征，个体的决策 Dk∈(0,1)为标签，通过50 次自助采样训练决策树模型取平均值以估计个体间的说服概率：

式中， nD表示训练数据中节点的 Dk=1的数目；nL表示所达叶节点中训练数据的数目， m取P(Dk=1)是 训练数据中 Dk=1的先验概率。然后根据说服概率提出表征个体说服能力的指标值如下：

式中， pij是 所求的实体i说 服实体 j 的概率； cj表示实体i 服能力，由说服概率和其他所有实体vj∈V,的说服能力共同决定。通过幂迭代算法求解表征实体说服能力的指标值，值越大，则对应的实体越重要。

文献[55]基于用户-对象的二分网络，将数据划分为过去的时间窗和未来的时间窗，以识别并预测电子商务平台或者社交媒体平台中的关键节点，即未来流行或重要的对象(商品、对象或推文等)。具体地，考虑复杂网络中驱动节点流行性的3 个影响因子(偏好连接、最近的流行度以及衰变)，提出表征节点在未来时间流行度或重要性的预测分数模型如下：

式中， Tp表 示过去的时间窗； s0( t,Tp)表示基于过去时间窗 Tp在 时间t对 象的预测分数；λ是调整新颖性和总流行性的参数；Tuo表示用户u 消 费对象o 的时间；γ为自由参数。然后，基于过去时间窗中的数据用梯度下降算法求解出模型中的参数，迭代过程如下：

式中， ∆e表示误差。最后通过预测分数模型进行未来时间窗中对象流行度或重要度的预测，并根据准确率、新颖性、时序新颖性以及AUC 等值评价模型的好坏。该应用虽然未涉及具体的时序信息，但在一定程度上引入了时序概念，为后续开展将机器学习方法用于时序网络中关键节点识别的研究提供了参考。

2.4 其他识别方法

除以上3 类方法外，有些研究从其他视角提出了关键节点的识别方法。如文献[36]提出马尔科夫时序网络模型，没有直接给出时序网络中的Katz 中心性的静态表示，而是通过成本最低不断调整马尔科夫时序网络中边的权重以优化给定节点的Katz 中心性测度，解决的是一个关键节点识别的优化问题。

文献[107]通过对办公大楼中面对面接触的时序数据的研究，发现一种无需完全了解时序网络，便可以根据部门的组织结构，获得关键节点的方法。具体地，根据各个部门中节点在部门内的连边与在部门间的连边数量，将节点分为居住者(有更多的部门内连边)、闲逛者(有更多的部门间连边)和连接者(部门内连边和部门间连边各占一半)，其中连接者被定义为重要节点，因为他们的介数中心性更大，且在增强部门间的沟通方面起重要作用。

文献[53]结合图挖掘和序列挖掘，基于静态结构属性和时序行为属性提出了一个识别信息扩散中活跃的有价值的节点的方法。具体的流程如下：首先，建立定量的时序聚合图，在此基础上根据社区探测算法揭示结构属性，并选择活跃有价值节点的候选者，这些候选者是社区的核心且是连接两个社区的桥梁；然后，运用序列挖掘算法从活动记录中提取候选者的行为趋势；最后，通过分析行为趋势的空间-时间特征，将候选者分为活跃节点与非活跃节点，于是得到活跃的有价值的节点。该方法通过对时间行为特征的跟踪，无需分析每个网络快照的结构。因此，具有相对较低的计算成本，且不会丢失活动有价值节点识别的准确性。

鉴于很多现有的时序网络中的节点中心性指标很少考虑不同快照中节点影响的关系，而一般而言，如果一个节点连接到更多在后续的快照中有更多邻居的节点，那么该节点可能是一个更重要的传播者。文献[35]从信息论的角度将静态网络中基于熵的中心性扩展到了时序网络，定义是快照t中节点 vi的邻居集合，是 快照t中 节点 vi的邻居集合中节点的数目，定义是快照t中 节点 vi的信息，则有

由于快照t中 节点 vi的影响不仅由其邻居数决定，还受其邻居影响的影响。基于此，定义为快照t中 节点 vi的影响，则有

式中， p ∈ [0,1]， 表示 t+1时 刻的节点 vi在多大程度上决定t时刻的节点 vi的影响。该指标值越大，说明节点在快照t中影响力越大，则该节点在相应的时间越重要。特别地，由于在最后一个时间戳图中，不知道下一快照中节点 vi的邻居影响，所以认为节点 vi的影响仅由其感染的不确定性决定，即有

同时由于当 t=1时，各节点的影响考虑了相邻节点在整个时间段内的累积效应，所以作者利用t=1处各节点的影响衡量节点在计算机病毒时序网络传播过程中的重要性。

3 时序网络中关键节点识别方法的评价指标

评价时序网络中关键节点识别方法的效果有多种不同的角度，可以依据节点在网络的结构和功能中的重要性，同时也可以与其他已有指标进行对比。一般而言，网络中节点的重要性排序主要从网络性能的变化、传播效果的好坏、指标间的相关性三个角度验证。

3.1 基于网络性能变化的评价方法

网络性能是考察节点对网络结构的影响力的评价指标。节点删除法是常用的利用网络性能变化评价节点重要性的方法，其有累积删除和依次删除两种思路[108]。假设网络时序性能为 E(G )，首先按节点识别方法对节点重要性排序，再计算表征时序网络性能变化的评价指标。具体有如下思路：

1) 分别衡量节点未删除时的网络性能以及节点删除后的网络性能，然后比较两者的差值[24, 38, 45, 48]。记累积删除σ 比例节点后的时序网络性能为 E(G σ)，则计算如下：

若两者差值越大，则说明节点对网络性能的影响越大，同时也说明节点越重要，识别方法性能越好。

2) 设定网络性能的阈值，观察达到该阈值所需删除的节点比例[108-109]。记累积删除 σth比例节点后网络性能达到阈值为 Eth(G)， 即有 Eth(Gσ)=Eth(G)，则计算如下：

若删除的节点比例越少，则说明节点对网络性能的影响越大，同时也说明识别出的节点越重要，识别方法性能越好。

3) 与上面直接删除前 σ比例重要节点不同，这里按节点重要性排序依次删除网络中的节点直至网络中所有节点被删除。记节点vi删除后的网络性能为 E(G vi)，则计算如下：

该结果衡量单个节点依次移除后网络性能的变化。若值越大，说明节点越重要，同时也说明识别方法有好的性能。

目前，针对时序网络的衡量指标尚不多见，所用的方法大多是将静态网络中网络性能的变量替换为时序网络中定义的时间相关的变量。其中，较为常见的用于评价时序网络关键节点识别方法的网络时序性能指标是网络时序效率和网络时序最大连通分量：

1) 网络时序效率：时序网络中信息传播效率的衡量指标，较小的值意味着信息能够在时序网络中更快传播开。该时序性能指标来源于静态网络中的网络效率[110]，即所有节点接近中心性的均值，定义如下：

式中， dij表示节点对 (i,j)间的最短路径。在时序网络中，基于不同的时序最短距离或时序接近中心性的定义，文献[27]、文献[33]以及文献[45]将网络的时序效率定义为：

式中， dt( u,v)表 示开始时间为t的 节点对 (u,v)间的时序距离，时序距离通过时序最短路径计算。开始时间t 不同时，同一节点对 (u,v)间的时序距离也不一定相同。此外，当节点对 (u,v)间不存在时序路径时， dt( u,v)=∞。

2) 网络时序最大连通分量：衡量时序网络可达性的指标，是时序网络最大连通图中的节点数占整个网络所有节点的比例[38]。该时序性能指标来源于静态网络中的最大连通分量，即最大连通分量中节点的比例，定义如下：

① 基于时序网络模型，选取初始时间的节点u，依次遍历各个时间点直至结束，统计可到达的节点数目为| Ωu|[111]，则有

② 分别求解各快照的最大连通分量并取均值[38]，即

3.2 基于传播模型的评价方法

基于传播模型的评价方法主要考虑节点在网络信息传递中的作用。其中，常用的传播模型有SI 传播模型、SIS 传播模型和SIR 传播模型。三类模型共呈现出节点的3 种状态：易感染状态(S,Susceptible)即未来可能被感染的健康状态，感染状态(I, Infected)即患病状态，以及移除状态(R,Removed)即从感染状态恢复并具备抵抗力。

在SI 传播模型中，只存在易感染状态(S)的节点以概率β 被感染状态(I)的节点感染，即有：

在SIS 传播模型中，易感染状态(S)的节点以概率β 被感染状态(I)的节点感染，感染状态(I)的节点以概率γ 恢复成为易感染状态(S)的节点，即有：

在SIR 传播模型中，假设易感染状态(S)的节点以概率β 被感染状态(I)的节点感染，感染状态(I)的节点以概率γ 成为移除状态(R)的节点，则有：

一般而言，在时序网络中基于传播模型对时序网络的节点识别方法的效果进行评价，主要在时序网络模型中模拟这三类传播模型的时序传播。该过程与静态网络中拟合的区别在于，节点对间连边产生和消失的时序性，因此传播也需考虑连边形成的时间。具体做法为基于几种关键节点的识别方法对节点的重要性进行排序，则几种关键节点识别方法性能评判的具体思路有：其一，取相同数目最重要节点群为初始感染源，最能促进“疾病”传染的关键节点识别方法则更优；其二，取相同数目最重要节点群为免疫群体，最能阻止“疾病”传染的关键节点识别方法则更优。

关于“疾病”传染的衡量指标，即是对节点传播能力的衡量。一般而言，在SI 传播模型或者SIS 传播模型中，常常以达到稳定状态时被感染的节点数目表示；在SIR 传播模型中，常常则以能够传播的平均距离表示。与此同时，也有不少文献基于时序网络模型的特征提出了新的评价指标，如文献[31]基于真实时序数据集构建时间窗图模型拟合SI 传播模型，定义每个节点i的传播影响力为一半节点患病时间。具体方法为：假设节点i是传播源并在时间 t0,i第一次出现，其他节点都是易患病节点，到时间 ti有 一半节点患病，那么定义节点i的传播能力为

式中，Ti值越小，表示节点i 对疾病的传播能力越强，即节点i 更重要。进一步，从疾病免疫的角度提出单个节点的感染延迟率：

文献[49]提出了一种网络影响的基准方法，用TKO 分数表示。该方法结合了超级传播者和免疫过程的影响，同时还包括感染的时间，能够克服不同的测度针对具体的网络结构有效以及传统方法的不足，从而更准确地测量节点对传播的影响。具体过程如下：

1) 选择初始传播源，基于时序网络运行疾病传播模型，同时获取每个节点的状态以及每次迭代的时间。其中，感染节点的数量及感染持续的时间是基于该初始传播源的疾病量级(magnitude)。

2) 对于对应时序网络中的每个时间层的节点，实施移除操作分析。即移除某节点，运行相同的动力学模型，测量疾病量级的变化，获得该节点的基于初始传播源的边际感染分数。

3) 使用每个节点作为初始感染源，执行过程1)和2)，获得每个时间层每个节点基于不同的初始传播源的边际感染分数。取平均值作为所求的TKO 分数。

TKO 分数是一个全方面的经验度量，可以捕获到节点在每个时期影响疾病传播的潜力，常用于评估其他影响测量方法的准确性，是一种有效的基准测量方法。

此外，文献[112]基于8 个人类接触数据集构建时序网络、静态网络及全连通网络进行SIR 传播模型仿真。提出两个评估指标：灭绝时间和爆发规模。定义没有感染的个体存在时，该传染病消失，灭绝时间即为从爆发到消失的时间间隔；定义传染病消失时，恢复状态个体的比例定义为爆发规模。

3.3 基于相关性的评价方法

时序网络中的关键节点识别方法主要实现对节点重要性的排序，预测时序网络中全局最重要的节点或者特定时间层的重要节点。若设定某一基准识别方法或已知节点真实的重要性排序，则可基于相关性评价所提出识别方法的预测性能。常用的相关性评价指标有Kendall’s τ 相关系数[113]以及Spearman相关系数[114]，两者的取值范围均为[−1, 1]，值越大，相关性则越强，即说明节点重要性的排序方法更优。

文献[97]在评估所提出的时序对动力学敏感的中心性这一关键节点识别方法的性能时，在4 个时序网络中拟合SIR 传播模型，以一段时间后感染节点的数目衡量节点的传播影响，选择随机选择初始感染节点的结果为基准，同时获得根据静态度/介数/接近中心性、文献[47]提出的时序度/介数/接近中心性、时序对动力学敏感的中心性这七个指标选择初始感染节点的传播影响；然后分别计算按照七个指标选取初始感染节点的传播影响与随机选择初始感染节点的传播影响的Kendall’s τ(肯德尔系数)，发现根据时序对动力学敏感的中心性选取初始感染节点的传播影响的相关系数最大，从而得知所提出方法有更高的精度。

文献[45]在提出时序网络中的各时间层网络上节点的特征向量中心性(SSAM)的方法后，基于两个实证网络数据，用节点删除法得到节点时序全局效率差值并排序，然后利用Kendall’s τ(肯德尔系数)计算特征向量中心性与时序网络效率差值的相关性；同时按照文献[44]提出的SAM 方法选取不同的参数以相同的方法计算相应的Kendall’s τ 系数。对比可知，SSAM 方法得到的Kendall’s τ 系数结果大部分比SAM 方法的高，说明其得到节点重要性排序更为准确。

此外，在利于过去的节点重要性排序结果表征未来的节点重要性排序时，常见的有将时间t的重要节点作为下一时间 t+1的预测[47]，或划分训练集和测试集将训练集中的重要节点作为测试集的预测[55, 105]，一般在已知真实的节点重要性排序时可计算其与预测的节点重要性排序之间的相关系数，从而评价识别方法的好坏。在此情况下，准确率[106]也是常见的评价指标。其表示预测的前 K个重要节点在真实排序中的数目占比。计算如下：

式中， PK和 RK为选取预测排序和真实排序的前 K点序列。准确率越高，说明节点识别方法的性能越好。

4 结 束 语

本文在介绍时序网络建模的基础上，总结了现有主要的时序网络中关键节点的识别方法以及时序网络中针对关键节点识别方法的评价方法，为后续开展设计时序网络中节点重要性指标提供了重要参考。关于时序网络中关键节点的识别方法的总结见表1。然而，时序网络中的关键节点识别方法大多是静态网络中的中心性测度基于时序网络模型的拓展，对关键节点识别方法的评价指标也多源自静态网络。虽然此类改进确实起到了提升关键节点识别方法性能的效果，但仍然存在诸多亟待解决的问题：

1) 网络的时序演化。现有的时序网络多考虑节点和连边随时间的增加和减少，尚未考虑网络结构的巨变，如从星形网络(关键节点最好的识别方法为度中心性)到桥连通网络(关键节点最好的识别方法为介数中心性)的演化。在此情况下，简单的静态图、时间窗图模型、多层图模型或路径流模型不再能概括时序网络模型的演化特征，基于一类模型设计标准一致的关键节点识别方法也难以捕捉到不同时间的关键节点。因此，需要寻找新的网络抽象方法，同时也需要探索可以随网络结构变化而调整的关键节点识别方法。

2) 时序网络中关键节点识别方法的内在关系。

基于不同的角度获得了各种关键节点识别方法，但这些方法实际上存在一定的联系，比如前面讨论的基于特征向量的识别方法和基于随机游走的识别方法。因此可以基于多个时序数据集构建不同的时序网络模型，对比分析这些时序识别方法间的联系和区别。

表1 时序网络中的关键节点识别方法

3) 时序网络中节点重要性的定义。相对静态网络中对关键节点识别的各种中心性测度，现有的时序网络中对关键节点的识别方法大多仍然是基于时序网络模型提出的全局时序静态指标，因此忽略了节点的位置和功能随时间而变化的情形；虽然有基于特定时间层的时序指标，但忽略了网络结构随时间变化的情形。而同一类型的时序指标只能探索节点在一个层面的重要性，因此在设计时序网络中的关键节点时，可以同时结合网络结构、节点位置以及节点功能等多方面的影响因素。

4) 时序网络中基于机器学习的关键节点识别方法。随着大数据时代的到来，机器学习由于能从海量数据中挖掘出有价值的信息而逐渐呈现出巨大优势。目前，机器学习方法已被应用于静态网络的关键节点分析并取得了较好的效果，机器学习有望应用于时序网络探索关键节点的识别方法，因此可以从该角度出发进行尝试性探索与应用。

本文研究还得到S-Tech 学术支持计划−互联网传播学项目的资助，在此表示感谢。