基于节点相似性的时序网络节点重要性识别算法

Node Importance Identification Algorithm for Temporal Networks Based on Node Similarity

摘要: 时序网络可以更加准确地描述网络节点之间的交互顺序。本文提出基于节点相似性的时序路径聚集方法识别时序网络节点重要性，具体思想是在聚集时序路径的邻居信息评估目标节点重要性时，与目标节点相似性越高的邻居节点具有更高的影响力。同时，通过引入衰减因子区分不同时序路径长度邻居的信息权重，融合节点相似性系数和衰减因子构建基于节点相似性的时间信息聚集模型度量目标节点的重要性。在两个实证网络数据集上的实验结果显示相比于经典的方法，本文方法的肯德尔相关系数最高提高13.85%。该结果表明节点相似性系数的引入能够有效邻居信息来评估时序网络节点重要性。

Abstract: Temporal networks can more accurately describe the interaction order between network nodes. In this paper, we propose a node similarity-based temporal path aggregation method to identify the importance of temporal network nodes, the specific idea is that when aggregating the neighbor information of temporal paths to assess the importance of the target node, the neighbor nodes with higher similarity to the target node have higher influence. At the same time, by introducing attenuation factors to distinguish the information weights of neighbors with different temporal path lengths, the node similarity coefficient and attenuation factors are fused to construct a node similarity-based temporal information aggregation model to measure the importance of target nodes. The experimental results on two empirical network datasets show that the Kendall correlation coefficient of this paper’s method is improved by up to 13.85% compared with the classical method. This result indicates that the introduction of node similarity factor can effectively neighbor information to assess the importance of temporal network nodes.

1. 引言

时序网络考虑节点之间的交互关系和次序可以更加准确地刻画电子通讯、社交等复杂系统的交互关系 [1] 。基于静态网络的节点重要性评价方法有很多种，如度中心性 [2] 、特征向量中心性 [3] 、基于引力模型 [4] 及基于深度学习方法的节点重要性识别方法 [5] 等。不同的评价方法考虑节点信息的侧重点也各有不同。Ou等人 [6] 从局部信息、全局信息、社团结构、机器学习等方面对节点重要识别方法进行归纳。现实世界中的大多数复杂网络都是随时间变化的，由于时间维度的引入，网络的连边随时间会间断性地出现和消失 [7] 。所以，近些年来人们开始探究在时序网络中的节点重要性识别方法。Tang等 [8] [9] 基于时间窗图模型，通过定义时序距离提出了时序介数中心性和时序紧密度中心性。Bi等 [10] 将引力模型应用到时序网络中，将静态网络中节点的中心性特征作为引力模型的节点质量，节点间的时序距离视为其距离，通过计算节点在引力模型的得分来评估节点的重要性。Ye等 [11] 计算各时间窗内边的k-shell值，再对各时间窗边的k-shell值进行累加，节点的重要性得分为其连边的k-shell值之和。Taylor等 [12] 根据时序网络的层内关系和层间关系建立超邻接矩阵(supra-adjacency matrix, SAM)，通过求解超邻接矩阵的特征向量来评估节点的重要性。刘等人 [13] 考虑到SAM模型的层间耦合系数为固定参数，其忽略了不同节点在层间的差异性，将邻居拓扑重叠系数作为节点的层间耦合系数，提出了基于层间相似性的超邻接矩阵。梁等人 [14] 考虑到时序网络层内的连接关系和层间耦合关系，引入基于评分矩阵的排名聚合理论，提出了一种基于排名聚合的时序网络节点重要性识别方法。胡等人 [15] 将相邻层间耦合耦合系数推广至跨层并提出新的层间相似度指标来评估节点的层间耦合关系。Jiang等人 [16] 引入层间衰减因子及新的层间相似度指标来进一步描述层间的耦合关系。

时序网络是拓扑结构随时间不断变化的网络，其中拓扑结构变化表现为节点或连边的增加或减少，导致一个节点的重要性会随着时间的演变会发生改变。因此，在这个过程中我们可以通过节点的邻域来评估节点的重要性。Qu等人 [17] 提出了基于时间信息聚集的方法(temporal imformation gathering, TIG)来评估时序网络节点重要性，通过聚集节点时序邻居的信息作为节点的重要性得分能够有效的评估时序网络节点重要性，但该文对不同邻居的信息采取相同的聚集系数，忽略不同邻居的信息对于节点重要性评估影响的差异。考虑到节点的相似性越高，节点的连接关系越紧密，本文通过节点相似性系数来对聚集不同相似性邻居信息的权重进行区分。同时，本文通过引入一个与路径长度相关的衰减因子 ${\alpha }^j$ 作为不同阶数的时序邻居信息的聚集系数，随着节点邻居阶数j的增加，衰减因子 ${\alpha }^j$ 将不断地变小。最后，通过融合节点相似性系数和衰减因子构建基于节点相似性的时间信息聚集模型来评估时序网络节点重要性。利用删除节点后网络的时序全局效率差值作为评价指标，在两个实证网络数据集上的肯德尔相关系数结果均优于TIG方法，说明本文方法可以更为恰当的描述节点邻居信息对时序网络节点重要性评估的影响，从而更准确地识别时序网络节点重要性。

2. 理论基础

2.1. 时序网络描述

时序网络是节点间的连边随时间变化且具有时间先后顺序的网络。设 $G^T=\left(V,E^T\right)$ 表示时间间隔为[0, T]上的时序网络。该网络的节点数 $N=\left|V\right|$ ，每个节点交互事件 $e\in E^T$ 由一个三元组 $\left(v_i,v_j,t\right)$ 给出，表示节点v_i和节点v_j在时间t发生了交互。因此，时序网络G^T在整个观察期[0, T]按一定时间间隔切分为t个时间切片，每个时间切片的时间大小为T/t，则网络被分为t个离散有序的时间层网络 $G_1,\cdot \cdot \cdot ,G_t$ 。

2.2. 时序距离

时序距离不同于静态网络的最短距离，其考虑节点间发生或者断开连接的时间先后顺序 [18] 。由于节点间的连接关系存在时间顺序，即使时序网络是由一组无向图组成，时序距离也不是对称的，因为信息从节点i经过节点k最终传到节点j，需要在时间维度上满足节点i到k的有效连接发生在节点k到j之前。当节点i到节点j最快在第t个时间切片完成信息传递，则节点i到节点j的最快到达距离d_ij为t，若节点i到节点j之间不存在时序路径，则这两节点间的时序距离为 $\infty$ 。在每个时间切片中，节点只能将信息传给自己的一阶邻居。具体地，如图1所示的时序网络，在表1中给出各节点间时序距离d_ij的结果。

Table 1. The temporal distance between nodes in Figure 1 temporal network

表1. 图1时序网络中各节点间的时序距离

2.3. 节点中心性指标

2.3.1. 静态度中心性

静态度中心性(static degree centrality, SDC)认为节点的影响力与直接相连邻居的数量相关 [2] 。节点的邻居越多，该节点就越重要。k_i为节点i直接相连的邻居个数，|V|-1表示节点i直接相连邻居个数的理论最大值。

$\text{SDC}\left(i\right)=\frac{k_i}{\left|V\right|-1}$ (1)

2.3.2. 静态特征向量中心性

特征向量中心性(static eigenvector centrality, SEC)认为节点的重要性不仅和邻居的数量有关，而且还和邻居节点的质量有关 [3] 。

$x=cAx$ $x=\left[x_1,x_2,\cdots ,x_{\left|V\right|}\right]$ (2)

其中，x表示邻接矩阵最大特征值的特征特征向量。x_i表示节点i的重要性。

2.4. Salton节点相似性指标

Salton节点相似性指标也称为余弦相似性指标，通过计算两个节点的公共邻居数目来评估两个节点在网络中的相似程度 [19] 。节点间的指标值越大，代表节点间的相似度越高。定义如下：

$s_{uv}=\frac{\left|{\Gamma }_{\left(u\right)}\cap {\Gamma }_{\left(v\right)}\right|}{\sqrt{k_u\times k_v}}$ (3)

其中 $\left|{\Gamma }_{\left(u\right)}\cap {\Gamma }_{\left(v\right)}\right|$ 表示节点u与节点v的公共邻居数目，k_u表示节点u的度值，即节点u的邻居数目。

2.5. 时间信息聚集模型

时间信息聚集模型(TIG)认为节点的重要性依赖于节点邻域的重要性 [17] 。TIG模型首先假设每个节点有自己的初始重要性得分 $g^{\left(0\right)}$ ，然后通过时间信息的聚集对节点i的重要性进行不断的更新，其更新的依据为节点的重要性依赖于其领域的重要性，故通过节点不同时序距离邻居的重要性得分来更新节点本身的得分。节点的通过时间信息收集过程得到最终记为 $g^{\left(n\right)}$ 。具体表示如下：

$g^{\left(n\right)}={\displaystyle {\sum }_{j=0}^{n}f\left(j\right)\cdot D_j\cdot g^{\left(0\right)}}$ (4)

其中，n为模型聚集的时间深度，即在更新节点的重要性时最多考虑到n阶邻居。f(j)表示节点j阶邻居的重要性。D_j为距离指标矩阵，若u节点与v节点的时序距离为j，则 $D_j\left(u,v\right)=1$ ，反之若节点u与节点v没有发生连接，则 $D_j\left(u,v\right)=0$ 。 $g^{\left(0\right)}$ 为初始节点的初始得分， $g^{\left(n\right)}$ 为经过聚合n阶时序邻居后节点的重要性得分。 $g_i^{\left(n\right)}$ 越大，则代表节点i在时序网络中越重要。

3. 基于节点相似性的时间信息聚集模型

在上述的TIG模型中，对节点的邻居进行信息聚集时，采用同样的系数聚集节点所有邻居的信息，忽略不同邻居对于节点重要性影响的差异，不能有效利用邻居信息来评估节点的重要性。实际上，不同的邻居对节点重要性的影响不同，因此应做不同的考虑，才能反映时序网络节点的真实情况。基于以上考虑，本文对TIG模型中聚集节点邻居信息的过程做了改进，提出了基于节点相似性的时间信息聚集模型(similarity temporal information gathering, STIG)。

考虑到节点间的相似性越高，节点间的连接关系越紧密，故在聚集不同相似性邻居的信息时，应给予不同的聚集权重，以区分不同邻居信息对节点重要性的影响，因此本文通过融合Salton节点相似性指标，构建了网络的相似性矩阵，具体如下所示：

$S_j\left(u,v\right)=s_{uv}\times D_j\left(u,v\right)$ (5)

其中，s_uv表示节点u和节点v的Salton相似性，D_j为时序距离指标矩阵， $S_j\left(u,v\right)$ 表示节点u与j阶邻居v的相似度系数。

受到Katz中心性 [20] 认为短路径比长路径更重要思想的启发，本文通过引入一个与路径长度相关的因子 ${\alpha }^j$ 对不同阶数j的时序邻居的重要性进行区分。随着节点时序邻居阶数的增加，高阶时序邻居对节点的影响将逐渐减弱，从而更加有效地利用节点高阶邻居信息评估节点重要性。综合节点相似性系数和路径长度相关因子的时间信息聚集模型(STIG)具体形式如下所示：

$g^{\left(n\right)}={\displaystyle {\sum }_{j=1}^n{\alpha }^j\cdot S_j\cdot g^{\left(0\right)}}$ (6)

其中， $\alpha \in (0,1]$ ，本文取 $\alpha =0.5$ 进行实验分析，衰减因子 ${\alpha }^j$ 的引入可以削弱高阶时序邻居的影响。S_j为网络的相似性矩阵，可度量不同相似性邻居信息对节点重要性评估的影响。 $g^{\left(0\right)}$ 为每个节点的重要性的初始得分，本文选取度量节点局部信息的度中心性及全局信息的特征向量中心性分别作为节点的初始得分。n为聚集的时间深度，可控制模型聚集时序邻居信息的阶数，n的最大值为时序网络中节点间时序距离的最大值T。 $g^{\left(n\right)}$ 为模型经过迭代后节点重要性的最终得分。 $g_i^{\left(n\right)}$ 为节点i的重要性的最终得分。

图1给出了一个包含4个节点和3个时间层的时序网络及基于节点相似性的时间信息聚集方法的具体表示，s_uv为节点u和节点v的相似性系数， ${\alpha }^j$ 为路径长度相关的衰减因子， $g_i^{\left(0\right)}$ 为i节点的初始信息， $g_1^{\left(t\right)}$ 为节点1在聚集至t阶邻居信息后的重要性得分。以系数 $\alpha \times s_{14}$ 聚集节点1的一阶时序邻居4的初始信息 $g_4^{\left(0\right)}$ ，以系数 ${\alpha }^2\times s_{12}$ 聚集节点1的二阶时序邻居2的初始信息 $g_2^{\left(0\right)}$ ，以系数 ${\alpha }^3\times s_{13}$ 聚集节点1的三阶时序邻居3的初始信息 $g_3^{\left(0\right)}$ ，最终得到节点1在聚集至三阶时序邻居信息后的重要性得分为 $g_1^{\left(3\right)}=\alpha \times s_{14}\times g_4^{\left(0\right)}+{\alpha }^2\times s_{12}\times g_2^{\left(0\right)}+{\alpha }^3\times s_{13}\times g_3^{\left(0\right)}$ 。

Figure 1. Example of temporal network modeling based on the node similarity approach

图1. 基于节点相似性方法的时序网络建模实例

4. 数据实验与实证分析

4.1. 数据描述

为了验证基于节点相似性的时间信息聚集模型的效果，本文在两个真实网络上进行了实验。FB-FORUM来自Facebook的在线社交网络的数据 [21] ，网络每个时间窗的时间大小为1天。HYPERTEXT 2009是在ACM超文本2009会议期间收集的与会者面对面接触的时序网络 [22] ，网络每个时间窗的时间大小为1小时。网络基本统计特性具体描述如表2，其中N表示节点总数，E表示整个时序网络的连边数，T表示切分的时间层网络数。

Table 2. Basic statistical features of empirical networks

表2. 实证网络基本统计特性

4.2. 评价方法

4.2.1. 时序全局效率

节点删除法是常用的利用网络性能变化来评估节点重要性的方法 [23] 。为进一步检验本文方法对节点重要性的排序效果，并与TIG方法做对比，文中通过删除节点后网络连通性的变化程度来评价节点重要性的排序结果。通常认为，当删除节点后网络连通性变化越大，该节点就越重要，反之则节点重要性相对较低。时序全局效率 [12] 为评价时序网络连通性的一个重要方法，其具体形式如下：

$e=\frac{1}{\left|V\right|\left(\left|V\right|-1\right)}{\displaystyle {\sum }_{ij}\frac{1}{d_{ij}}}$ (7)

其中d_ij为时序网络中各节点的时序距离。|V|为网络的节点数。

最后用删除节点后网络时序全局效率的差值作为节点重要性的验证方法，其删除节点后的差值越大，说明被删除的节点越重要。E_i为删除节点i后网络时序全局效率差值，e为未删除节点的网络时序全局效率，e_i为删除节点i后网络的时序全局效率。

$E_i=\left|e-e_i\right|$ (8)

4.2.2. 肯德尔相关系数

肯德尔相关系数 [24] 被用来计算两个序列之间排序结果的相关性，对于 $x=\left\{x_1,x_2,\cdots ,x_{\left|V\right|}\right\}$ 和 $y=\left\{y_1,y_2,\cdots ,y_{\left|V\right|}\right\}$ 的肯德尔相关系数定义为：

$\tau =\frac{1}{\left|V\right|\left(\left|V\right|-1\right)}{\displaystyle {\sum }_{i\ne j}\mathrm{sgn}\left(x_i-x_j\right)\mathrm{sgn}\left(y_i-y_j\right)}$ (9)

其中，肯德尔相关系数取值为[−1, 1]，该值越接近1表示两个序列的正相关性程度越强，接近−1表示负相关性越强。这里x表示经过时序信息聚集模型的节点重要性得分序列，y为时序全局效率差值序列，|V|为序列的长度即网络的节点个数。

4.3. 实验及实证分析

本文基于上述两个实证网络数据集，依据本文的STIG方法及TIG方法计算各节点在聚集邻居信息时节点的重要性得分，分别得到两个方法的实证网络数据节点重要性排序。另外，为了更直观地检验本文方法的效果，用节点删除法得到各节点的时序全局效率差值后，利用肯德尔相关系数(Kendall’sτ)来评估排序的相关性。具体而言，就是将节点聚集时序邻居信息后的最终重要性得分与各节点的时序全局效率差值计算肯德尔相关系数。即得到时序信息聚集模型的排序结果与时序全局效率差值排序的一致性。

对两个实证网络数据集分别用本文的STIG方法及TIG方法得到的节点重要性得分与时序全局效率差值得到相应的排序结果一致性程度如图2、图3所示，选取节点的度中心性(SDC)、特征向量中心性(SEC)作为节点的初始信息。(ai)和(bi)表示随着聚集邻居信息时间深度n的增加，本文的STIG模型及TIG模型肯德尔相关系数 $\tau$ 的变化

Figure 2. In the FB-FORUM dataset, the Kendall correlation coefficients τ of the STIG model of this paper and the TIG model

图2. 在FB-FORUM数据集中，本文的STIG模型和TIG模型的肯德尔相关系数τ

Figure 3. In the HYPERTEXT 2009 dataset, the Kendall correlation coefficients τ of the STIG model of this paper and the TIG model

图3. 在HYPERTEXT 2009数据集中，本文的STIG模型和TIG模型的肯德尔相关系数τ。

由图2、图3的结果看出：1) 在两组实证网络中，TIG方法在聚集邻居的时序信息时，采取同样的系数来聚集不同邻居的信息，不能有效利用节点的邻居信息来评估节点的重要性，导致随着聚集邻居信息时间深度的增加，其肯德尔系数呈下降趋势。因此，可以考虑引入节点相似度系数区分不同邻居信息对节点重要性的影响，使模型能更加有效利用邻居信息来评估节点的重要性；2) 本文的STIG方法得到的肯德尔系数结果均优于TIG方法。随着聚集邻居信息深度的增加，肯德尔系数呈上升趋势。当聚集到一定时间深度时，肯德尔系数趋于稳定。表示本文方法考虑了节点在聚集邻居的时序信息时，引入节点相似度系数对不同邻居信息进行不同的度量，能更准确地对时序网络进行描述，得到的节点重要性排序也更为准确，其中两组实证数据STIG方法的结果相比TIG方法的肯德尔系数值均有提高，最高为13.85%。

5. 结论

对网络节点的重要性排序一直是复杂网络的热点问题，基于静态网络中的节点排序问题已经取得一定的进展，但在时序网络的节点排序问题还缺乏深入的研究。本文提出了一种基于节点相似性的时间信息聚集方法，在聚集节点邻居的时间信息来评估节点的重要性过程中，对不同邻居信息的重要程度进行区分。另外，本文利用节点删除法，通过计算删除节点前后网络的时序全局效率差值，来评估本文方法对节点重要性排序的效果。

两组实证数据的结果表明，本文的STIG方法得到的节点排序结果优于TIG方法，其肯德尔相关系数值较TIG方法均有提高。由于本文方法考虑了不同邻居在时间信息聚集的差异性，在聚集邻居信息时引入节点相似性系数。两个实证网络数据上的结果表示，随着聚集邻居时间信息深度的不断增加，本文模型的肯德尔相关系数不断上升并达到稳定，说明本文模型能够更有效利用邻居信息来评估时序网络节点重要性，从而更准确地时序网络中的重要节点。

参考文献