基于邻域中心性和重力模型的关键节点识别算法

Key Node Identification Algorithm Based on Neighborhood Centrality and Gravity Model

摘要: 识别复杂网络中的关键节点对促进信息传播、阻断谣言传播、管理交通运输和预防电网灾难性破坏等都具有很强的理论意义和应用价值。在对现有关键节点识别算法的研究分析基础上，受K-shell分解方法和重力模型的启发，本文提出了一种基于邻域中心性和重力模型的改进算法NCGM。NCGM算法不仅考虑了节点与处于核心位置节点之间的连接程度，还考虑了节点与其他节点之间的最短路径长度。为了评估所提出的NCGM算法，本文在7个常用数据集上使用易感–感染–恢复(SIR)传播动力学模型进行了实验仿真，将所提出的NCGM算法和5个对比算法的传播范围和肯德尔相关系数进行了比较分析。实验结果表明，所提出的NCGM算法能够更准确地识别不同类型网络中的关键节点。

Abstract: Identifying key nodes in complex networks has strong theoretical significance and practical value in promoting information dissemination, blocking rumor spread, managing transportation, and preventing catastrophic damage to the power grid. Based on the analysis and research of existing key node recognition algorithms, inspired by the K-shell decomposition method and gravity model, this article proposes an improved algorithm NCGM based on neighborhood centrality and gravity model. The NCGM algorithm not only considers the degree of connection between nodes and nodes at the core position, but also takes into account the shortest path distance between nodes and other nodes. To evaluate the proposed NCGM algorithm, this article conducted experimental simulations using the Susceptible-Infected-Recovered (SIR) propagation dynamics model on seven commonly used datasets, and compared and analyzed the propagation range and Knedall’s tau correlation coefficient of the proposed NCGM algorithm with five existing algorithms. The experimental results show that the proposed NCGM algorithm can more accurately identify key nodes in different types of networks.

1. 引言

识别复杂网络中的关键节点是网络科学的重要研究课题，这些节点不仅连接着网络中的各个部分，更是信息传播、资源调控和系统应对能力的关键枢纽。例如，这些关键节点可以抑制疫情的扩散[1]、抑制谣言的传播[2]、抵抗网络攻击[3]、保护生态系统中的关键成员[4]、加速新产品的病毒营销[5]以及防止电网的灾难性中断[6]等。由此可见，复杂网络在诸多领域中扮演着重要角色。因此，找到这些网络中的关键节点具有重要的理论意义和实践价值。

近年来，研究人员对识别复杂网络中的关键节点展开了广泛研究[7]，许多关键节点识别算法被提出，比较典型的有K-shell分解方法、度中心性、接近中心性、中介中心性、特征向量中心性、PageRank算法、DegreeDiscount算法、重力指数中心性等。其中，度中心性和K-shell分解方法[8]虽然计算复杂度较低，但是识别准确性也较低。接近中心性、中介中心性[9]和特征向量中心性[10]虽然识别准确性较高，但计算复杂度较高。DegreeDiscount算法[11]虽可以获得近似最优的实验结果，但其核心为贪心算法，计算复杂度高。而PageRank算法[12]在有向网络中表现出了较好的性能，却在无向网络中表现不佳。重力指数中心性[13]将节点的K-shell值作为重力公式中的质量，将节点之间的最短路径长度作为重力公式中的距离，以此来计算每个节点的影响力分数。但其只片面地考虑了节点自身的K-shell值，没有考虑邻居节点对节点的影响，也没有考虑节点与网络中核心位置的节点的连接情况。因此，受K-shell分解方法和重力模型的启发，本文提出了一种基于邻域中心性和重力模型的关键节点识别算法NCGM。首先，通过考虑邻居节点的K-shell值，可以衡量节点拥有邻居节点的数量和与处于网络核心位置的节点的连接情况，能够更好地识别引起广泛传播的节点。其次，通过考虑节点与其他节点的距离，能够更好地识别传播速度较快的节点。本文将节点的邻域中心性值作为重力公式中的质量，将节点之间的最短路径长度作为重力公式中的距离。实验结果表明，NCGM算法在不同类型的网络数据集上都表现出了最优的结果，说明其能够有效识别网络中的关键节点。

2. 相关工作

2.1. 相关改进算法

K-shell分解方法通过区分节点所处的位置来识别关键节点，但会将许多不同的节点分配相同的值，这样则无法区分处于同一层的不同节点，难以有效衡量节点的重要性。但由于它是一种适用于大规模网络的快速节点排序方法，因此，近年来，研究人员基于K-shell分解方法提出了大量的改进算法。例如，[14]考虑了节点与网络核心位置之间的距离，提出了改进的K-shell分解方法来区分同一层中的不同节点。K-shell分解方法在分解时只考虑了节点的剩余度，[15]通过考虑节点的剩余度和已移除度，提出了混合度分解算法MDD。[16]提出了一种基于K-shell的改进重力中心性测量算法KSGC。同时，不少研究者还将邻居节点对节点的影响考虑在内。例如，[17]提出了一种半局部中心性方法，其通过考虑节点的邻居和二阶邻居的度中心性来衡量节点的影响力。[18]提出了LSC算法，其考虑了节点的邻居及二阶邻居的数量和拓扑结构。受上述算法启发，考虑邻居节点对节点的影响，本文将节点邻居的K-shell值与重力模型相结合，提出一种新的关键节点识别算法NCGM。

2.2. 本文对比算法

1) 度中心性DC [9]基于节点的度(即与节点相连的边的数量)来评估节点的重要程度。节点的度中心性计算如下：

$DC\left(v_i\right)=\frac{d\left(v_i\right)}{n-1}$ (1)

其中，d表示节点的度，n表示网络中节点的总数。

2) 重力指数中心性算法GIC [13]是一种基于重力公式的方法。该方法将节点的K-shell值作为重力公式中的质量，将节点之间的最短路径长度作为重力公式中的距离，其具体计算公式如下：

$GI{C}_{\left(i\right)}={\displaystyle \sum _{j\in {\psi }_i}\frac{ks\left(i\right)\times ks\left(j\right)}{d_{ij}^2}}$ (2)

其中，GIC_(i)表示节点i的影响力值，${\psi }_i$ 为节点i的邻居集合，ks(i)和ks(j)代表节点i和j的K-shell值，d_ij表示节点i和节点j之间的最短路径长度。

3) 局部邻居贡献LNC [19]综合考虑了节点自身的影响以及最近邻居节点和次近邻居节点的影响，以此来量化复杂网络中节点的影响力。

4) 局部和全局中心性LGC [20]通过考虑节点自身的度及其与网络中其他节点的连接来识别网络中的关键节点，其具体计算公式如下：

$LG{C}_{\left(v_i\right)}=\frac{d\left(v_i\right)}{n}\times {\displaystyle \sum _{i\ne j}\frac{\sqrt{d\left(v_j\right)+\alpha }}{d_{ij}}}$ (3)

其中，d(v_i)和d(v_j)和分别代表节点v_i和v_j的度，d_ij表示节点v_i和节点v_j之间的最短路径长度，α为网络中的可调参数，用于控制节点度对网络的影响，其取值范围在0到1之间。

5) 基于局部的结构系统LSS，[21]考虑了节点的度、K-shell值以及网络中三角形的数量，以此来识别复杂网络中的关键节点。

3. 算法描述

传统的重力模型将网络中节点的度作为质量，将节点与节点之间的最短路径长度作为距离进行计算。一般认为，具有少数但影响力较高的邻居节点的节点比具有多数但影响力较小的邻居节点的节点具有更强的传播能力。而节点的度仅反映了其邻居数量，对于准确识别关键节点的能力有限。因此，本文综合考虑了节点的邻居数量和节点与网络中处于核心位置的节点的连接强度，提出了一种新的关键节点识别算法NCGM，下面将详细讨论所提出的算法。

给定无向无权网络$\text{G}=\left(V,E\right)$ ，V表示网络G的节点集合，E表示网络G的边集，且$n=\left|V\right|$ 表示网络G中节点的数量，$m=\left|E\right|$ 表示网络G中边的数量。

节点的邻域中心性NC指的是节点的邻居节点的K-shell值之和。K-shell值是描述节点在网络中所处位置的度量，具有较大K-shell值的节点处于网络中的核心位置，具有较强的影响力。考虑节点的一阶邻居节点的K-shell值之和，既考虑了节点的邻居节点数量，又考虑了节点与处于网络中核心位置的节点的连接程度。因此，具有较高邻域中心性值的节点具有更多的邻居节点，也说明其与网络中处于核心位置的节点连接紧密。节点邻域中心性的具体计算公式如下：

$NC\left(v_i\right)={\displaystyle \sum _{v_j\in N\left(v_i\right)}ks\left(v_j\right)}$ (4)

其中，ks表示节点的K-shell值，v_j表示网络中节点v_i的邻居节点。

基于对上述问题的考虑，受重力模型的启发，本文将节点的邻域中心性作为质量，将节点之间的最短路径长度作为距离。因此，节点的影响力值定义如下：

$NCGM\left(v_i\right)={\displaystyle \sum _{v_i\ne v_i}\frac{NC\left(v_i\right)\times NC\left(v_j\right)}{d_{ij}^2}}$ (5)

其中，d_ij表示节点v_i和节点v_j之间的最短路径长度，且v_j是网络中除了v_i之外的所有节点。

节点与其他节点的距离越短，说明节点能够更快地进行传播。节点具有较多的邻居且与处于网络中核心位置的节点连接越紧密，则节点能够进行更广泛的传播。显然，根据NCGM的计算等式可知，具有邻居数量较多且与网络中处于核心位置的节点连接越紧密，同时靠近大多数节点的NCGM值越大，节点能够更快、更广泛地进行传播，节点更具影响力。因此，所提出的NCGM算法在理论上是有效的。

4. 实验结果及分析

本节将详细介绍所使用的数据集和评价标准，并对实验结果进行对比分析，以进一步证明所提出的NCGM算法的有效性。

4.1. 数据集

为了评估所提出的NCGM算法的有效性，本文使用了7个无向无权的真实网络进行实验。这些网络包括：

Jazz：爵士音乐家的合作网络；

Email：西班牙一所大学的电子邮件交流关系；

Facebook：来自Facebook的社交圈，其中节点代表用户，边代表用户之间有联系；

GrQc：物理学领域中量子物理和相对论物理方面的研究合作网络；

Router：描述的是互联网路由器之间的连接关系；

PG：从2002年8月开始的Gnutella对等文件共享网络快照中提取出来的，其中节点代表网络拓扑中的主机，边代表主机之间的连接关系；

Sex：双向网络，其中节点表示女性和男性，边代表他们之间的好友关系。

这些网络的详细信息如表1所示，其中，N表示网络中节点的数量，E表示网络中边的数量，$\langle k\rangle$ 表示网络的平均度，$\langle d\rangle$ 表示网络的平均最短路径，C表示网络的聚类系数。

Table 1. Structure information statistics of real network datasets

表1. 真实网络数据集的结构信息统计

Network	N	E	$\langle k\rangle$	$\langle d\rangle$	C
Jazz	198	2472	27.697	2.235	0.633
Email	1133	5451	9.622	3.606	0.254
Facebook	4039	88,234	43.691	3.693	0.617
GrQc	4158	13,422	6.456	6.049	0.665
Router	5022	6258	2.492	6.449	0.033
PG	6299	20,776	6.597	4.643	0.015
Sex	15,810	38,540	4.875	5.785	0

4.2. 评价标准

4.2.1. SIR传播模型

本文使用易感–感染–恢复(SIR)传播模型进行实验仿真。在SIR模型中，个体被划分为三类：易感者S、感染者I和康复者R。其中，S指的是处于易感染状态且可能感染疾病的个体，I指的是处于感染疾病状态且能够传播疾病的个体，R指的是已经从感染状态恢复并对疾病具有免疫力的个体。初始时网络中存在少量感染个体I和大量易感个体S，感染个体I通过一定的概率β感染与其相连的易感个体S，同时感染个体I以一定的概率μ恢复健康。在SIR传播模型中，网络中节点的最终传播范围的计算公式如下所示：

$F\left(t\right)=SI{R}_{\left(v_i\right)}=\frac{1}{n}\times \left(nI+nR\right)$ (6)

其中，n表示网络的总节点数，nI表示感染节点的数量，nR表示康复节点的数量。

4.2.2. 肯德尔相关系数

肯德尔相关系数[22]用于衡量两个元素个数相同的排名序列之间的相关性。本文采用肯德尔相关系数来量化SIR模拟排名结果与不同算法得到的结果之间的相关程度。假设两个排名序列具有相同数量的节点，即$X=\left(x_1,x_2,\cdots ,x_n\right)$ 和$Y=\left(y_1,y_2,\cdots ,y_n\right)$ 。如果两个节点的次序一致，即$x_i>x_j$ 且$y_i>y_j$ ，或$x_i<x_j$ 且$y_i<y_j$ ，那么认为$\left(x_i,y_i\right)$ 和$\left(x_j,y_j\right)$ 是一致的。如果两个节点的次序不一致，即$x_i>x_j$ 且$y_i<y_j$ ，或$x_i<x_j$ 且$y_i>y_j$ ，那么认为$\left(x_i,y_i\right)$ 和$\left(x_j,y_j\right)$ 是不一致的。如果$x_i=x_j$ 或$y_i=y_j$ ，那么它们既不是一致的，也不是不一致的。肯德尔相关系数的定义如下：

$\tau \left(X,Y\right)=\frac{n_c-n_d}{n\left(n-1\right)/2}$ (7)

其中，n表示序列中节点的总数量，$n_c$ 和$n_d$ 分别表示一致对和不一致对的数量。一般来说，相关系数的取值范围在−1到1之间，$\tau >0$ 表示正相关，而$\tau <0$ 表示负相关。肯德尔相关系数的值越大，意味着两个排名序列之间的相关性越大，算法生成的排序结果越准确。

4.3. 实验结果分析

4.3.1. 传播范围

在实验中将传染病模型中的感染概率β设置为β = 0.1，将恢复概率μ设置为μ = 1。同时，使用所提出的NCGM算法和不同的对比算法计算每个网络中每个节点的影响力值，并对其进行降序排序，选择NCGM和对比算法所选出的前10个节点作为初始感染源。一般来说，一个更具有影响力的节点的传播范围更广泛，会感染更多的节点。图1~7展示了不同网络上NCGM算法和5个对比算法的传播范围。由图可知，NCGM算法识别的前10个节点的传播范围最大。因此，在7个网络数据集中，NCGM算法的识别效果较好。

Figure 1. Propagation scale F(t) of top-10 on the Jazz network dataset

图1. Jazz网络数据集上top-10的传播规模F(t)

Figure 2. Propagation scale F(t) of top-10 on the Email network dataset

图2. Email网络数据集上top-10的传播规模F(t)

Figure 3. Propagation scale F(t) of top-10 on the Facebook network dataset

图3. Facebook网络数据集上top-10的传播规模F(t)

Figure 4. Propagation scale F(t) of top-10 on the GrQc network dataset

图4. GrQc网络数据集上top-10的传播规模F(t)

Figure 5. Propagation scale F(t) of top-10 on the Router network dataset

图5. Router网络数据集上top-10的传播规模F(t)

Figure 6. Propagation scale F(t) of top-10 on the PG network dataset

图6. PG网络数据集上top-10的传播规模F(t)

Figure 7. Propagation scale F(t) of top-10 on the Sex network dataset

图7. Sex网络数据集上top-10的传播规模F(t)

4.3.2. 肯德尔相关系数值

使用随机函数选择节点作为初始感染源，在自然状态下用SIR模型计算每个节点的SIR值进行降序排序产生排名序列。将所提出的NCGM算法和其它对比算法产生的排名序列与SIR产生的排名序列进行比较，计算肯德尔相关系数，在实验中将感染概率β设置为β = 0.1，将恢复概率μ设置为μ = 0.5，所得结果如表2所示。由表2可知，NCGM与SIR得到的排名序列的肯德尔系数值最高，进一步证明了NCGM算法在识别网络关键节点方面的有效性。

Table 2. Kendall coefficient values of ranking sequences obtained from different algorithms and SIR

表2. 不同算法与SIR得到的排名序列的肯德尔系数值

Network	DC	GIC	LNC	LGC	LSS	NCGM
Jazz	0.005	0.013	0.021	0.009	0.012	0.027
Email	0.333	0.344	0.367	0.342	0.368	0.373
Facebook	0.330	0.378	0.406	0.375	0.287	0.413
GrQc	0.184	0.261	0.282	0.254	0.313	0.328
Router	0.085	0.275	0.260	0.274	0.261	0.296
PG	0.407	0.472	0.496	0.465	0.493	0.506
Sex	0.175	0.325	0.435	0.320	0.391	0.453

5. 总结和展望

本文受重力模型的启发，提出了一种新的关键节点识别算法NCGM。NCGM算法将节点的邻域中心性作为重力模型中的质量，将节点之间的最短路径距离作为重力模型中的距离，不仅考虑了节点与处于核心位置的节点的连接程度，还考虑了节点与其他节点的最短路径长度。本文在7个常用数据集上对所提出的NCGM算法进行了实验仿真。实验结果表明，NCGM算法在不同类型的网络数据集上都表现出了最优的结果，说明其能够有效识别网络中的关键节点。但NCGM算法仅适用于无向无权网络，为了使算法更具广泛性和现实性，我们将进一步考虑将其改进适用于带权无向网络和带权有向网络。