DOI: 10.12677/aam.2024.139398, PDF, HTML, XML,  被引量    国家自然科学基金支持
作者: 徐 清, 刘士虎^*：云南民族大学数学与计算机科学学院，云南 昆明
关键词: 复杂网络；引力模型；信息熵；关键节点；Complex Network； Gravity Model； Information Entropy； Key Nodes

文章引用：徐清, 刘士虎. 复杂网络中基于引力模型的关键节点识别方法[J]. 应用数学进展, 2024, 13(9): 4171-4181. https://doi.org/10.12677/aam.2024.139398

1. 引言

一般而言，现实生活中的许多实体都可以抽象为复杂网络，即把每一个实体抽象为一个节点，把实体与实体之间的联系抽象为边[1]。例如在航空网络[2]中，可以将机场抽象为节点，将机场之间的航线抽象为边。类似的，还有电力网络[3] [4]、社交网络[5] [6]等。识别出复杂网络中的关键节点，不仅对于研究复杂网络的结构和功能具有重要的理论作用，而且对人们的日常生活具有重要的指导意义。例如，在谣言传播网络[7]中，及时识别和控制能够迅速传播信息的关键节点，可以有效地控制虚假信息的传播。因此，识别出复杂网络中的关键节点已成为网络科学领域研究人员关注的研究热点之一，复杂网络中的关键节点识别方法不断被提出。

到目前为止，许多经典的关键节点识别方法已经被提出，例如基于节点局部信息的度中心性[8]方法，该方法认为邻居节点数越多的节点越关键。基于节点路径信息的介数中心性[9]方法，该方法通过计算节点在网络中作为其他节点对间最短路径中介的次数来评估其关键程度。基于节点位置信息的K-Shell分解[10]方法，该方法认为越位于网络核心位置的节点越关键。这些经典的关键节点识别方法通常只考虑了节点某一方面的信息，以至于不能有效识别出复杂网络中的关键节点。因此，近些年来，综合考虑节点不同信息的关键节点识别方法不断被提出，例如Meng等人[11]通过综合考虑节点的局部信息和位置信息，提出了一种新颖的关键节点识别方法。基于物理学中引力公式提出的引力模型识别方法是其中常见的方法之一。

受万有引力定律的启发，Ma等人[12]通过将万有引力公式推广到复杂网络的关键节点识别问题中，提出了引力中心性方法。该方法利用K-Shell分解方法求得的K-Shell值代替引力公式中的质量，用节点对间的最短路径长度代替引力公式中的距离，考虑到计算所有节点对间最短路径长度的运行时间代价是较高的，所以引力中心性方法只考虑了节点3阶内的邻居节点。类似的，基于万有引力定律的启发，Li等人[13]提出了一种新的识别方法，称为局部引力模型。该方法利用节点的度代替引力公式中的质量，用节点对间的最短路径长度代替引力公式中的距离，并且只考虑小于网络平均最短路径长度一半以内的节点对。相较于引力中心性方法，局部引力模型方法的性能有了提升。然而，在衡量节点“质量”时，局部引力模型方法仅考虑了节点的度，这种单一因素的考虑在一定程度上限制了其性能。对于局部引力模型中仅考虑节点的度这一不足，Zhang等人[14]对此进行改进并提出了拉普拉斯引力中心性方法，该方法在衡量节点“质量”时，不仅考虑了节点自身的度，而且还考虑了邻居节点的度，故该方法的性能得到了进一步提升。总体来说，拉普拉斯引力中心性方法只是利用了节点的度，考虑的因素依旧单一。

基于上述分析，为解决基于引力模型的关键节点识别方法存在的两方面不足，即一是衡量节点“质量”时考虑的因素单一，二是所需的运行时间代价较高，本文提出了一种改进的引力模型方法。该方法同时考虑了节点的度、H指数中心性和聚类系数，并重新考虑了节点的影响范围。为评估所提方法的性能，本文在八个数据集中进行仿真实验。实验结果表明，与现有的六种关键节点识别方法相比，本文提出的方法具有良好的单调性、鲁棒性以及准确性。并且与需要计算节点对间最短路径长度的引力模型识别方法相比，本文方法的运行时间代价显著降低。

2. 基础知识

一般的，无向无权的复杂网络可以表示为 $G=\left(V,E\right)$ ，其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 和 $E=\left\{\left(v_i,v_j\right)|v_i,v_j\in V\right\}$ 分别表示节点集与边集， $\left|V\right|=n$ 和 $\left|E\right|=m$ 表示节点的总数和边的总数。其邻接矩阵可以表示为 $A={\left(a_{ij}\right)}_{n\times n}$ ，对于任意两个节点 $v_i$ 和 $v_j$ ，如果 $\left(v_i,v_j\right)\in E$ ，则 $a_{ij}=1$ ，否则 $a_{ij}=0$ 。 $K\left(v_i\right)=\underset{j=1}{\overset{n}{{\displaystyle \sum }}}{a}_{ij}$ 表示节点 $v_i$ 的度， $cc\left(v_i\right)=\frac{2e\left(v_i\right)}{K\left(v_i\right)\left(K\left(v_i\right)-1\right)}$ 表示节点 $v_i$ 的聚类系数， $e\left(v_i\right)$ 表示节点 $v_i$ 的1阶邻居节点之间存在的边数，当 $K\left(v_i\right)=1$ 时， $cc\left(v_i\right)=0$ 。

2.1. 接近中心性(CC)

接近中心性[15]方法根据节点对间的最短路径长度衡量节点的关键程度，其计算公式为

$CC\left(v_i\right)=\frac{n-1}{{\displaystyle \underset{j\ne i}{\sum }{d}_{ij}}},$ (1)

其中 $d_{ij}$ 表示节点 $v_i$ 和 $v_j$ 之间的最短路径长度。

2.2. H指数中心性(HC)

H指数中心性[16]方法根据节点1阶邻居节点的度衡量节点的关键程度，即假设节点 $v_i$ 至少有h个1阶邻居节点的度大于或等于h，则节点 $v_i$ 的H指数中心性值 $H\left(v_i\right)=h$ 。

2.3. K-Shell分解(KS)

K-Shell分解[10]方法根据节点在网络中的位置衡量节点的关键程度，其为节点分配K-Shell值的步骤如下：第一步，计算所有节点的度，找出度为1的节点并移除，标记这些移除节点的K-Shell值为1。第二步，更新剩余节点的度，检查是否还有度为1的节点。如果有，则接着移除度为1的节点，直至所有剩余节点的度都大于1，并标记这些移除节点的K-Shell值为1；如果没有，则依次增加节点的度和K-Shell值并重复上述过程，直至网络中所有的节点都被移除。

2.4. 引力中心性(GC)

引力中心性方法[12]通过结合节点的K-Shell值和最短路径长度值衡量节点的关键程度，其计算公式如下

$GC\left(v_i\right)=\underset{j\ne i,d_{ij}\le 3}{{\displaystyle \sum }}\frac{KS\left(v_i\right)\times KS\left(v_j\right)}{d_{ij}^2},$ (2)

其中 $KS\left(v_i\right)$ 表示节点 $v_i$ 的K-Shell值。

2.5. 拉斯引力中心性(LGC)

拉普拉斯引力中心性[14]方法通过结合节点的拉普拉斯中心性值和最短路径长度值衡量节点的关键程度，其计算公式如下

$LGC\left(v_i\right)=\underset{j\ne i,d_{ij}\le R}{{\displaystyle \sum }}\frac{LC\left(v_i\right)\times LC\left(v_j\right)}{d_{ij}^2}$ ,(3)

$LC\left(v_i\right)=K^2\left(v_i\right)+K\left(v_i\right)+2\underset{v_j\in N_1\left(v_i\right)}{{\displaystyle \sum }}K\left(v_j\right)$ ,(4)

其中，R为网络平均最短路径长度 $\langle d\rangle$ 的一半，即 $R=\frac{1}{2}\langle d\rangle$ ， $LC\left(v_i\right)$ 表示节点 $v_i$ 的拉普拉斯中心性值， $N_1\left(v_i\right)$ 表示节点 $v_i$ 的1阶邻居。

2.6. 拉普拉斯能量中心性(LEC)

拉普拉斯能量中心性[17]方法根据节点的度及节点形成的三角形个数衡量节点的关键程度，其计算公式为

$LC\left(v_i\right)=K^3\left(v_i\right)+3K^2\left(v_i\right)-2K\left(v_i\right)+\underset{v_j\in N_1\left(v_i\right)}{{\displaystyle \sum }}\left\{3K^2\left(v_j\right)+3K\left(v_j\right)\right\}-6\Delta \left(v_i\right),$ (5)

其中 $\Delta \left(v_i\right)$ 表示以节点 $v_i$ 为顶点形成的三角形个数。

2.7. 信息熵

信息熵是信息论中广泛应用的基本概念之一，可用于度量信息的信息量。对于任意的离散随机变量 $X=\left\{x_1,x_2,\cdots ,x_n\right\}$ ，其概率分布为 $P=\left\{p_1,p_2,\cdots ,p_n\right\}$ ，则随机变量X的信息熵可以通过以下公式计算，即

$E\left(X\right)=-\underset{i=1}{\overset{n}{{\displaystyle \sum }}}{p}_i{\log }_2{p}_i,$ (6)

其中，信息熵的值越大，表示其拥有的信息量越多。近年来，信息熵作为有效的信息量度量指标，不断被推广应用于复杂网络中关键节点识别问题的研究中[18]-[20]。

3. 提出方法

由于前人提出或改进的引力模型识别方法在衡量节点“质量”时考虑的因素比较单一，因此，本文通过考虑节点的度、H指数中心性和聚类系数以改善这一问题。同时，本文重新考虑节点的影响范围，即只考虑节点2阶内的邻居节点。通过综合考虑多种因素及节点的影响范围，本文提出一种改进的引力模型关键节点识别方法(Improved Gravity Model，简称IGM)。

3.1. 综合考虑多种因素

节点的度仅考虑了节点的1阶邻居个数，而H指数中心性忽略了节点自身的度，即对于一些节点自身度较大而1阶邻居节点度较小的节点，会造成识别结果不准确的问题。此外，无论是在计算节点度还是H指数中心性的过程中，都只考虑了邻居节点的个数而没有考虑邻居节点之间的连接情况。与此相反，聚类系数可以很好的衡量节点的邻居节点之间的连接情况。但近些年的研究结果表明，高聚类系数值的节点在信息传播过程中会造成信息的重复传播，从而影响信息传播的速度。因此，本文将通过综合考虑节点的度、H指数中心性以及聚类系数，对引力模型中衡量节点“质量”时考虑的因素单一这一问题进行改进，改进后节点 $v_i$ 的“质量”表示为

$C\left(v_i\right)=\frac{K\left(v_i\right)}{K_{\max }}+\frac{H\left(v_i\right)}{H_{\max }}+\frac{1-cc\left(v_i\right)}{1-\min \left(cc\right)},$ (7)

其中， $K_{\max }=\max \left\{K\left(v_1\right),K\left(v_2\right),\cdots ,K\left(v_n\right)\right\}$ ， $H_{\max }=\max \left\{H\left(v_1\right),H\left(v_2\right),\cdots ,H\left(v_n\right)\right\}$ ， $\min \left(cc\right)=\min \left\{cc\left(v_1\right),cc\left(v_2\right),\cdots ,cc\left(v_n\right)\right\}$ 。为进一步区分不同节点的“质量”，利用信息熵对求得的值再次进行区分。基于此，节点 $v_i$ 的“质量”进一步表示为

$E\left(v_i\right)=-\underset{v_j\in \Psi \left(v_i\right)}{{\displaystyle \sum }}p\left(v_j\right){\log }_{2}p\left(v_j\right),$ (8)

其中， $p\left(v_j\right)=\frac{C\left(v_j\right)}{{{\displaystyle \sum }}_{v_j\in \Psi \left(v_i\right)}C\left(v_j\right)}$ ， $\Psi \left(v_i\right)=N_1\left(v_i\right)\cup \left\{v_i\right\}$ 。

3.2. 改进的引力模型关键节点识别方法

在利用引力模型求节点的影响力值时，如何衡量节点的影响范围一直是一个难题，大部分学者将节点的影响范围定义为网络平均最短路径长度的一半。然而，计算一个网络的平均最短路径长度所需的运行时间代价是较高的。通过对近些年关键节点识别的相关论文进行阅读，发现许多学者在考虑节点的影响范围时，通常考虑的是节点2阶内的邻居节点。因此，本文在考虑节点的影响范围时，只考虑节点2阶内的邻居节点。最终，节点 $v_i$ 的影响力值表示为

$IGM\left(v_i\right)=\underset{j\ne i,d_{ij}\le 2}{{\displaystyle \sum }}\frac{E\left(v_i\right)\times E\left(v_j\right)}{d_{ij}^2}.$ (9)

4. 实验设置

这一部分将介绍本文使用的八个数据集以及三个评估指标。其中，本文所有的实验，均是在表1描述的实验环境中运行的。

Table 1. Description of experiment environment

表1. 实验环境描述

参数项	参数值
操作系统	Windows 10
运行内存	16.0 GB
中央处理器	Intel(R) Core(TM) i5-1135G7
编程语言	Python 3.11

4.1. 实验数据集

本文采用以下八个数据集作为实验数据集，即Adjnoun [21]：小说《大卫科波菲尔》中形容词和名词构成的网络；Enron [22]：安然公司员工之间的电子邮件通讯网络；Netscience [21]：网络科学领域中作者之间的合著关系网络；Celegans [21]：秀丽隐杆线虫的代谢网络；Crime [22]：由罪犯之间的联系构成的犯罪网络；Email [23]：罗维拉–威尔吉利大学成员之间的电子邮件通讯网络；Air [23]：由美国联邦航空局国家飞行数据构建的航空网络；Health [24]：由青少年之间的联系构成的网络。八个数据集的基本信息如表2所示，其中， $\langle cc\rangle$ 表示网络平均聚类系数。

Table 2. The basic information of eight datasets

表2. 八个数据集的基本信息

数据集	n	m	$\langle d\rangle$	$\langle cc\rangle$
Adjnoun	112	425	2.5356	0.1728
Enron	143	623	2.9670	0.4339
Netscience	379	914	6.0419	0.7412
Celegans	453	2025	2.6638	0.6465
Crime	829	1473	5.0400	0.0058
Email	1133	5451	3.6060	0.2202
Air	1226	2408	5.9290	0.0675
Health	2539	10455	4.5594	0.1467

4.2. 评估指标

这一部分将介绍三个评估指标，分别是基于单调性的评估指标、基于网络连通性的评估指标以及基于传染病模型的评估指标。

4.2.1. 基于单调性的评估指标

单调性函数[25]可以用于评估不同方法的节点区分能力，其计算公式为

$M\left(R\right)={\left\{1-\frac{{{\displaystyle \sum }}_{r\in R}{n}_r\times \left(n_r-1\right)}{n\times \left(n-1\right)}\right\}}^2,$ (10)

其中，R是根据节点的影响力值从大到小将节点进行排序的排序等级列表， $n_r$ 表示在排名等级r上的节点数，M的取值范围是[0, 1]。当M值为0时，表明所有节点的影响力值是相同的，即所有节点的排序等级都是相同的；当M值为1时，表明所有节点的影响力值都是不同的，即所有节点的排序等级都是不同的。M值越接近于1，表明对应方法的节点区分能力越强。

4.2.2. 基于网络连通性的评估指标

按照排序等级列表R依次移除一定的比例节点后，网络连通子图的数量和最大连通子图的规模可以用于衡量节点识别方法的鲁棒性[26]。记网络连通子图的总数为 $\xi$ ，则最大连通子图的规模表示为

$\tau =\frac{M_c}{n},$ (11)

其中， $M_c=\max \left\{N_1,N_2,\cdots ,N_{\xi }\right\}$ 表示最大连通子图包含的节点总数， $N_{\xi }$ 表示对应连通子图包含的节点总数。当 $\xi$ 的值越大， $\tau$ 的值越小时，表明对应识别方法的鲁棒性越强。

4.2.3. 基于传染病模型的评估指标

识别方法的准确性可以用SI模型[27]进行评估。SI模型将节点分为两种状态，即易感状态和感染状态。在每一步感染过程中，处于感染状态的节点以概率 $\beta$ 感染其易感状态的邻居，标记第t步时处于感染状态的总节点数为 $F\left(t\right)$ 。在传染过程中，如果感染率 $\beta$ 过低，则感染状态节点只能以较低的概率感染其周围易感状态节点，从而只有少量节点被感染。相反，如果感染率 $\beta$ 过高，则所有节点最终都会被感染，使得难以区分出各个节点的真实感染能力。本文与文献[27]取值相同的参数值，即 $\beta =0.1$ ， $t=10$ 。在相同步长内，如果 $F\left(t\right)$ 值越大，表示对应方法识别出的节点感染能力越强，即识别出的节点越准确。

5. 实验结果分析

本文的实验结果分析主要包括四个部分，分别是单调性分析、鲁棒性分析、准确性分析以及运行时间分析，接下来将依次对这四个部分进行详细的分析。

5.1. 单调性分析

表3列出了七种方法在八个数据集的单调性值，其中，每个数据集上最高的单调性值被加粗表示。根据表3可知，除了在Netscience数据集上，IGM方法总是可以取得最高的单调性值，并且在Netscience数据集上的单调性值也是位于第二的。KS方法是一种基于节点位置信息的粗粒化识别方法，故该方法将许多影响力不同节点分配到同一层中，导致该方法在不同数据集上的单调性值都是最低的。从表3可以观察到，相比于KS方法，HC方法在节点区分能力上有一定的提升。LEC方法不仅考虑了节点自身与邻居节点的度，而且还考虑了节点的邻居互为邻居的情况。因此，LEC方法的节点区分能力得到进一步提升，并且在Netscience数据集上取得了最高的单调性值。CC方法的单调性值基本都大于0.99，比起KS和HC方法，该方法的节点区分能力是更强的。GC方法同时考虑了节点的位置信息和路径信息，LGC方法同时考虑了节点自身以及邻居节点的度和路径信息，故这两种方法的节点区分能力相对来说也是比较好的。总而言之，相较于其他六种方法，IGM方法的节点区分能力是更强的。

Table 3. Monotonicity values for seven methods on eight datasets

表3. 七种方法在八个数据集的单调性值

数据集	M(CC)	M(KS)	M(HC)	M(GC)	M(LGC)	M(LEC)	M(IGM)
Adjnoun	0.9837	0.5990	0.8110	0.9990	0.9997	0.9994	0.9997
Enron	0.9872	0.7245	0.8331	0.9998	0.9998	0.9986	0.9998
Netscience	0.9928	0.6421	0.6825	0.9946	0.9950	0.9972	0.9950
Celegans	0.9900	0.6962	0.7331	0.9967	0.9983	0.9971	0.9986
Crime	0.9982	0.4327	0.5651	0.9990	0.9986	0.9836	0.9994
Email	0.9988	0.8088	0.8583	0.9999	0.9999	0.9986	0.9999
Air	0.9992	0.3772	0.4916	0.9992	0.9997	0.9912	0.9997
Health	0.9994	0.5245	0.7986	0.9999	0.9999	0.9994	0.9999

5.2. 鲁棒性分析

图1给出了移除一定比例节点后 $\xi$ 值的变化曲线，其中横轴表示移除节点的比例，纵轴表示 $\xi$ 值。从图1中可以观察到，在大多数情况下，IGM方法总是可以取得最大的 $\xi$ 值，尤其是在Adjnoun、Netscience、Crime和Air数据集上，可以看到明显的优势。在剩余的四个数据集上，虽然不同方法之间的区别没有前面四个数据集明显，但总体来说IGM方法依旧是更有优势的。例如在Celegans数据集上，当移除前40%比例的节点时，IGM方法的优势也是明显的。根据图1可知，在大多数情况下，HC方法获得连通子图数量是大于其它五种对比方法的。例如在Air数据集上，当移除20%~70%比例的节点时，HC方法获得的连通子图数量是大于其它五种对比方法的。相对来说，GC和LGC方法总是位于中间的位置，而CC、KS和LEC这三种方法获得的连通子图数量是较少的。例如在Enron数据集上，当移除前50%比例的节点时，KS方法获得的连通子图数量总是最少的；在Celegans数据集上，当移除前80%比例的节点时，CC和LEC方法在大多数情况下总是获得最小的 $\xi$ 值。结合表2，可以观察到对于 $\langle d\rangle$ 较大的网络，CC方法获得的连通子图数量总是较少的。

Figure 1. The changing curve of $\xi$ value

图1. $\xi$ 值变化曲线

Figure 2. The changing curve of $\tau$ value

图2. $\tau$ 值变化曲线

图2给出了移除一定比例节点后 $\tau$ 值的变化曲线，其中横轴表示移除节点的比例，纵轴表示 $\tau$ 值。从图2中可以观察到，在Adjnoun、Netscience、Crime和Air数据集上，IGM方法总是可以取得最小的 $\tau$ 值。例如，在Netscience数据集上，当移除节点比例为10%时，IGM方法获得了最小的 $\tau$ 值，并且与最大 $\tau$ 值之间的 $\tau$ 值差为0.5963。与图1中的情况类似，HC、GC和LGC方法总是位于中间的位置，而CC、KS和LEC这三种方法的效果较差。根据图1和图2可知，按一定比例移除IGM方法识别出的节点，不仅可以快速增加连通子图的数量，而且还可以使得最大连通子图的节点总数达到最少，即说明IGM方法的鲁棒性是最强的。

5.3. 准确性分析

在本实验中，选取每种方法影响力值最大的前20个节点为最初的感染节点，将每种方法独立运行100次后，取每一步的平均值并标记为 $\langle F\left(t\right)\rangle$ ，该平均值即为每一步最终的感染节点数。图3给出了七种方法在八个数据集上的感染曲线，其中横轴表示步长，纵轴表示感染节点总数。从图3中可以观察到，IGM方法在大多数情况下都可以取得最大的 $\langle F\left(t\right)\rangle$ 值，即说明IGM方法识别出节点的感染能力是最强的，也即IGM方法识别出的节点是更准确的。例如，在Health数据集上，IGM方法比其它对比方法存在明显的优势，并且与最低的 $\langle F\left(t\right)\rangle$ 值之间的差值分别为32，116，208，286，376，378，343，263，195，129。相对来说，在大多数数据集上，CC、GC和LGC方法的 $\langle F\left(t\right)\rangle$ 值总是位于中间的位置。在Netscience和Crime数据集上，KS方法识别出节点的感染能力是更弱的，因为在大多数情况下，KS方法获得的 $\langle F\left(t\right)\rangle$ 值总是更小的。在Enron数据集上，HC方法识别出节点的感染能力是更弱的。在Email和Health数据集上，LEC方法识别出节点的感染能力是更弱的。总而言之，相比于其它六种节点识别方法，IGM方法识别出的节点是更准确的。

Figure 3. The changing curve of $\langle F\left(t\right)\rangle$ value

图3. $\langle F\left(t\right)\rangle$ 值变化曲线

5.4. 运行时间分析

在本实验中，将每种方法独立运行100次后，取其运行时间的平均值作为每种方法的最终运行时间。表4列出了七种方法在八个数据集上的最终运行时间，运行时间单位为秒。根据表4可知，IGM方法的运行时间总是位于中间的位置，即IGM方法的运行时间不是最高的，也不是最低的。HC、KS和LEC方法相对来说运行时间较短，且三种方法均在1秒以内完成。然而，HC和KS方法的节点区分能力较弱。虽然CC、GC和LGC方法的节点区分能力比HC和KS方法强，但这三种方法的运行时间相对来说是更高的。尤其是CC和LGC方法，因为它们需要计算所有节点对间的最短路径长度，这是比较费时间的。从表4中可以观察到，随着数据集规模的扩大，CC和LGC这两种方法的运行时间是快速增加的，尤其是在Health数据集上，CC方法的运行时间是IGM的5.6倍，LGC方法的运行时间是IGM的8.1倍。此外，通过计算可得，在所有数据集上与GC和LGC方法相比，IGM方法的运行时间可以降低18.97%~87.65%。综合考虑，IGM方法的运行时间在可接受的范围内。

Table 4. The running time of the seven methods on eight datasets

表4. 七种方法在八个数据集上的运行时间

数据集	CC	KS	HC	GC	LGC	LEC	IGM
Adjnoun	0.0286	0.0033	0.0041	0.0324	0.0341	0.0086	0.0203
Enron	0.0453	0.0057	0.0054	0.0453	0.0520	0.0120	0.0248
Netscience	0.1633	0.0216	0.0233	0.0987	0.2490	0.0315	0.0706
Celegans	0.4041	0.0108	0.0131	0.5080	0.6250	0.0422	0.2157
Crime	1.0309	0.0155	0.0165	0.4633	1.5494	0.0363	0.2169
Email	2.4928	0.0280	0.0337	1.9417	3.4798	0.0848	0.5733
Air	2.5880	0.0215	0.0250	0.6702	3.2100	0.0539	0.4368
Health	11.0311	0.0598	0.0722	3.5867	15.8230	0.1564	1.9547

6. 结论

本文通过利用度、H指数中心性和聚类系数衡量节点的“质量”，并利用信息熵对其进行区分，同时将节点的影响范围限制为其2阶内邻居节点，提出了改进的引力模型识别方法IGM。在八个数据集上的实验结果表明，IGM方法在单调性、鲁棒性以及准确性方面的性能是更优的。尽管本文提出的方法在运行时间上略高于KS、HC和LEC方法，但KS和HC方法通常会将相同的影响力值分配给多个节点，从而不能有效区分节点。但比起需要计算最短路径长度的CC和LGC方法，IGM方法的运行时间是更短的，尤其是在数据规模比较大的网络中。此外，在衡量节点“质量”时，IGM方法考虑了三种因素，未来的研究将扩展到考虑节点更多的因素，以确保其影响力得到更加合适的衡量。

基金项目

国家自然科学基金资助项目(61966039)。

NOTES

^*通讯作者。

参考文献

[1]	周建林, 樊瑛, 狄增如. 复杂网络进展[J]. 北京师范大学学报(自然科学版), 2023, 59(5): 691-704.
[2]	Su, M., Luan, W., Li, Z., Wan, S. and Zhang, Z. (2019) Evolution and Determinants of an Air Transport Network: A Case Study of the Chinese Main Air Transport Network. Sustainability, 11, Article 3933. https://doi.org/10.3390/su11143933
[3]	Li, G., Zhang, L., Wang, Y. and Kang, Z. (2023) Critical Node Identification Method of Power Grid Based on the Improved Entropy Weight Method. Electronics, 12, Article 2439. https://doi.org/10.3390/electronics12112439
[4]	Li, J., Lin, Y. and Su, Q. (2024) Identifying Critical Nodes of Cyber-Physical Power Systems Based on Improved Adaptive Differential Evolution. Electric Power Systems Research, 229, Article 110112. https://doi.org/10.1016/j.epsr.2024.110112
[5]	Kou, J., Jia, P., Liu, J., Dai, J. and Luo, H. (2023) Identify Influential Nodes in Social Networks with Graph Multi-Head Attention Regression Model. Neurocomputing, 530, 23-36. https://doi.org/10.1016/j.neucom.2023.01.078
[6]	Jain, S. and Sinha, A. (2023) TriBeC: Identifying Influential Users on Social Networks with Upstream and Downstream Network Centrality. International Journal of General Systems, 52, 275-296. https://doi.org/10.1080/03081079.2023.2194642
[7]	Yao, X., Gu, Y., Gu, C. and Huang, H. (2022) Fast Controlling of Rumors with Limited Cost in Social Networks. Computer Communications, 182, 41-51. https://doi.org/10.1016/j.comcom.2021.10.041
[8]	Chen, D., Lü, L., Shang, M., Zhang, Y. and Zhou, T. (2012) Identifying Influential Nodes in Complex Networks. Physica A: Statistical Mechanics and Its Applications, 391, 1777-1787. https://doi.org/10.1016/j.physa.2011.09.017
[9]	Newman, M.E.J. (2005) A Measure of Betweenness Centrality Based on Random Walks. Social Networks, 27, 39-54. https://doi.org/10.1016/j.socnet.2004.11.009
[10]	Kitsak, M., Gallos, L.K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H.E., et al. (2010) Identification of Influential Spreaders in Complex Networks. Nature Physics, 6, 888-893. https://doi.org/10.1038/nphys1746
[11]	Meng, L., Xu, G., Yang, P. and Tu, D. (2022) A Novel Potential Edge Weight Method for Identifying Influential Nodes in Complex Networks Based on Neighborhood and Position. Journal of Computational Science, 60, Article 101591. https://doi.org/10.1016/j.jocs.2022.101591
[12]	Ma, L., Ma, C., Zhang, H. and Wang, B. (2016) Identifying Influential Spreaders in Complex Networks Based on Gravity Formula. Physica A: Statistical Mechanics and Its Applications, 451, 205-212. https://doi.org/10.1016/j.physa.2015.12.162
[13]	Li, Z., Ren, T., Ma, X., Liu, S., Zhang, Y. and Zhou, T. (2019) Identifying Influential Spreaders by Gravity Model. Scientific Reports, 9, Article No. 8387. https://doi.org/10.1038/s41598-019-44930-9
[14]	Zhang, Q., Shuai, B. and Lü, M. (2022) A Novel Method to Identify Influential Nodes in Complex Networks Based on Gravity Centrality. Information Sciences, 618, 98-117. https://doi.org/10.1016/j.ins.2022.10.070
[15]	Lü, L., Chen, D., Ren, X., Zhang, Q., Zhang, Y. and Zhou, T. (2016) Vital Nodes Identification in Complex Networks. Physics Reports, 650, 1-63. https://doi.org/10.1016/j.physrep.2016.06.007
[16]	Lü, L., Zhou, T., Zhang, Q. and Stanley, H.E. (2016) The H-Index of a Network Node and Its Relation to Degree and Coreness. Nature Communications, 7, Article No. 10168. https://doi.org/10.1038/ncomms10168
[17]	Zhao, S. and Sun, S. (2023) Identification of Node Centrality Based on Laplacian Energy of Networks. Physica A: Statistical Mechanics and Its Applications, 609, Article 128353. https://doi.org/10.1016/j.physa.2022.128353
[18]	Xi, Y. and Cui, X. (2023) Identifying Influential Nodes in Complex Networks Based on Information Entropy and Relationship Strength. Entropy, 25, Article 754. https://doi.org/10.3390/e25050754
[19]	Tong, T., Dong, Q., Sun, J. and Jiang, Y. (2023) Vital Spreaders Identification Synthesizing Cross Entropy and Information Entropy with Kshell Method. Expert Systems with Applications, 224, Article 119928. https://doi.org/10.1016/j.eswa.2023.119928
[20]	吴亚丽,任远光,董昂,等. 基于邻域K-shell分布的关键节点识别方法[J]. 计算机工程与应用, 2024, 60(2): 87-95.
[21]	Newman, M.E.J. (2006) Finding Community Structure in Networks Using the Eigenvectors of Matrices. Physical Review E, 74, Article 036104. https://doi.org/10.1103/physreve.74.036104
[22]	Rossi, R. and Ahmed, N. (2015) The Network Data Repository with Interactive Graph Analytics and Visualization. Proceedings of the AAAI Conference on Artificial Intelligence, 29, 4292-4293. https://doi.org/10.1609/aaai.v29i1.9277
[23]	Kunegis, J. (2013) KONECT: The Koblenz Network Collection. Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, 13-17 May 2013, 1343-1350. https://doi.org/10.1145/2487788.2488173
[24]	Moody, J. (2001) Peer Influence Groups: Identifying Dense Clusters in Large Networks. Social Networks, 23, 261-283. https://doi.org/10.1016/s0378-8733(01)00042-9
[25]	Zheng, J. and Liu, J. (2023) A New Scheme for Identifying Important Nodes in Complex Networks Based on Generalized Degree. Journal of Computational Science, 67, Article 101964. https://doi.org/10.1016/j.jocs.2023.101964
[26]	Liu, S. and Gao, H. (2022) The Self-Information Weighting-Based Node Importance Ranking Method for Graph Data. Entropy, 24, Article 1471. https://doi.org/10.3390/e24101471
[27]	Fan, W., He, Y., Han, X. and Feng, Y. (2021) A New Model to Identify Node Importance in Complex Networks Based on DEMATEL Method. Scientific Reports, 11, Article No. 22829. https://doi.org/10.1038/s41598-021-02306-y