ISSN 
-
时序网络考虑了节点之间交互的时间、先后顺序和频率，能够更准确地刻画如社交、通信等具有时间属性复杂系统的交互关系[1-5]。传统静态网络的节点重要性研究方法有很多，如度中心性、介数中心性、接近度中心性、特征向量中心性等[6-8]。文献[6]从网络结构和传播动力学角度，对现有的复杂网络当中的节点重要性排序方法进行了系统的归纳和总结。文献[9]综合网络结构和传播动力学特征进行耦合分析，利用差分方程评估传播过程来对节点重要性进行排序。文献[10]考虑节点邻居的影响，提出了一种基于迭代邻居信息的节点重要性评估方法。文献[11]通过分析节点的位置重要性和网络中所有节点之间的依赖关系，提出了一种基于多重影响矩阵的节点重要性评估方法。文献[12]引入熵变理论，将节点的重要性定义为网络的熵值在移除节点前和移除节点后的变化，利用移除节点对网络熵值的变化对节点的重要性进行排序。文献[13]建立复杂网络动力学模型的偏离均值和基于偏离均值的方差两级节点重要性评估标准，给出了扰动测试和破坏测试两种基于复杂网络动力学模型的节点重要性评估方法。
然而，时序网络不同于传统的静态网络。由于考虑了时间因素，时序网络中节点交互会随时间的推移产生和消失[5, 14]。近年来，有关时序网络节点重要性的研究越来越多。文献[15]在构建网络时引入时序最短路径，定义了时序介数中心性、时序接近度中心性等指标。文献[16]在静态网络基于节点边缘贡献度评价节点重要性的基础上，考虑网络的时间属性并提出节点的感染方式，提出了时序社交网络重要节点的排序算法。文献[17]基于PageRank算法提出指向页面的链接越多，排名越高的思想，分析节点与节点之间的指向关系，提出了一种NodeRank算法来识别时序社交网络中的重要节点。文献[18]考虑了时序网络的动态变化，将动态中心性概念扩展到时间网络来对时序网络的节点排序。文献[19]从时序网络的建模方法、时效网络的结构特性、时序网络与人类行为结合的统计特性与处理时序网络的理论方法等方面对时序网络当前的研究进展进行总结和归纳。文献[20-21]从各时间切片网络之间的层间关系的角度对节点在各个时间切片网络的重要性进行评价，为时序网络节点重要性的研究提供了新的思路。文献[22]应用TOPSIS方法对时序网络层间关系进行选择，挖掘时序网络中的重要节点。
上述研究综合评价了不同的节点重要性评价指标在各时间切片网络的表现。然而，针对某一特定指标，当评价整个时序网络中的节点时，仍存在节点在不同时间层排序不一致的情况。本文引入了一种基于评分矩阵的排名聚合(ranking aggregation, RA)方法[23]来解决这一问题。本文通过构建基于层间相似性的超邻接矩阵，利用特征向量中心性计算出每个时间切片网络上的节点重要性排序。引入基于评分矩阵的排名聚合方法，建立每个时间切片网络的评分矩阵并进行聚合，计算每个节点的总得分来评价节点的重要性。
HTML
-
通常一个时序网络可以表示为
$G = (V{\rm{,}}{E_{(i,j)}})$ ，其中所有节点集合$V{\rm{ = \{ }}{v_{\rm{1}}},{v_{\rm{2}}},\cdots ,{v_N}{\rm{\} }}$ ，${E_{\left( {i,j} \right)}}$ 表示节点在$[i,j]$ 时间段内的连边，若将时序网络按时间切分成T个时间切片网络，则被切分的时间切片网络分别用${G_1},{G_2},\cdots ,{G_T}$ 表示。针对上述时序网络，本文的基于排名聚合的时序网络节点重要性度量方法具体步骤如下：1)建立基于层间相似性的超邻接矩阵(SSAM)时序网络模型
为了考虑同一节点与其他节点在相邻时间切片的连接关系和持续连接度，文献[21]提出了基于层间相似性的超邻接矩阵(SSAM)时序网络模型，SSAM为
$NT \times NT$ 的分块矩阵，那么对于一个给定节点数为N的时序网络$G$ ，其切分的有序时等间切片网络集合为$G{\rm{ = }}\left\{ {{G_1},{G_2},...,{G_T}} \right\}$ ，T为切分的时间切片总数，具体表示为：式中，A为基于节点层间相似性的超邻接矩阵；
${ A^{(t)}}$ 表示$t(1 \leqslant t \leqslant T)$ 时刻对应的时间切片内连接关系，这里用$N \times N$ 的邻接矩阵表示；$c_i^{(t - 1,t)}$ 表示两个相邻时间切片间的连接关系，即${ C^{(t - 1,t)}}{\rm{ = }}{\rm{diag}}$ $ (c_1^{(t - 1,t)},c_2^{(t - 1,t)},c_3^{(t - 1,t)},\cdots,c_N^{(t - 1,t)})$ ，其中$c_i^{(t - 1,t)}$ 为节点的邻居拓扑重叠系数[16]，即节点在${G_{t - 1}}$ 时间切片网络上与${G_t}$ 时间切片网络的共同邻居数所占的比例。2)利用特征向量中心性计算节点在各时间切片网络的排序
特征向量中心性是评估网络节点重要性的一个重要指标[6]，本文采用特征向量中心性这一指标对SSAM求解，得到最大特征值对应的特征向量
$ v = \left\{ {{v_1},{v_2},\cdots,{v_T}} \right\}$ ，${v_1},{v_2},\cdots,{v_T}$ 分别代表T时间片段上各时间切片的节点重要性得分，向量长度为N。根据重要性得分得到节点在各时间切片上的排序。3) 基于评分矩阵的排名聚合方法评价节点
当评价整个时序网络中的节点时，存在节点在不同时间层的排序不一致的情况。文献[23]介绍了一种基于评分矩阵的排名聚合方法。该方法以排序靠前得分、排序靠后不得分的逻辑制定得分规则，建立评分矩阵后对矩阵进行聚合，根据聚合后的矩阵对节点进行综合评价。
首先建立各时间切片网络的评分矩阵
${{{X}}_t}$ ：评分矩阵${{{X}}_t}$ 是指根据排名来确定节点之间的比较关系的矩阵，该矩阵为$N \times N$ 型的非对称矩阵，这里评分矩阵${{{X}}_t}$ 中的$x_{(v,u)}^t$ 由节点${a_v}$ 和节点${a_u}$ 在第$t(1 \leqslant t \leqslant T)$ 个时间切片排序顺序决定，其规则为：然后聚合各时间切片网络评分矩阵X：本方法将各时间切片网络建立的评分矩阵相加得到时序网络的节点排名的评分矩阵X，其具体表示为：
式中，
${{{X}}_t}$ 为t时刻对应的评分矩阵。最后计算时序网络中节点
$v$ 的排名得分${g_v}$ ：计算节点$v$ 与节点$u \in V\backslash v$ 的综合得分${g_{(v,u)}}$ ，然后将结果求和得到节点的总得分${g_v}$ ，具体表示为：式中，
${g_{(v,u)}}$ 表示节点$v$ 与节点$u \in V\backslash v$ 的综合得分。这里用节点$v$ 与节点$u \in V\backslash v$ 排序比较中排序靠前与排序靠后的得分差来表示，即${g_{(v,u)}} = {x_{(v,u)}} - {x_{(u,v)}}$ 。 -
为了验证本文方法的有效性，本文采用时序网络当中3种常用的中心性度量指标：时序中心度(temporal degree, TD)、时序接近度中心性(temporal closeness, TC)、时序介数中心性(temporal betweenness, TB)[15]；3种静态网络中心性度量指标[6]：度中心性(degree centrality, DC)、接近度中心性(betweenness centrality, BC)、介数中心性(closeness centrality, CC)进行对比分析。6种网络中心性度量指标的基本定义如表1所示。
方法 定义方式 符号说明 TD ${D_{i,j}}(v) = \frac{{\displaystyle\sum\limits_{t = 1}^j {{D_t}(v)} }}{{(\left| V \right| - 1)(j - i)}}$ ${D_t}(v)$为$v$节点在${G_t}(i \leqslant t < j)$上的度，$\left| V \right|$为节点集合 TC ${C_{i,j}}(v) = \displaystyle\sum\limits_{i \leqslant t < j} {\displaystyle\sum\limits_{u \in V\backslash v} {\frac{1}{{{\Delta _{t,j}}(v,u)}}} } $ ${\Delta _{t,j}}(v,u)$表示时间间隔$[t,j]$ $(i \leqslant t < j)$节点$v$与其他节点$\mu \in V\backslash v$之间的时序距离[24] TB ${ {B}_{i,j} }(v)=\displaystyle\sum\limits_{i\leqslant t < j}{\displaystyle\sum\limits_{ s\ne v\ne d\in V \\ { {\sigma }_{t,j} }(s,d) }{\frac{ { {\sigma }_{t,j} }(s,d,v)}{ { {\sigma }_{t,j} }(s,d)} } }$ ${\sigma _{t,j}}(s,d)$表示在节点$s$到节点$d$路径中所有的最短路径数。${\sigma _{t,j}}(s,d,v)$表示在节点$s$到节点$d$
路径当中，通过$v$节点的最短路径数量.DC ${D_{(v)}} = \displaystyle\sum\limits_{u \in G} {{a_{vu}}} $ $avu$为节点$v$与节点$u$的关系，若节点$v$与节点$u$存在连边，则$avu$为1，否则为0 BC ${B_{(v)}} = \frac{1}{{{N^2}}}\displaystyle\sum\limits_{p,q} {\frac{{n_{pq}^v}}{{{g_{pq}}}}} $ $N$为节点数目，${g_{pq}}$为节点$p$到节点$q$的最短路径的的数目，$n_{pq}^v$为${g_{pq}}$中通过节点$v$的数目 CC ${c_{(V)}} = \frac{N}{{\displaystyle\sum\limits_{u = 1}^N {{d_{vu}}} }}{c_{(V)}}$ N为节点数目，${d_{vu}}$表示节点$v$到节点$u$的最短路径长度
1.1. 基于排名聚合RA的时序网络节点重要性度量方法
1.2. 其他方法
-
本实验采用Manufacturing和Enrons数据进行来检验本方法对时序网络节点重要性排序的效果。Manufacturing和Enrons两个数据集为公司员工之间电子邮件往来产生的交互数据。因为对员工的评价通常是以月为单位进行考量，所以选择以月为单位来当作时序网络切片的一个时间尺度。Manufacturing数据集[25]是某中型制造公司员工之间的内部电子邮件通信数据，交互日期由2010年1月−2010年9月，时间按月进行切分；Enrons数据集[26]为美国某公司员工邮件来往的数据，交互日期由1999年9月−2002年，取其中2001年数据子集，数据按月切分。网络基本统计特性述如表2所述，其中N表示节点总数，T表示切分的时间层网络数，C表示节点之间的总交互次数，E表示整个聚合网络的连边数。
网络 N T C E Manufacturing 167 9 82927 5784 Enrons 151 12 33125 1270 -
通常认为，评价节点的重要性由两个方面进行评价[27-29]：1)计算节点在网络中对信息的传播能力；2)移除节点对网络连通性的影响力[8]。本文采用第2种方法来评价节点的重要性。通常认为，移除节点后网络的连通性变化大，该节点的影响力越大。反之，该节点的影响力越小。
时序网络效率是评判时序网络连通性的一个重要方法，其时序全局效率[20]的具体形式为：
式中，
$d_{vu}^T$ 表示节点$v$ 到节点$u$ 的时序最短距离。这里考虑删除节点后对网络连通性的影响，用
$E'_v$ 表示：式中，
${e_v}$ 和$e$ 分别删除节点后和原始网络的时序全局效率。 -
为了更直观地检验本文方法的效果，引入Spearman相关系数[30]来计算实验方法与评价方法结果排序之间的相关性，相关性越强说明两序列变化趋势越接近，排序的准确率越高。
对于Manufacturing数据集和Enrons数据集采用基于排名聚合RA的方法计算时序网络的节点排序与基准排序的Spearman相关系数，同时与上述6种中心性指标进行比较，结果如表3所示。
方法 数据集 Manufacturing Enrons RA 0.9351 0.7136 DC 0.9134 0.6133 CC 0.9136 0.4565 BC 0.8934 0.6232 TD 0.9134 0.6133 TC 0.8961 0.6425 TB 0.9486 0.6603 本文方法与基准的Spearman相关系数在两个数据集实验结果分别为0.9351和0.7136，对比其他6种方法，Spearman相关系数平均分别提高2.41%和18.63%。本文基于排名聚合RA的方法的排序准确率高于TD、TC、DC、BC，接近CC。且对于Enrons数据效果显著，对比其他方法最高提高56%。对于不同数据产生不同的提升效果与实际数据有关，对于Manufacturing数据集，对比方法的Spearman相关系数均大于0.8，都属于强相关，提升效果虽不显著，但有所提高；Enrons数据，对比方法的Spearman相关系数位于0.4～0.8之间，属于中等程度相关，提升效果明显。
2.1. 数据描述
2.2. 评价方法
2.3. 结果分析
-
本文首先通过建立层间相似性的超邻接矩阵对时序网络进行建模，利用特征向量中心性计算各时间切片网络的得节点重要性排名。另外，本文以删除节点前后网络连通性的变化情况为基准，同3种时序网络的节点重要性度量指标和3种静态网络的节点重要性度量指标，度中心性、介数中心性、接近度中心性作对比，评估本文所提方法对时序网络节点重要性排序的效果。Manufacturing和Enrons数据实验结果显示，本文所提方法的排序准确率高于其他6种节点重要性度量方法中的大部分方法，该方法较其他方法的Spearman相关系数也有提高。综上所述，本文提出的方法能准确地识别时序网络当中的重要节点，该工作对于时序网络节点重要性度量具有重要意义。
然而，本方法仅考虑了相邻时间切片网络的关系，而实际生活中节点之间的联系受之前多个时间切片网络的影响，如何从多个时间切片网络的角度描述和评价时序网络当中的节点是需要深入研究的问题。另外，本文提出的基于排名聚合的时序网络节点重要性度量方法是在两个小规模网络下进行的研究，考虑该方法在大规模网络的应用是接下来要研究的课题之一。
DownLoad: