时序网络是当前动态复杂网络特征多属性研究的重要领域，时序网络可以更加准确地描述网络演化进程，刻画现实生活中存在的生物网络、社交网络、交通网络和蛋白质网络等^[1-5]复杂网络系统的时序演化交互关系. 时序网络研究始于静态网络，经典静态网络节点重要性序结构的研究方法有度中心性^[6]、介数中心性^[7]、特征向量中心性^[8-9]等. 杨松青等^[10]结合节点K-shell中心性和结构洞特征，提出基于Tsallis熵的复杂网络节点重要性评估方法. Lu^[11]利用相对熵并引入灰色关联度量曲线边缘耦合度，提出基于结构洞和改进TOPSIS的节点重要性评估方法. 苏晓萍等^[12]提出基于节点及其邻域结构洞的局部中心性测量方法，可以准确地评价节点传播能力. Zeng等^[13]考虑节点混合度和剩余度，提出混合度分解方法. Sun等^[14]提出基于熵的自适应节点重要性评估方法，客观地评估节点重要性. 杨杰等^[15]提出基于覆盖范围和结构洞影响力最大化算法，挖掘使信息在网络中传播范围最大化的种子节点.

时序多层网络节点重要性辨识是目前网络系统研究的难点，对时序网络中节点的时序化分层提取属性特征，可以有效地表征动态复杂网络的演化过程，揭示动态复杂网络的拓扑结构与动力学系统的内在规律. 在现实生活中，网络包含时间属性，网络节点活跃程度随着时间不断变化. 时序网络节点全时间段内的属性信息变更规律及节点全时间段内的重要性排序结果较静态网络的准确性更高. Kim等^[16]将时序图转化为有向静态网络，定义有向时序网络度中心性、介数中心性和紧密度中心性. Taylor等^[17]考虑网络多层耦合的方法，分析网络时间层内和层间关系，建立超邻接矩阵，定义基于特征向量中心性指标和节点重要性的评判指标(SAM). 杨剑楠等^[18]使用邻居拓扑重叠系数对层间关系进行度量，计算相邻层间的相似性，提出基于节点层间相似性的超邻接矩阵时序网络节点重要性识别方法. 笔者等^[19]提出基于时序网络层间同构率动态演化的超邻接矩阵建模重要节点辨识方法，分析时序网络多时间层内节点交互信息对节点重要性排序的影响. 曹连谦等^[20]分析节点异质性、层间耦合、层内耦合对网络能控性的影响，给出网络系统能控的充分条件或必要条件.

时序网络领域研究取得初步成果，应注意到在动态多层复杂网络的时序演化过程中，不同时序网络层间节点交互关联信息集结存在冗余，同一时间段内多层网络、层与层之间、层内之间的关联关系存在冗余. 为了有效地剔除动态网络时序演化的大量冗余交互关联信息，提高时序网络节点重要性的辨识准确性，本文提出熵值结构洞时序网络（entropy-valued structural holes temporal networks, ESHT）节点重要性辨识模型. 给出时序网络K-shell广义邻接信息熵、熵值投入比、熵值结构洞等相关定义. 提出熵值结构洞模型，给出相应的算法. 利用SIR模型与Kendall相关系数进行验证，说明模型的有效性及优越性.

时序网络节点的重要性排序结果在不同时间层内是动态变化的. 在静态多层网络中，节点的邻接信息熵可以提供准确的节点重要性排序信息. 将其延伸至时序网络，则节点在相邻时间层和多个连续时间层内的交互关系会随着时间的推进而不断间断和重连，网络拓扑结构不断演化，如图1所示，静态网络无法描述这一过程. 本文针对动态多层无向无权时序网络节点的重要性进行演化分析，使用邻接度和邻接度概率函数表征节点属性信息. 基于网络K-shell分解，构建K-shell广义邻接信息熵. 本文提出节点熵值结构洞重要性序结构辨识方法，并延伸至时序网络，提出对应的时序网络节点重要性辨识模型.

节点邻接信息熵通过研究节点及其直接和间接节点间交互关联关系，利用节点信息熵刻画不同节点在网络中局部影响力的重要性. 网络节点交互关联属性信息通过局部信息熵集结表述更加精准.

设无向网络 $G = \left( {V,E} \right)$( $ V = \left\{ {{v_1},{v_2},{v_3}, \cdots ,{v_n}} \right\} $)为网络中的节点集合, $\left| V \right| = n$, $E = \left\{ {{e_1},{e_2},{e_3}, \cdots ,{e_m}} \right\} \subseteq $ $V \times V$为边的集合, $\left| E \right| = m$. 节点 $i$的度值可以表示为 $ {k_i} =\displaystyle \sum\nolimits_{j \in G} {{a_{ij}}} $，其中

$ {a}_{ij}=\left\{ { \begin{array}{c}1,\text{ }i与j有边相连;\\ 0,\text{ }i与j无边相连.\end{array} } \right.$

邻接度为

(1) $ {Q_i} = \mathop \sum \limits_{\omega \in {\varGamma _i}} {k_\omega }. $

其中 ${\varGamma _i}$为节点 $i$的邻居节点集合.

邻接度概率函数为

(2) $ {P_i} = \frac{{{k_i}}}{{{Q_j}}};{\text{ }}j \in \varGamma \left( i \right). $

信息熵^[21]由香农在1948年提出，指出任何信息都存在冗余，冗余大小与信息中每个符号的出现概率或不确定性有关. 利用概率与统计的方法，表征样本空间所体现的无序化程度.

(3) $ {H_i} = - \mathop \sum \limits_{i=1}^n {P_i^{'}}{\log _2}\;{P_i^{'}}. $

式中： ${P_i^{'}}=k_i/\displaystyle\sum\nolimits_{{i=1}}^{{n}}{{k_i}} $.

节点邻居概率函数. 为了描述不同节点的邻居节点对节点的影响力大小，根据信息熵理论，定义节点邻居概率函数如下：

(4) $ {{\rm{NP}}_i} = - \mathop \sum \limits_{j \in {{{\varGamma }}_i}} {P_i}{\log _2}\;{P_i}. $

广义邻接信息熵为

(5) $ {{\rm{NH}}_i} = - \mathop \sum \limits_{j \in {\varGamma _i}} {P_j} {{P_i}{{\log }_2}\;{P_i}} . $

节点邻接信息熵通过集结网络节点多属性度偏好信息，比较全面有效地表征网络各个节点的重要性权重.

K-shell分解的核心思想是将整个网络划分为从边缘至核心的不同层次，递归地删除网络中节点度值小于或等于 $k$的节点，记录被删除节点的K-shell（简称K_s）值. K-shell分解有利于大型复杂网络节点的快速分类计算. 如图2所示为K-shell分解的具体划分步骤. 1）删除网络中所有度为1的节点，若删除完成后网络内继续出现度为1的节点，则继续上述删除过程，直至网络中不出现度为1的节点，此时将已删除节点的 $K_{\rm{s}}$记为1. 2）删除网络中节点度为2, 3, 4,···的节点, $K_{\rm{s}}$值分别记为2,3,4,···，直到网络中的所有节点都被赋予对应的 $K_{\rm{s}}$. 如图2所示为 $K_{\rm{s}} = 3$的分解过程, $K_{\rm{s}} = 1$的节点包括1、2、3、4、5、6、9、14、16、17， $K_{\rm{s}} = 2$的节点包括7、8、15， $K_{\rm{s}} = 3$的节点包括10、11、12、13.

节点的广义邻接信息熵表征各个节点在网络中不同层间的局部交互关联信息. 在时序网络演化过程中，节点会被网络局部信息影响，网络整体关联信息对每个节点的演化进程起到主导作用. K-shell分解是对网络整体信息等级划分处理的方式，节点 $K_{\rm{s}}$值表征网络节点位置属性，大量节点被赋予相同的 $K_{\rm{s}}$，使得节点间区分度变低. 基于以上信息，提出K-shell广义邻接信息熵，结合网络邻接节点交互关系，通过熵值实现局部属性到整体属性的跨越. 应用K-shell分解，有效地提高层内层间交互关联信息的整体可靠性.

K-shell广义邻接信息熵为

(6) $ {{\rm{KH}}_i} = - \left( {{{\rm{e}}^k}} \right)\mathop \sum \limits_{j \in {\varGamma _i}} {P_j} {{P_i}{{\log }_2}{P_i}} . $

式中： ${\rm{e}}$为自然常数， $k$为节点 $i$在该网络中的 $K_{\rm{s}}$.

结构洞^[22]是Burt研究人际关系网络的经典社会学理论，从社会学角度来看，结构洞通常表示非冗余联系. 图3中，Kev与A、B、C之间任意两者的关系是一个结构洞. A和B与Kev都有联系，但是二者之间不存在关系，相当于存在一个空洞. Kev充当起中间人的角色，为Kev获取“信息利益”和“控制利益”提供机会，较网络中其他位置上的节点具有更高的重要性.

Burt为了衡量网络节点形成结构洞时所受到的约束，提出网络约束系数^[22]：

(7) $ {C_i} = \mathop \sum \limits_{j \in {\varGamma _i}} {\left( {{p_{ij}}+\mathop \sum \limits_q {p_{iq}}{p_{qj}}} \right)^2};{\text{ }}q \ne i,j. $

式中：节点 $q$为节点 $i$和节点 $j$的共同邻居； ${p_{ij}}$为节点 $i$连接节点 $j$付出的总精力占比，

(8) $ {p_{ij}} = \frac{{{a_{ij}}}}{{\displaystyle\mathop \sum \nolimits_{j \in {\varGamma _i}} {a_{ij}}}}. $

如图4所示，计算节点 $i$的约束系数. 可知，节点 $i$的邻居节点集合 $ {\varGamma _i} = \left\{ {A,B,C,D,E,F} \right\} $，其中i和A的共同邻居有 $\left\{ {B,E,F} \right\}$，于是有

$ \begin{split} &\displaystyle\mathop \sum \limits_{q \in \left\{ {B,E,F} \right\}} {p_{iq}}{p_{qA}} = 1/6\times 1/3 + 1/6\times 1/2 + 1/6\times 1/4 = 11/72，\\ & C_{iA} = (1/6+11/72)^2. \end{split} $

同理可以继续求得 ${C_{iB}}$, ${C_{iC}}$,···，求和后可得 ${C_i}$. 在网络约束系数的计算过程中，考虑每个节点度和网络邻居节点拓扑的关系，网络约束系数越大，表示该节点的紧密度越高，节点在新的关系资源竞争中可能处于不利地位. 网络约束系数越小，使得该节点拥有较高的度和较低的紧密度，则该节点有更高的结构洞性质.

结构洞理论为寻找网络中的重要枢纽节点提供理论基础. 结构洞计算结合网络中节点的自身度和所计算节点的共同邻居数目，计算出每个节点与共同邻居节点间的贡献程度，得到每个节点的结构洞约束系数. K-shell邻接信息熵可以快速约简，加速网络分层分块，但K-shell信息熵带来较多的冗余信息. 为了有效地解决节点信息的冗余性问题，基于结构洞投入比提出节点熵值投入比：

(9) $ {{\rm{Hp}}_i} = \frac{{{{\rm{KH}}_i}}}{{\displaystyle\mathop \sum \nolimits_{v \in {\varGamma _i}} {{\rm{KH}}_v}}}. $

网络K-shell分解得到节点 $K_{\rm{s}}$值，大量节点被赋予相同的属性值，使得节点在分类后网络一阶邻居节点的属性特征相同，导致网络广义邻接信息熵相同，故在网络中部分节点的K-shell广义邻接信息熵值相等. 为了提升网络节点重要性的分辨效率，引进网络节点与邻居节点，计算节点与其邻居节点K-shell广义邻接信息熵比值，细化节点信息表征.

基于结构洞理论，提出节点熵值结构洞：

(10) $ {{\rm{HC}}_i} = \mathop \sum \limits_{j \in {\varGamma _i}} {\left( {{{\rm{KH}}_i}+\mathop \sum \limits_{j \in {{{\varGamma }}_i}} {{\rm{Hp}}_i}{p_{ij}}} \right)^2}. $

时序多层网络熵值结构洞在计算过程中，将结构洞投入比转换成节点K-shell邻接信息熵投入比，节点K-shell邻接信息熵信息包含网络整体拓扑结构属性和节点局部拓扑信息属性，使得节点在网络全局计算上更加精准.

熵值结构洞的时序化网络节点重要性计算考虑节点累计效应的影响，将时序多层网络节点在每个时间层内的排序结果进行归一化无量纲处理. 基于以上分析可知，时序网络节点熵值结构洞的重要性系数为

(11) $ {{\rm{THC}}_i} = \mathop \sum \limits_{t = 1}^{{T}} \frac{{{{\rm{HC}}_i}^t}}{{\displaystyle\mathop \sum \nolimits_{i = 1}^N {{\rm{HC}}_i}^t}} . $

式中： ${{\rm{HC}}_i}^t$为节点 $i$在时间层 $t$的熵值结构洞系数， $N$为网络节点总数， $T$为网络时间层总数.

式（11）中 $t = 1$时表示第1个时间层内节点 $i$熵值结构洞系数. 由于第1个时间层内的节点未进行累计结果，当前时间层内的节点重要性排序结果等于节点熵值结构洞排序结果.

式（11）中 $t = 2$时表示第1个时间层和第2个时间层内节点 $i$熵值结构洞系数的累计结果. 由于节点熵值占比信息在时间层内进行累计， $t = 2$时节点重要性的排序结果与 $t = 1$时相比，节点重要性排序结果发生明显变化.

式（11）中 $t = T$时表示第1个时间层至第T个时间层内节点 $i$熵值结构洞系数的累计结果.

熵值结构洞计算节点在时序网络中的活跃性系数，根据熵增定律可知，在确定时间层划分长度的情况下，每个时间层内的熵总值为定值. 计算时间层内节点熵值结构洞系数在本层内的占比，可以直观地表述该节点在本层的活跃性占比. 网络时间层依据时间间隔进行均值划分，单一时间层的时间长度比例相等，节点随着时间推进演化，累计节点熵值结构洞系数占比更加合理. 熵值结构洞时序网络计算模型反映节点在一个或多个时间层内节点重要性排序结果的演化规律，避免单一时间层节点活跃性突变导致重要性排序在短时间内发生巨大变化，降低节点影响力突变效应在全时间层内的消极影响.

使用SIR传播模型，模拟真实网络节点受到感染后的传播过程，统计在时序网络层内稳定状态下的免疫节点数量，计算该节点在当前时间层内的影响力大小. SIR模型将网络中的节点分为以下3类. 1)易感者，其数量记为 $S\left( t \right)$，表示 $t$时刻健康但缺乏免疫力的节点. 2)感染者，其数量记为 $I\left( t \right)$，表示 $t$时刻被感染成为病人并且具有传染能力的节点. 3)免疫者，其数量记为 $R\left( t \right)$，表示 $t$时刻已经痊愈并且获得免疫能力的节点或已经死亡、不再对相应动力学行为有影响的节点. 设总人口为 $N\left( t \right)$，则有 $N\left( t \right) = S\left( t \right)+I\left( t \right)+R\left( t \right)$. 传染率 $\;\beta $为2个人接触后被感染的概率，无论其是否为易感者. 治愈率 $\gamma $为一位感染者被治愈为免疫者的概率. SIR模型的微分方程如下：

(12) $ \left. {\begin{array}{*{20}{l}} {\dfrac{{{\rm{d}}S\left( {{t}} \right)}}{{{\rm{d}}t}}{{ = - \lambda I}}\left( {{t}} \right){{S}}\left( {{t}} \right)}, \\ {\dfrac{{{\rm{d}}I\left( {{t}} \right)}}{{{\rm{d}}t}}{{ = \lambda {{I}}}}\left( {{t}} \right){{S}}\left( {{t}} \right){{ - \eta {{I}}}}\left( {{t}} \right)}, \\ {\dfrac{{{\rm{d}}R\left( {{t}} \right)}}{{{\rm{d}}t}}{{ = \eta {{I}}}}\left( {{t}} \right)}. \end{array}} \right\} $

实验采用Workspace数据集和Email-Eu-core数据集，验证时序多层网络熵值结构洞节点重要性的排序结果. Workspace数据集^[23]是2013年6月24日至7月3日在法国一栋办公楼测量到的个人之间面对面交互联系数据集. 面对面接触记录是按照交流时长进行统计，每个场景的总时长不同，因此Workspace数据的单位时间层划分长度为“一天”，即每个时间层的时间范围是24 h. Email-Eu-core数据集^[24]利用欧洲一家大型研究机构的电子邮件数据生成的网络数据集，电子邮件时序网络数据包含986个匿名ID在历时803天中产生的交互信息，本文以30 d为一个时间尺度进行划分，截取其中360 d的交互信息进行仿真实验. 网络的基本特征如表1、2所示. 表中， $T$为切分的网络层数， $N$为网络节点数目， $ N _{\rm{a}} $为当前时间层内有连边的节点数， $ E $为当前时间层内整个网络的连边数， $\left\langle k \right\rangle $为网络平均度， $\left\langle {{k^2}} \right\rangle $为网络二阶邻居平均度，β_th为传播阈值.

假设传染者为节点 $i$，开始时刻只有该节点一个传染者，剩余节点均为易感者. 在设定传播率 $\;\beta $时， $\;\beta $过大或过小都无法衡量每个节点的传播能力. 设定的传播阈值^[25]为 $\;{\beta _{{\rm{th}}}} \approx \left\langle k \right\rangle /\left\langle {{k^2}} \right\rangle $. 为了保证传播过程的正常进行，本文的 $\;\beta $大于 $\;{\beta _{{\rm{th}}}}$. 对每个节点进行1 000次模拟仿真实验，传染者节点 $i$在当前层内传染后，最终的免疫者数量取1000次实验结果的期望值. 不同网络时间层内节点 $i$的邻居节点数和邻居节点信息熵可能不同，故节点 $i$在每一层实验仿真的排序结果都会有所差异.

实验采用肯德尔相关系数(Kendall’s $\tau $)^[26]，对时序网络熵值结构洞排序结果和单位时间层内SIR传播模型结果进行相关性分析. Kendall’s $\tau $相关系数用来衡量各指标两变量序列之间的相关性程度，表达式为

(13) $ \tau = \frac{{\displaystyle\mathop \sum \nolimits_{i < j} {\text{sgn}}\left[ {\left( {{x_i} - {x_j}} \right)\left( {{y_i} - {y_j}} \right)} \right]}}{{\sqrt {\left[ {\dfrac{{n\left( {n - 1} \right)}}{2} - {n_1}} \right]\left[ {\dfrac{{n\left( {n - 1} \right)}}{2} - {n_2}} \right]} }} . $

式中： ${\boldsymbol{X}} = {\left[ {{x_1},{x_2}, \cdots ,{x_n}} \right]^{\rm{T}}}$, ${\boldsymbol{Y}} = {\left[ {{y_1},{y_2}, \cdots ,{y_n}} \right]^{\rm{T}}}$，X和Y中元素的节点熵值按从大到小的顺序排列； $n$为序列长度，即节点总数；

$ {n_1} = \mathop \sum \nolimits_i {t_i}\left( {{t_i} - 1} \right)/2,\;{n_2} = \mathop \sum \nolimits_j {u_j} \left( {{u_j} - 1} \right)/2,$

其中 ${t_i}$为 $X$序列中第 $i$个使得 ${\text{sgn}} \;z = 0$的 ${x_i}$的个数， ${u_j}$为 $Y$序列中第 $j$个使得 ${\text{sgn}}\; z = 0$的 ${y_j}$的个数. $\tau $的取值为 $\left[ { - 1,1} \right]$，该值越大，两序列的相关性越强；反之，则两序列的相关性越弱.

为了验证本文方法的有效性，基于实证网络数据集，使用SIR模型得到节点免疫数量排序分析, 利用 $\tau $评估排序相关性. 利用本文ESHT方法与SAM方法、OSAM方法^[27]开展仿真比较，时序网络中SAM和OSAM节点重要性辨识方法均是依托超邻接矩阵计算网络节点特征向量中心性大小，对节点进行重要性排序. SAM方法使用固定参数表征相邻时间层内的关系，取 $\omega \in \left\{ {0.1,0.2, \cdots ,1.0} \right\}$，且只考虑当前时间层与相邻时间层的关系. OSAM方法在SAM的基础上，考虑不同时间层对当前时间层内节点重要性序结构的叠加信息演化影响. 具体的实验结果如图5~8所示.

根据实验结果分析，可得如下结论. 1) 如图5、6所示，ESHT方法在Workspace数据的部分时间层内τ有所提高，与SAM方法和OSAM方法相比，在整个时域内τ的提升比例分别为11.178%和29.776%. 在部分时间层中，ESHT方法的结果表现不如其他方法，这是由于数据本身的特性所导致的. 2) 如图7、8所示为Email-Eu-core数据实验结果，ESHT方法在全时域内的结果都有明显的提高. 3) 时序化网络的τ在整个时域内有所下降，这是由于SIR结果的序结构没有进行时序化处理所导致的，随着时间的推移，这种误差效应将更加明显.

本文提出熵值结构洞时序网络的节点重要性序结构辨识方法，可以有效地对复杂网络中的节点重要性进行排序. 该方法综合考虑了网络节点局部信息熵属性变化和节点K-shell全局拓扑信息，利用时序网络计算模型将网络节点时序化，揭示了节点重要性序结构随时间的演化规律，通过仿真建模分析验证了相关结论. 未来应进一步探讨动态多层网络熵值结构洞节点重要性的辨识方法，并将其推广到时序演化节点重要性的预测分析中.