二阶邻居节点信息驱动的节点重要性排序算法

Second-Order Neighbor Node-Driven Importance Ranking Algorithm

摘要: 在复杂网络中，挖掘重要节点对精准推荐、交通管控、谣言控制和疾病遏制等应用至关重要。为此，本文提出一种局部信息驱动的节点重要性排序算法Leaky Noisy Integrate-and-Fire (LNIF)。该算法通过获取节点的二阶邻居信息计算节点重要性，首先通过信息量衡量节点重要性，然后叠加符合条件的邻居节点重要性，进一步区分节点重要程度，最终获得节点排序。为验证LNIF的有效性，在11个真实数据集和1个网络模型上进行了实验，采用平均度、网络效率、最大连通子图系数和SIR传播模型四个指标进行对比分析。实验结果表明，LNIF生成的节点序列在多个关键指标上表现显著优于现有基准方法。LNIF计算出的节点序列使网络平均度、网络效率和最大连通子图系数下降最快，表明其在优化网络结构和识别关键节点方面效率更高；在SIR传播模型中，LNIF的节点序列传播能力也优于其他五种算法，进一步证明了其在遏制和引导信息传播方面的潜力。

Abstract: In complex networks, identifying important nodes is crucial for applications like recommendation systems, traffic control, rumor containment, and disease transmission management. To address this, we propose the Leaky Noisy Integration-and-Fire (LNIF) algorithm, which ranks node importance using second-order neighbor information. LNIF first measures node importance by calculating information quantity, then refines the ranking by aggregating the importance of qualified neighbor nodes. Experiments on 11 real datasets and 1 network model, using metrics like average degree, network efficiency, maximum connectivity subgraph coefficient, and the SIR propagation model, demonstrate LNIF’s effectiveness. Results show that LNIF outperforms existing methods, with its node sequences causing the fastest declines in average degree, network efficiency, and maximum connected subgraph coefficient, highlighting its efficiency in optimizing network structure and identifying key nodes. Additionally, in the SIR model, LNIF’s node sequences exhibit superior propagation capabilities, further proving its potential in controlling and guiding information spread.

1. 引言

在科技驱动的互联网快速发展中，复杂网络逐渐兴起，成为社会学、计算机科学、管理学、物理、数学、生物、交通等多个领域的研究热点[1]-[3]。在现实世界中，许多复杂系统可以抽象为网络结构，常见的网络结构有：在社会关系网络中，有社交网络、邮件网络、科学家合作网络等[4] [5]；在交通系统中，有公路、铁路、航空网络等[6] [7]；在生物领域中的蛋白质网络、神经网络、新陈代谢系统等[8] [9]。在这些多样的网络结构中，小世界和无标度特性使某些节点具有极大影响力，其行为对网络功能和结构产生重大影响，这些节点被称为重要节点[10]-[12]。因此，准确快速识别复杂网络中的重要节点是当前的热点之一。

挖掘网络中的重要节点对于现实生活具有重要意义。在传染病传播中，构建传染病网络，找到关键传染源，可以大大降低传染病的传播速度[13] [14]；在设备网络中对关键节点采取保护措施，可以增强设备网络的整体抗毁性[15]；在交通网络中，识别关键路段，并有效对这些关键路段进行管控，可以降低高峰期交通网络的堵塞情况[6]；在谣言传播的网络中[16]，谣言传播经过众多节点，尤其重要节点能加速信息扩散。快速定位这些节点有助于引导舆论，发挥其影响力，有效遏制谣言传播。

研究人员在节点重要性方面做了很多工作，许多经典的节点重要性算法被提出，如度中心性、介数中心性、紧密度中心性、特征向量中心性、PageRank算法与K-shell算法等[17]-[19]。近年来，随着复杂网络理论的发展，研究者们提出了新的节点重要性算法，丰富了复杂网络的相关知识。Liu等人[20]通过结合网络拓扑与信息传播，利用邻居节点的影响来对网络中的节点重要性等级进行修正。Lü等人[21]将用于评价学术论文作者影响力的H指数引入到复杂网络节点重要性分析领域。王安等人[22]通过LPA算法将网络进行社区划分，然后在社区内部排序处理，最终得到节点的综合排序结果，提高了传播性能。Liu等人[23]将结构空穴和K-shell分解算法结合来区分网络中的重要节点。Yang等人[24]结合K-shell算法与节点的位置提出一种新的重要性算法，并通过相关实验验证了该算法的合理性和有效性。

在大规模复杂网络中，全局节点重要性算法因高时间复杂度不实用，局部算法虽降低复杂度，但H-index和K-shell无法区分同值节点。本文提出LNIF算法，结合二阶邻居信息和信息传播因素，通过计算节点信息量并引入传播阈值修正，提升准确性。在11个真实数据集和1个网络模型上的实验显示，LNIF在平均度、网络效率、最大连通子图系数和SIR传播模型中表现最优，能有效识别重要节点并产生最大影响力。

2. 材料和方法

2.1. 相关理论基础

令无向网络$G=\left(V,E\right)$ ，$V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 代表所有节点的集合，$\left|V\right|=n$ ；$E=\left\{e_1,e_2,\cdots ,e_n\right\}$ 代表节点间的连接关系，$\left|E\right|=m$ ，网络G的邻接矩阵用A表示，若节点之间存在连边时，则相应的位置上置1，否则为0。

1) 度中心性

度中心性是表示与节点直接相连的节点数量，度中心性的值越大，节点就越重要，计算公式如下：

$DC\left(v_i\right)={\displaystyle {\sum }_{j=1}^N{A}_{ij}}$ (1)

2) 介数中心性

介数中心性衡量的是某个节点在多大程度上介于(between)其它节点对之间，其中$\sigma \left(j,k|i\right)$ 表示节点j到节点k经过节点i的最短路径数，$\sigma \left(j,k\right)$ 为节点j到节点k的最短路径数。

$BC\left(v_i\right)={\displaystyle {\sum }_{i\ne j\ne k}\frac{\sigma \left(j,k|i\right)}{\sigma \left(i,k\right)}}$ (2)

3) 紧密度中心性

紧密度中心性的思想是：如果一个节点与许多其他节点都很接近，那么节点处于网络中心位置：

$CC{v}_i=\frac{1}{{\displaystyle {\sum }_{j\in V}{d}_{ij}}}$ (3)

其中$d_{ij}$ 为节点i到节点j的最短距离。

2.2. 基于局部领域信息的中心性算法

2.2.1. 算法描述

通常认为，网络中度数最大的节点最重要，但实际上节点的重要性不仅取决于度数，还与邻居节点的信息贡献有关。如图1所示，一个小型网络被分为三块，尽管某节点的度数小于其邻居，但当该节点受攻击时，网络迅速分裂为三个独立部分，破坏性最大。度数仅表示节点直接连接的边数，无法区分相同度数的节点差异，尤其对于“桥节点”，虽然连接度不高，但在网络中地位关键。此外，从信息传播角度看，节点是各块间信息传输的必经之路，因此信息通过该节点能更广泛传播。信息量可用于衡量节点的重要性。

Figure 1. Small networks

图1. 小型网络

通过衡量信息在网络中的流通来衡量节点的重要性，计算公式如下：

${\text{LNI}}_a={\displaystyle {\sum }_{i\in {\Gamma }_a}{F}_{ai}}$ (4)

$F_{ai}=-\left[p_{ai}\log p_{ai}+\left(1-p_{ai}\right)\log \left(1-p_{ai}\right)\right]$ (5)

$p_{ai}=\frac{k_i}{{\displaystyle {\sum }_{j\in {\Gamma }_a}{k}_j}}$ (6)

其中$k_a$ 表示节点a的度数，${\Gamma }_a$ 表示节点a的一阶邻居。

为了更有效筛选出核心节点，比如“桥节点”，将符合条件的节点邻居的重要性叠加到节点本身，来进一步区分节点的重要程度。同时，在信息传播方面，存在一定阈值，例如在疾病传播模型中，当感染阈值大于感染节点与易感节点之间的阈值时，疾病才可以进行传播；当感染阈值小于感染节点与易感节点之间的阈值时，不进行传播。基于上述思想，将符合条件的节点邻居的重要性叠加到节点本身来进一步区分节点的重要程度。计算公式如下：

$f\left(x\right)=\{\begin{array}{l}x,\text{if}x>0\\ 0,\text{otherwize}\end{array}$ (7)

$\text{LNIF}\left(i\right)={\displaystyle {\sum }_{j\in \Gamma \left(i\right)}f\left(\text{LNI}\left(i\right)-\text{LNI}\left(j\right)\right)}$ (8)

若根据节点的度数来确定节点的重要性，则可能会忽略节点的信息，如图1中的节点a。但是LNIF算法综合考虑了节点的二阶内邻居信息以及信息传播的因素来衡量节点的重要性值，若某节点的LNIF值越大，则说明该节点在网络中越不能被替代，其重要性就越高，节点就越重要。

算法描述
输入：网络$G=\left(V,E\right)$
输出：节点的LNIF重要性值
对于节点a：
	对于节点a的邻居节点i：
		$p_{ai}=\frac{k_i}{{\displaystyle {\sum }_{j\in {\Gamma }_a}{k}_j}}$
		$F_{ai}=-\left[p_{ai}\log p_{ai}+\left(1-p_{ai}\right)\log \left(1-p_{ai}\right)\right]$
	结束
	${\text{LNI}}_a={\displaystyle \sum }_{i\in {\Gamma }_a}{F}_{ai}$
结束
对于网络中的节点：
	对于节点N(node)的邻居节点neighbour (nbr)：
		如果$f\left(\text{LNI}\left(\text{node}\right)-\text{LNI}\left(\text{nbr}\right)\right)$ ：
			$\text{LNIF}\left(\text{node}\right)=\text{LNIF}\left(\text{node}\right)+f\left(\text{LNI}\left(\text{node}\right)-\text{LNI}\left(\text{node}\right)\right)$
		结束
	结束
结束

以图2中的节点0为例来说明算法第一部分如何计算，首先计算节点a与它全部邻居节点的F值，这里计算得到每个节点的结果如下：$F_{01}=0.391$ ，$F_{02}=0.619$ ，$F_{03}=0.890$ ，$F_{04}=0.779$ ，$F_{05}=0.779$ 。对于节点0来说，$\text{LNI}\left(0\right)=F_{01}+F_{01}+F_{01}+F_{01}+F_{01}=3.46$ ，同理可以求出剩下几个节点的E值。

Figure 2. Algorithm illustration diagram

图2. 算法说明图

2.2.2. 时间复杂度分析

设网络$G=\left(V,E\right)$ 中含有的节点数为N，边数为M，整个网络的平均度为$\langle k\rangle$ 。由图3可以知道，首先计算节点的E值，这里面包含了2个循环，一个大循环和一个小循环。其中大循环需要遍历全部节点，而小循环需要遍历每个节点的邻居节点，所以这两个循环的时间复杂度为$O\left(\langle k\rangle N\right)$ 。当计算完全部节点的E值后，需要计算各节点的LIE值，此时也包含两个循环，与上一步一样，其时间复杂度为$O\left(\langle k\rangle N\right)$ ，所以本文的LIE算法的总时间复杂度为$O\left(2\langle k\rangle N\right)~O\left(N\right)$ 。

Figure 3. Flow chart of LNIF algorithm

图3. LNIF算法流程图

2.3. 评价标准分析

基于复杂网络的鲁棒性对节点重要性的结果进行评价，主要采用网络平均度、网络效率和最大连通子图系数三个指标来量化移除节点及其连边后，网络连通性和网络结构受到的影响，以此来评价节点的结构重要性。此外还有基于网络的传播学原理来衡量节点的重要性算法，如SI算法、SIR算法等，在这些算法中节点的重要性是通过该节点的平均传播范围决定。在本文中将采用网络平均度、网络效率、最大连通子图系数和SIR传播模型这4个指标来衡量LNIF算法的优越性。

2.3.1. 最大连通子图系数

在社会关系中，如果一个人没有任何朋友，或者一群人除他们外没有别的朋友，那么在整个网络中，这个(群)人就是孤立存在的，对于整个网络来说，是不连通的网络。对于复杂网络来说，任何一个节点的行为都有可能影响整体网络的连通性，而最大连通子图系数是用来评估网络连通性的指标。将网络中的所有节点按重要性排序算法进行排序，移除节点后，对网络连通性的影响。最大连通子图系数(G)的计算公式如下：

$G=\frac{r}{n}$ (9)

其中，r表示移除节点后的网络中的最大连通子图系数的节点数目，n表示网络的节点数量。若最大连通子图系数随着节点移除而变小的趋势越明显，说明节点重要性排序算法越准确。

2.3.2. 网络效率

利用网络中节点间信息交换的效率来评价节点重要性排序算法。使用网络效率来量化网络中交换信息的效率，用于评价网络连通性的强弱，当移除某个节点以及所有的连边时，网络某些路径被切断使得一些节点间的最短路径变大，从而增加了整个网络的平均路径长度，影响网络的信息连通性。网络效率(ED)计算公式如下：

$\text{ED}=\frac{1}{n\left(n-1\right)}{\displaystyle {\sum }_{i\ne j\in V}\frac{1}{d_{ij}}}$ (10)

其中，n表示网络的节点数量，$d_{ij}$ 表示节点i和j的最短路径。当节点i和节点j之间不存在可达路径时，$d_{ij}=+\infty$ ，而$1/d_{ij}=0$ ，在无向图中，网络效率的变化范围是$\left[0,1\right]$ 。通过删除一定数量的节点，模拟现实世界中网络遭受攻击时的效果，通过计算网络被攻击前后网络效率下降的比例来量化衡量节点重要性评价指标的准确性。

2.3.3. 平均度

网络中所有节点i的度$k_i$ 的平均值称为网络的平均度，记为$\langle k\rangle$ ，其计算公式如下：

$\langle k\rangle =\frac{{\displaystyle {\sum }_{i=1}^N{k}_i}}{N}$ (11)

2.3.4. SIR传播模型

SIR传播模型是经典的传染病模型，用于评估节点传播能力，其中S、I、R分别表示易感者、感染者和恢复者。由于网络信息传播与传染病传播规律相似，SIR模型被广泛应用于研究信息传播及其演化规律。它可以模拟计算机病毒在通信网络、危机在经济网络、谣言在社交网络中的传播。因此，节点重要性可通过SIR模型在网络上进行传播模拟获得。

2.4. 实验数据集

由于不同的网络具有不一样的结构与特征，为了验证LNIF算法的有效性，本文共使用12个数据集，包括真实网络数据集11个：Football，Adjnoun，Cond-mat，Karate，Dolphins，Polbooks，Polblogs，Power，Hep-th，As-22july06，Astro-ph以及1个人工模拟网络NW，数据集的拓扑统计特征如表1所示。其中N和M分别代表数据集网络总节点数与总连边数，$\langle k\rangle$ 表示平均度数，$K_{\max }$ 表示网络中节点的最大度数，C表示网络中的平均集聚系数。

Football数据集：2000年美国秋季常规赛期间学院之间的美式橄榄球比赛网络[25]；

Adjnoun数据集：Charles Dickens的小说David Copperfield中常用形容词和名词的邻接网络[26]；

Cond-mat数据集：该数据集是1995年到1999年凝聚态物理方面的合作网络数据集[27] [28]。

Karate数据集：该数据集为美国一所大学空手道俱乐部成员之间的社交网络[29]；

Dolphins数据集：该数据集是新西兰62只海豚之间的关系网络[30] [31]；

Polbooks数据集：该数据集是在2004年美国总统大选期间出版的书籍网络[32]；

Ploblogs数据集：该数据集是2004年美国总统大选前2个月内网络上自由派与保守派之间的互动情况，在该数据中，节点表示博客，连边表示博客之间存在超链接[33]；

Power数据集：该数据集是美国西部各州电网的拓扑结构，其节点表示变压器、变电站、发电机，而连边则表示高压输电线[34]；

Hep-th：高能理论合作，科学家在高能理论电子印刷档案上的预印的加权网络[27] [35]。在该网络中共有8361个节点和15,751条连接关系。

As-22july06数据集：该数据集是Newman收集的在自治系统级别上的互联网结构的对称快照[36]；

Astro-ph数据集：该数据集是1995年到1999年中科学家在天体物理学方面的合著网络[37]，其中节点表示科学家，连边表示科学家之间的合作关系；

NW网络：NW网络采用随机增加节点的连边来取代边的随机重连[34] [38]。在本文NW网络的参数设置为$N=500,k=3,p=0.5$ 。由于模型每次成的连边数以及平均度$\langle k\rangle$ 等不一致，在本文中，NW实验结果均取20次的均值作为最终结果。

Table 1. Topological characteristics of the experimental data set network

表1. 实验数据集网络的拓扑特征

数据集	N	M	<K>	$k_{\max }$	C
Adjnoun	112	425	7.59	49	0.17
Football	115	613	10.66	12	0.40
Dolphins	62	159	5.13	12	0.26
Karate	34	78	4.59	17	0.57
Polbooks	105	441	8.40	25	0.49
Polblogs	1490	16,718	22.44	351	0.26
Power	4941	6594	2.67	19	0.08
Hep-th	8361	15,751	3.77	50	0.77
As-22july06	22,963	48,436	4.22	2390	0.23
Cond-mat	16,726	47,594	5.69	107	0.62
Astro-ph	16,706	121,251	14.52	360	0.64
NW	500	750.05	3.0	6.55	0.003

3. 结果

3.1. 平均度结果

基于上述的其中6个真实数据集和一个模拟网络，本文将采用同样是基于局部信息的Degree、H-index [21]、SC [39]、WL [40]、K-shell [41]与本文的LNIF算法进行对比和分析。根据6种算法得到的节点排序结果，以静态攻击的方式将网络中的节点按照排序结果进行移除，模拟网络遭受攻击时网络平均度<k>的变化情况，以此来评价算法的准确性。本文所有实验均采用Python 3.7。

图4展示了不同节点重要性算法下，移除节点后网络平均度的变化，横坐标f表示移除节点比例，纵坐标表示平均度变化。实验结果如图4(a)~(f)所示。在图4(a)的karate网络中，LNIF算法在移除相同比例节点时下降最快，前20%与WL、SC、Degree算法曲线重合，超过20%后LNIF曲线位于左下方，最先使$\langle k\rangle$ 降至0。图4(b)的Dolphins网络中，前40%时LNIF与Degree算法曲线接近，超过40%后LNIF曲线下降最快，仅需移除约60%节点即可使$\langle k\rangle$ 降至0，而其他算法需移除约80%。图4(c)的Adjnoun网络中，前30%时LNIF与Degree算法位于左下方，超过30%后LNIF曲线下降最快，最先使$\langle k\rangle$ 降至0。图4(d)的Football网络中，前10%时除H-index和K-shell外，其余算法曲线接近，超过10%后LNIF曲线位于最下方。图4(e)的Polbooks网络中，LNIF曲线与图4(a)类似，超过20%后表现最优。图4(f)的Polblogs网络中，除K-shell外，各算法曲线接近，但LNIF仍位于最下方。图4(g)的NW网络模型中，LNIF曲线下降幅度更大，更为陡峭。

(a) Karate (b) Dolphins

(c) Adjnoun (d) Football

(e) Plobooks (f) Ploblogs

(g) NW

Figure 4. Changes of the average degree <k> of the network under different attack methods

图4. 在不同攻击方法下网络的平均度<k>的变化

3.2. 网络效率结果

基于上述的其中6个真实数据集，本文将采用同样是基于局部信息的Degree、H-index [21]、SC [39]、WL [40]、K-shell [41]算法与本文的LNIF算法进行对比和分析。根据6种算法得到的节点排序结果，以静态攻击的方式将网络中的节点按照排序结果进行移除，模拟网络遭受攻击时网络效率ED的变化情况，以此来评价算法的准确性。

图5展示了不同节点重要性算法下，移除节点后网络效率的变化，横坐标f表示移除节点比例，纵坐标表示网络效率。实验仅展示移除80%节点的情况，因网络此时已基本崩溃，可减少运行时间。在图5(a)的Karate网络中，LNIF算法初始略逊于K-shell，但之后表现最优。图5(b)的Dolphins网络中，LNIF算法在前20%与Degree、WL、SC算法重合，20%~40%时与Degree算法表现最佳，超过40%后LNIF算法显著优于其他算法。图5(c)的Adjnoun网络中，LNIF算法基本最优，仅小部分略逊于Degree算法。图5(d)的Football网络中，LNIF算法下降速度远超其他算法。图5(e)的Plobooks网络中，LNIF算法在前20%与Degree、WL、SC算法接近，随移除比例增加，优势愈发明显。图5(f)的Ploblogs网络中，LNIF算法除初始部分外，后续表现最佳，最先使网络效率降至0。图5(g)的NW网络模型中，LNIF算法曲线下降速率更快，优于其他算法。

3.3. 最大连通子图系数结果

基于上述的其中6个真实数据集，本文将采用同样是基于局部信息的Degree、H-index [21]、SC [39]、WL [40]、K-shell [41]算法与本文的LNIF算法进行对比和分析。根据6种算法得到的节点排序结果，以静态攻击的方式将网络中的节点按照排序结果进行移除，模拟网络遭受攻击时最大连通子图系数G的变化情况，以此来评价算法的准确性。

(a) Karate (b) Dolphins

(c) Adjnoun (d) Football

(e) Plobooks (f) Ploblogs

(g) NW

Figure 5. Changes in ED of network efficiency under different attack methods

图5. 在不同攻击方法下网络的网络效率ED的变化

图6展示了不同节点重要性算法下，移除节点后最大连通子图系数的变化，横坐标f表示移除节点比例，纵坐标表示最大连通子图系数。实验结果如图6(a)~(f)所示。在图6(a)的Karate网络中，LNIF算法初始略差，但后续表现最优。图6(b)的Dolphins网络中，LNIF算法在前30%与Degree算法各有优劣，超过30%后逐渐领先其他算法。图6(c)的Adjnoun网络中，LNIF算法曲线基本处于左下方，仅部分略逊于Degree和WL算法。图6(d)的Football网络中，前40%各算法曲线重合，超过40%后LNIF算法下降趋势明显，更能降低网络连通性。图6(e)的Plobooks网络中，LNIF算法在前40%略逊于Degree和SC算法，与WL算法接近，但优于H-index和K-shell算法；超过40%后逐渐体现优势，处于其他算法曲线下方。图6(f)的Polblogs网络中，除重合部分外，LNIF算法均表现最佳。图6(g)的NW网络模型中，LNIF算法更能降低网络连通性，而K-shell算法曲线为直线。

(a) Karate (b) Dolphins

(c) Adjnoun (d) Football

(e) Plobooks (f) Ploblogs

(g) NW

Figure 6. The change of the maximum connectivity subgraph coefficient G under different attack methods

图6. 在不同攻击方法下网络的最大连通子图系数G的变化

3.4. SIR实验结果

在SIR实验中，设置的SIR的相关参数为感染概率为0.05，恢复概率为0.01，设置感染轮数为30，取不同的初始感染比例a = 0.02和a = 0.03作为感染源，所有结果均取100次均值。

基于上述的其中5个真实数据集，本文将采用同样是基于局部信息的Degree、H-index [21]、SC [39]、WL [40]、K-shell [41]算法与本文的LNIF算法进行对比和分析。根据6种算法得到的节点排序结果，选取不同的感染比例来衡量算法的传播能力。对于同一个数据集来说，不同算法得到的节点排序结果往往不同，所以选取排序结果的前面部分作为感染源，以此来衡量算法的优劣。

图7表示的是在同一个网络中采用不同的节点重要性算法下，选取感染比例为0.02时，每次时间下感染比例的变化，其中横坐标f(t)表示感染时间，纵坐标表示每次时间下的感染比例。实验结果如图7(a)~(e)所示。在图7(a)~(e)的Power、Hep-th、Cond-mat、Astro-ph和As-22july06网络中，LNIF算法的传播性能均优于其余5种算法，尤其是在图7(a)~(c)表现得最为明显，与其他5种算法的感染比例相差最大，而表现最差的算法则是K-shell算法。

图8表示的是在同一个网络中采用不同的节点重要性算法下，选取感染比例为0.03时，每次时间下感染比例的变化，其中横坐标f(t)表示感染时间，纵坐标表示每次时间下的感染比例。实验结果如图8(a)~(e)所示。在图8(a)~(e)的Power、Hep-th、Cond-mat、Astro-ph和As-22july06网络中，LNIF算法的传播性能均优于其余5种算法，在图8(a)中的Power网络中，LNIF算法在第30次时间的感染比例比K-shell算法在第30次时间的感染比例的差值要大于0.2，这说明LNIF算法得到的节点重要性排序结果的传播力更强。LNIF算法在其他数据集上均有最佳的表现。

(a) Power

(b) Hep-th (c) Cond-mat

(d) Astro-ph (e) As-22july06

Figure 7. Changes in the proportion of network infection under different node importance algorithms (a = 0.02)

图7. 在不同节点重要性算法下网络的感染比例变化(a = 0.02)

(a) Power

(b) Hep-th (c) Cond-mat

(d) Astro-ph (e) As-22july06

Figure 8. Changes in the proportion of network infection under different node importance algorithms (a = 0.03)

图8. 在不同节点重要性算法下网络的感染比例变化(a = 0.03)

4. 讨论

节点重要性研究是复杂网络的一个热门方向之一。不同节点重要性算法得到的节点排序往往不同，这主要体现在对节点重要性的定义上的不同[42]-[44]。从网络的拓扑结构来研究节点重要性是常用的一个方法，研究人员在这方面做了很多工作，提出来不少经典的节点重要性算法[45]-[47]。从结构上来说分为基于局部信息和基于全局信息来衡量节点的重要性。本文在此总结对比了几种经典的节点重要性算法，详见表2。为了更直观表示，将设置的平均度$\langle k\rangle$ 简写成k。

Table 2. Comparison of importance algorithms of different nodes

表2. 不同节点重要性算法对比

Algorithm	Information	Time
LNIF	Local	O (2kN)
Degree	Local	O (N)
BC	Global	O (N^3)
CC	Global	O (N^3)
WL	Local	O (M + kN)
K-shell	Node Location	O (M)

在3.1节的平均度实验中，LNIF算法的曲线大多位于图的左下方，表明其节点序列能更快降低网络平均度，比其他算法更有效地移除高度数节点。在3.2节的网络效率实验中，LNIF算法的曲线同样位于左下方，说明其节点排序能更快降低网络效率，当效率降至20%时，网络基本崩溃。实验中，曲线有时会上升，这是由于静态攻击模式下，原本排序靠前的节点(伪核心节点)在网络结构变化后可能不再处于重要位置(如边缘或孤立节点)，移除这些节点可能导致平均度或网络效率不降反升。

在第三节的最大连通子图系数实验中，LNIF算法在几乎所有数据集中均处于不同算法曲线的下方，表明其移除节点后，网络的最大连通子图下降更快，破坏性更大。此外，部分数据集的曲线在初始阶段就呈现快速下降趋势，而另一些则趋于平缓，这与网络结构有关。例如，图6(d)中的Football网络平均度高，节点连接边数多，移除节点时网络仍保持全连通性，直到移除比例超过一定值后，网络才进入非全连通状态。不同算法因移除顺序不同，最大连通子图的变化速率也不同，而LNIF算法的效果最为显著。在3.4节的SIR实验中，通过设置不同感染比例评估LNIF算法的节点排序效果。图7和图8显示，在相关数据集上，LNIF算法的感染曲线高于其他5种算法，表明其节点排序结果的传播能力更强。

在上述实验中，K-shell算法表现较差，主要原因是其将节点分层的结果是粗粒度的，无法区分同数值节点的重要性[48]。H-index算法也存在类似问题，部分H-index值相同的节点在网络中的重要性可能不同，导致结果不够精确。相比之下，本文提出的LNIF算法表现优异，在几乎所有数据集中均表现最佳。综合平均度、网络效率、最大连通子图系数以及SIR实验结果，LNIF算法在多数网络中优于现有的Degree、H-index、WL、SC和K-shell算法。

5. 结论

在复杂网络中，核心节点处于网络中的优势地位，挖掘核心节点具有重要的意义。为了挖掘网络中的重要节点，本文提出一种考虑了节点的拓扑信息以及信息传播的影响的LNIF算法，与基于全局信息的算法相比，该算法只需要计算节点的二阶内邻居信息即可计算节点的重要性值，对于挖掘、寻找大规模网络中的关键节点具有现实意义。

在12个数据集上将本文提出的LNIF算法与其它5种算法(Degree, H-index, WL, SC, K-shell)进行对比，通过平均度、网络效率、最大连通子图系数和SIR来验证LNIF算法的优劣。实验结果表明，LNIF算法要优于同为基于局部信息的Degree算法、H-index算法、WL算法、LC算法以及K-shell算法。

挖掘重要节点，是为了后续的研究做准备，如挖掘团队中的核心人员来管理和维护团队的稳定以及协作任务的精准推荐等。虽然本文提出的LNIF算法能够挖掘重要(核心)节点，但是本文只分析了单层网络的结构，而在多层网络中的节点相互关联，一旦节点失效后，会产生蝴蝶效应从而导致多层网络崩溃，因此下一步研究方向是如何在多层网络中挖掘重要节点。

NOTES

^*通讯作者。