图卷积融合计算时效网络节点重要性评估分析

周传华，操礼春，周家亿，詹凤

(1.安徽工业大学 管理科学与工程学院，安徽 马鞍山 243032；2.中国科学技术大学 计算机科学与技术学院，安徽 合肥230027；3.国家电网江苏电力营销服务中心，江苏 南京 210019；4.马鞍山学院，安徽 马鞍山 243100)

时效网络考虑节点之间交互关联关系的时间特征属性，集中分析动态演化条件下网络的拓扑结构和动力学特征，可以更加准确地解释社交通讯信息流与人类活动模式关系、电子和生物病毒传播机制、基因调控激活序列以及脑功能网络时域特征等[1-4].节点重要性评价方法根据不同视角可分为2类，即分析节点在时间分层网络结构中的局部重要性和节点在网络演化过程中的全局综合重要性.

Taylor等[5]通过多层耦合网络分析法构建超邻接矩阵（supra adjacency matrix, SAM）以表征动态时效网络层内和层间连接关系，定义了时效网络基于特征向量的中心性度量指标以及节点重要性的评价指标.经典的SAM时效网络模型利用共享参数调节层间关系，忽略不同节点层间连接关系的差异性.杨剑楠等[6]引入邻居拓扑重叠系数重新表达节点的层间连接关系，提出基于节点层间相似性的超邻接矩阵（similarity based supra-adja cency matrix, SSAM）改进的时效网络表达方法.胡钢等[7]考虑到跨层网络间的相容相似度问题，定义网络层间逼近关系系数，通过信息集结弥补邻居拓扑重叠系数的不足，提出改进的基于时效网络层间同构率动态演化的超邻接矩阵模型（isomorphism rate based supra adjacency matrix, ISAM），给出节点在各时间层的排序结果.Jiang等[8]考虑节点连接信息递延的非马尔可夫性特征，提出新的增强相似度指数（enhanced similarity index, ESI）来度量相邻层和非相邻层之间的耦合关系，并引入时间衰减因子描述不同时间层内节点间耦合强度，构建出基于衰减的SAM时效网络模型（attenuation based SAM, ASAM）.

上述方法根据节点在时间层内和层间的连接关系，通过引入和定义相关系数并进行理论推导完善时效网络动态演化过程的结构表达，提高网络节点重要性判断的准确率和有效性.将网络的结构演化过程分解为系列静态时间窗的集合，统筹分析层内和层间关联关系影响因素，量化表达节点在当前时间窗内的时序特征，可以实现各时间窗口节点重要性的测度评价，但也因此存在不同时间窗内节点重要性排序评价结果不一致的情况.

Tang等[9-10]通过时序最短路径定义时序介数中心性和时序紧密度中心性，描述网络演化过程中的消息传递控制机制，提出时效网络节点重要性综合度量方法.Kim等[11]通过跨时间复制节点交互信息表达潜在信息流向，构建基于明显路径流的时效网络模型，提出间隔时间内节点的时序度中心性、时序介数中心性和时序接近中心性指标，将静态网络中的度中心性[12]、介数中心性[13]、接近中心性[14]的概念拓展应用到时效网络中，实现对节点的全局重要性综合评价.Wang等[15]对时序度中心性概念进一步拓展，通过计算时序度中心性偏差，提出时序度偏差中心性指标.Takaguchi等[16]分析现有中心性方法存在时间间隔难以选取调整和计算效率2大瓶颈，将节点和时间戳的组合视为时序节点单元，聚焦时序路径的局部结构，提出时序覆盖中心性（temporal coverage centrality, TCC）和时序边界覆盖中心性（temporal boundary coverage centrality, TBCC），揭示节点中心性值分布的非均匀性.Ye等[17]基于k-核分解[18]在静态网络节点重要性评价问题中的优异表现，提出基于边的k-核分解方法并应用于时效网络，通过计算时间聚合图上节点与其邻域节点间连边的权重和，综合评价节点重要性.Qu等[19]提出适用于时效网络的时序信息收集（temporal information gathering, TIG）过程，探究时序结构信息对节点重要性排序结果的影响.梁耀洲等[20]引入基于评分矩阵的聚合理论，通过计算节点在各时间层内的排序得分累加和，实现节点重要性的全局综合评价.通过对静态网络节点中心性度量方法在时效网络上的改进应用，针对全局视角下的节点重要性综合评价问题给出初步解决方案，但方案的排序有效性在具体应用场景数据集上缺少更进一步的量化透视和模型的性能仿真验证.

基于上述问题以及超邻接矩阵模型建模时效网络动态演化过程，量化表达节点交互顺序和关联关系，利用图卷积神经网络[21-22]（graph convolutional network, GCN）对图结构数据的处理优势和参数优化能力捕捉空间依赖，构建基于图卷积融合计算的时效网络重要节点辨识模型（identifying critical nodes in temporal networks via SAM and graph convolution, ISGC），聚合节点邻域结构信息和时序特征，在全局维度上实现对时效网络节点重要性的综合评价.

1 定义与理论基础

1.1 时效网络符号表达

时效网络是从时间维度抽象描述个体和个体间相互作用关系的系统表示，将个体或群体单元抽象为节点，单元间的相互作用关系视为连边，单元间的关联关系具有随时间先后变化的时序特征.当网络结构发生可描述的节点和连边随时间增加或减少的系统性变化时，将变化过程称为时效网络演化.

通常可以将一个网络定义为二元组G=(V,E)，所有的网络节点构成节点集合V={v1,v2,···,vn}，节点间的关联关系构建边集合E={e1,e2,···,en}.在时效网络中，若不考虑节点交互关系发生的时长，则在整个网络演化期内的边都可以用三元组(i,j,t)来描述，表示节点i和节点j在t时刻发生一次交互事件，此时整个演化期 (t,t+N)将被划分为T个时间窗，每个时间窗大小L=N/T，得到时间窗序列 {(t,t+n),(t+n,t+2n),···,(t+(T-1)n,t+N)}和时效网络的离散网络切片序列 {G1,G2,···,Gn}；若要考虑时长，则边集元素可用四元组 (i,j,t,Δt)抽象表示节点i和节点j在t时刻产生交互并持续Δt时长.

1.2 超邻接矩阵模型

文献[5]将节点规模为N、层数为T的时效网络表示为层内连接关系和层间连接关系的耦合，用维度大小为NT×NT的分块矩阵形式进行描述，提出经典的超邻接矩阵SAM时效网络模型：

式中：超邻接矩阵A为时效网络模型；A(1),A(2),A(3)···,A(t)分别为切分的T个时间层网络内节点间的连接关系，依次位于A的对角线上，表示有序的时间层网络；邻接矩阵A(t)中的元素用ai,j(t)表示，则ai,j(t)=1为在时间层网络Gt中节点i与节点j间存在的连接关系，ai,j(t)=0 为无连接关系；ωI为相邻时间片网络层间耦合关系；ω为可调参数；I为N×N单位矩阵；因为经典的超邻接矩阵仅考虑相邻网络层节点间的连接关系，所以矩阵其他位置元素均为0.

为了更真实地反映网络连接变化规律，文献[6]引入邻居拓扑重叠系数表达层间连接关系，解决SAM模型无法利用可调参数对网络层间连接紧密程度变化进行差异化表达的问题.节点i在相邻时间层的邻居拓扑重叠系数的代数表达式为

式中：c为节点i在相邻时间层的邻居拓扑重叠系数.ai,j(t)、ai,j(t+1)分别为相邻时间层网络Gt、Gt+1对 应邻接矩阵中的元素.若在Gt中节点i与节点j之间存在连接，则ai,j(t)=1，否则ai,j(t)=0 .将ωI替换为C(t,t+1)可得SSAM时效网络模型矩阵表达式为

1.3 图卷积神经网络

卷积神经网络(convolutional neural network,CNN)[23-24]模型可以利用离散卷积在输入数据空间定义全局共享的卷积核，通过计算中心像素点、相邻像素点的加权和构成特征图，提取局部的空间特征，这只适用于在欧几里德空间，处理图像和规则网格等类型的数据.对于普遍表达应用的图结构数据，每个节点的局部拓扑结构都存在差异，导致其不再满足平移不变性，无法利用相同尺寸的卷积核执行卷积运算，提取数据拓扑空间特征.Bruna等[25]基于图谱理论利用卷积定理先对谱空间的特征信号做乘法，再通过傅里叶逆变换将信号转换到原空间，对谱域上的图卷积算子进行定义，构建出第一个图卷积神经网络，有效克服图结构数据上不满足平移不变性的局限性.构造的谱卷积神经网络并不满足局部连接特征，并且计算时空复杂度较高.Kipf等[21]利用一阶Chebyshev多项式作为卷积核，通过参数化设计，有效实现网络局部性，同时大大降低算法时空复杂度，提出图卷积神经网络的空间方法.

2 模型与方法

2.1 图卷积融合计算时效网络重要节点辨识模型

基于图卷积融合计算的节点重要性评估方法建立在时效网络数据的时空依赖关系之上.其中，时间依赖关系表示时效网络中的时序特征表达，空间依赖则表示空间信息提取.将时效网络节点重要性综合评价和排序问题分解为节点时序特征表达和空间信息提取2个阶段.

在时序特征表达阶段中，通过超邻接矩阵对时效网络进行动态演化建模，表征节点层内和层间连接的时间依赖关系，并计算节点在不同时间层的时序特征属性，构造时序特征矩阵作为下一阶段的输入；在空间信息提取阶段中，根据时效网络数据构建静态聚合网络，通过邻接矩阵描述时效网络的静态聚合拓扑结构以表征空间依赖，并将经过数据预处理后的节点时序特征作为模块共同输入，利用图卷积提取网络空间信息和节点特征，输出节点最终特征序列表示.针对模型训练过程中存在的梯度消失和节点信息丢失问题，设计添加跳跃连接机制（skip connection, SC）[26]，以提升网络表征能力.ISGC模型结构如图1 所示，主要包含3个部分，即输入层、图卷积层和输出层.

图1 ISGC 模型结构示意图Fig.1 Structure diagram of ISGC model

2.1.1 输入层 ISGC模型的输入数据集都是动态图数据，将数据按照给定时间间隔划分时间窗，得到不同时刻的无权图Gt=(Vt,E) .其 中，Vt为t时刻节点集.输入层主要任务包括时效网络超邻接矩阵模型构建和节点时序特征矩阵构造2部分.

创建空矩阵A用于存储超邻接矩阵结构，利用邻接矩阵(A(1),A(2),···,A(T))分别刻画离散时间窗图 (G1,G2,···,GT)中的节点关联关系，并将邻接矩阵依次插入空矩阵A的对角线上，构建时效网络演化建模超邻接矩阵模型.特征向量中心性[12]能够综合表达节点自身及邻域节点重要性，因此利用特征向量中心性作为节点重要性基本度量指标，即求解超邻接矩阵A的主特征向量（最大特征值对应的特征向量）m={m1,m2,···,mNT}T.将向量m记作维度为N×T的 特征矩阵则有：

式中：矩阵的第i行第t列元素wi,t为向量m的第N(t-1)+i项元素，表示第t个时间层上节点i的 特征向量中心性.最后基于特征向量中心性矩阵W，构造节点时序特征矩阵作为图卷积层输入特征.

2.1.2 图卷积层 节点的重要性程度不仅取决于节点自身的重要性，同时也由它的邻域节点决定.如何充分考虑节点邻域信息是时效网络节点重要性评估过程中需要解决的一个关键问题.针对节点在物理空间呈现出的非欧几里德式空间位置关系，ISGC模型融合图卷积张量计算框架，通过在傅里叶域构造滤波器，作用于图中节点及一阶邻域，转换聚合邻域结构信息和时序特征.对聚合后的结果进行非线性变换得到新的节点特征，最终实现节点重要性综合排序.通过多层叠加可以从更远的邻居接收信息，实现节点邻域信息的有效聚合.图卷积网络结构如图2所示，其中X为节点的时序特征矩阵，zi为节点i对应的矩阵行向量.GCN图卷积机制如图3所示，σ (x)为图卷积层的激活函数，H为隐含层特征矩阵，Y为输出层特征矩阵.

图2 谱域图卷积网络结构图Fig.2 Spectral convolutional network structure diagram

图3 谱域图卷积算子Fig.3 Spectral graph convolution operator

通过构建2层GCN图卷积神经网络模型捕捉网络空间依赖，聚合邻域节点时序特征.图卷积代数表达式为

式中：γ为一个超参数，决定x≤0时的饱和曲线.

2.1.3 输出层 为了避免不必要的节点特征信息流失，通过学习函数f获得节点重要性的综合测度，在特征提取过程中不进行图池化操作，而是直接采用全连接层输出图级别的分值向量记为O：

式中：sn为节点排序输出分值.在实验训练阶段中，计算节点对网络性能的影响力作为重要性基准评价结果.模型输出目标是节点重要性顺序结构接近基准结果，选择均方误差（mean squared loss，MSE）作为损失函数最小化两者之间的误差.

2.2 基线方法

研究采用“5+1+2”模式，选取5种基于拓扑结构的时效网络节点重要性度量方法、基于动力学随机游走的识别方法、基于排名聚合及引力模型的节点综合重要性度量方法进行性能对比.

2.2.1 时序度中心性[11]节点中心性最直接有效的度量指标就是度中心性，节点度值越大表明节点重要性越强.时序度中心性（temporal degree,TD）将节点度的概念推广到时间维度，得到时效网络中心性度量基准指标：

式中：Dt(v) 为 节 点v在 时 间 窗Gt(i≤t＜j)内 的 度值 ，|V|为节点 数量.

2.2.2 时序度中心性偏差值[15]基于时间窗图模型通过计算各时间窗内的度中心性标准差，时序度中心性偏差值（temporal degree deviation centrality, TDDC）刻画每个节点的时序度值与均值的偏离程度.偏差值越大，该节点属于网络核心关键节点的可能性越大.时序度中心性偏差计算为

2.2.3 时序接近中心性[11]接近中心性算法通过计算静态物理路径评估节点重要性，（temporal closeness, TC）则通过引入时序最短路径，拓展应用于时效网络节点重要性评估，时序接近中心性定义的计算式为

式中：Δt,j(v,u) 为在时间间隔i≤t＜j内节点v与其他节点间的时序距离.

2.2.4 时序介数中心性[11]时序介数中心性（temporal betweeness, TB）通过统计任意两点间的时序最短路径数目，计算经过目标节点的最短路径比例，评估节点重要性程度，具体代数式为

式中：σt,j(s,d) 为 时间间隔内节点s到 节 点d的最短路径总数，σt,j(s,d,v) 为 通过 节点v的最 短路 径数量.

2.2.5 时序k-核分解[17]时序k-核分解（temporalkshell decomposition, TK）通过连边权值计算聚合目标节点和邻居节点时序k-核特征，实现时效网络节点重要性度量，聚合权值越大节点越重要.节点时序k-核计算式为

2.2.6 排名聚合[20]基于排名聚合（ranking aggregation, RA）的方法通过制定评分机制，建立各时间窗口内节点的重要性评分矩阵并进行加和计算，根据加和得分获得节点重要性综合排序：

式中：g(v,u)为节点v相对于节点u的综 合得 分，g(v) 为v相对于网络其他所有节点的最终评分.

2.2.7 时序网页排名[27]（temporal page rank, TPR） 将时效网络表示为系列静态图集合，基于网络上的随机游走策略，结合时序信息和动力学提出适用于时效网络的时序PageRank方法来评估节点重要性程度：

式中：α为阻尼因子，P r′[z|t]为 特定随机游走序列发生的概率，z为游走路径，W为所有游走路径的集合.

式中：c(z|t)为在时间t之前从节点v出发到达u的游走序列集合，c(z′|t)为所有从节点v出发且与游走z的路径长度相等的游走数目.

2.2.8 时序引力模型[28]（temporal gravity model,TGM） 假设节点的中心性取决于对邻居节点的引力大小，必须满足邻居节点在结构和时序距离上都接近目标节点.将经典静态中心性度量指标及时序扩展视为质量，结合节点之间的时序距离，定义时序引力中心性，实现对节点重要性的综合度量：

式中：T G(i) 为节点i相对于邻域节点的引力中心性，Mi和Mj分别为节点i和j的属性值，di,j为节点间的时序距离，R为截断半径.

3 仿真与实验结果分析

3.1 实验网络数据

为了验证ISGC模型在时效网络节点重要性评价过程中的有效性，选用3个公开实证网络数据集Workspace[29]、Enrons[30]和SFHH[31]进行实验.Workspace是一家法国公司通过移动射频设备获得的公司员工每天面对面的交互数据，时间是2013-6-24—2013-7-3；Enrons是网络科学研究领域最常用的实证网络数据之一，主要包含美国安然公司员工之间的往来邮件数据，时间是1999—2002年，本研究截取其中2001年交互数据子集作为实验数据，SFHH是2009年法国尼斯会议中与会者之间的交互网络.数据集的基本统计特征信息描述如表1所示，其中Num为网络节点规模，Win为切分的时间窗口数量，Inter为节点间的交互次数，Static为聚合静态网络节点间的连边数量，During为数据集时间跨度.

表1 实证网络数据集的特征描述Tab.1 Empirical network data set feature description

3.2 评价方法

时效网络中的节点重要性可以从2个方面进行评价：1）从网络结构性能角度出发，考察节点移除如何影响网络连通性；2）从网络功能性角度出发，考察节点对网络传播效果的影响[6].通过计算网络中所有节点之间的距离倒数之和的均值获得网络效率[32]，可表示静态网络中信息流通的难易程度，并评判网络连通性.时效网络通过替换距离变量，定义时序全局效率[5]指标来衡量信息传播效率，表征网络时序性能：

式中：e为时序全局效率，di,j为时效网络中各节点之间的时序距离[10].时序距离指的是时序最短路径，与静态网络中的最短路径不同的是其需要遵循节点连接发生的时间先后顺序.例如信息从节点i经 过节点j到达节点k时，需要在时间维度上满足节点i和节点j之间先发生有效连接，节点j和 节点k之间后发生有效连接的条件，否则信息无法顺利传达.

为了检验ISGC方法对节点重要性的排序效果，研究采用节点删除法[33]计算节点删除后时序全局效率与原时序效率的差值Ev，量化表达网络时序性能波动，验证节点重要性.删除节点后网络性能指标波动幅度越大，说明节点越重要，计算式为

式中：ev和e分别为删除节点后的时效网络全局效率和原时效网络全局效率.通过肯德尔系数[34-35](Kendall’s τ )评估模型输出序列和时效全局效率差值序列排序的一致性程度.一致性程度越高，则模型输出序列排序精准度越高.

Kendall’s τ 在用于评估相关序列一致性程度时取值为 - 1～1.0，取值越大表明2序列一致性程度越强；反之，则表明2序列一致性程度越弱.对于2个数值序列和τ值计算式为

3.3 实验结果分析

针对实证网络公开数据集，通过本研究ISGC方法和现有方法计算得到网络节点重要性综合排序结果，并计算各方法所得排序序列与时序全局效率差值基准序列的Kendall’s τ 值，表征一致性程度，实验对比结果如表2所示.

由表2 结果可以得出：1）本研究ISGC方法在Workspace和Enrons数据集上所得节点重要性排序序列与基准序列的Kendall’s τ 相关性结果分别为0.7096和0.7644，相较于现有方法综合性能平均提高16.74%（Workspace）和22.45%（Enrons），说明在数据预处理阶段超邻接矩阵能够有效构建时序特征输入，通过图卷积融合计算机制能够有效聚合邻域节点时序特征，最终实现排序量化表达输出，实现方法有效性和精准性的提升.在SFHH数据集上，ISGC方法排序一致性低于TD和TGM，但是一致性值接近0.7，并且优于其他方法，说明该方法具有相对优势.2）RA方法在Workspace数据集上表现效果优于TD、TC和TK，而在Enrons数据集上弱于TD和TC，接近TK；TB方法在Workspace数据集上表现优于TC，而在Enrons数据集上弱于TC；TD和TC在实验数据集上表现效果差异较大，而在TDDC上则是均表现最差.TGM在数据集上均表现优良且优于TPR算法，而在Workspace和Enrons上弱于ISGC方法.ISGC输出序列与基准序列的排序一致性均高于或接近0.7，由于ISGC相比于现有方法具有反馈机制作用优势，能够自适应调整优化模型参数，在不同数据集上都具有良好的应用泛化性和鲁棒性.

表2 ISGC和现有方法排序与基准排序的相关性对比结果Tab.2 Correlation comparison results of ISGC and existing methods with the benchmark sort

根据图4实验结果可以发现：当层间关系可调参数 ω取值不同时，ISGC模型输出序列与全局时序效率差值序列排序一致性也会随之波动.在Workspace数据集上，当 ω=0.2时，一致性比较结果Kendall’s τ呈现谷值；在Enrons数据集上，当 ω=0.8时，出现一致性结果谷值.考虑通过参数 ω对输入时序特征的优化机制与模型的反馈调优机制联合作用，寻求最优 ω表达层间连接关系，使得模型序列输出逼近全局时序效率基准序列，获得排序一 致性满意解.

图4 相邻层间耦合关系可调参数 ω 对ISGC与基准排序的相关性影响Fig.4 Influence of tunable parameters ω of coupling relation between adjacent layers on correlation between ISGC and benchmark sort

3.4 算法复杂性

TD算法的时间复杂度为O(|V|+|E|)，TK算法和TDDC算法的复杂度均为O(R)，R=j-i.TC算法 复 杂 度 为O(R|V|2) ，TB算 法 复 杂 度 为O(R3|V|3).TPR算法每次交互更新的时间开销为O(1)以及TGM算法复杂度为O(R|V|2).综上所述，本研究ISGC算法计算时间复杂度相对较低，有利于在大规模网络上的泛化应用.

4 结语

针对动态时效网络演化节点重要性辨识进行系统建模分析，提出基于时效网络结构超邻接矩阵和图卷积神经网络数值计算系统模型.模型具体应用超邻接矩阵特征向量中心性指标辨识网络节点重要性.基于深度学习框架张量，计算节点最终特征序列表示和排序结果，分析评估时序全局效率差值，评价节点对网络连通性影响力，综合评测网络全局节点重要性序结构.实验结果表明基于图卷积融合计算的时效网络节点重要性评估和排序分析是科学有效的.

基于图卷积融合计算的时效网络节点重要性评价方法，等间距划分时间窗，依据节点在相邻时层的交互关联关系提取初始时序特征.现实时效网络受网络内外环境及其他因素影响，节点重要性结构演变并非按照时间均匀分布，更多表现为非线性、随机性，下一步研究计划围绕柔性时间窗口提取与划分和跨层交互关联逻辑演化表征作为核心工作.