近年来，复杂网络在网络安全等领域应用广泛，识别复杂网络中的关键节点，对于理解网络的结构和功能，维持网络的稳定运行具有重要作用^[1]。在实际应用中，对复杂网络中的节点进行重要性排序能够为网络节点的风险评估、重要节点防护和网络中节点的风险处置优先级排序提供依据。然而，现有的关键节点识别方法存在准确性不高和计算复杂度高的问题，因此，设计快速高效的关键节点识别方法是复杂网络以及网络安全领域的研究热点。

目前，针对关键节点识别问题的研究方法有许多，其中，度中心性是基于局部特性的方法，但度中心性没有考虑节点位置及周围节点的影响，其分类效果并不理想^[2]。介数中心性、接近中心性和K-shell方法等是基于全局特性的方法，前两者由于计算复杂度高，不适合节点和边数众多的网络^[3]。K-shell方法为每个节点分配一个K_s值量化节点的重要性^[4]，该方法具有良好的时间复杂度，但难以区分同一层上的关键节点。为解决上述方法的不足，Liu等^[5]根据节点和拥有最大K_s值的节点间最短距离进行排序。Zeng等^[6]考虑网络中余留节点和移除节点的贡献提出混合度分解方法。Namtirtha等^[7]提出了一种为网络中所有边分配权重的改进K-shell方法。Berahmand等^[8]提出了一种局部排序方法识别关键节点，该方法基于重要位置参数衡量节点的重要性。Bae等^[9]提出了扩展的K-shell，但该方法在部分网络中分辨率不足。上述方法分别从不同角度衡量节点的重要性，但是存在一些不足：1) 现有的网络拓扑结构多种多样，部分方法仅考虑网络的局部结构而忽略网络的全局结构；2) 计算复杂度高；3) 在不同的复杂网络中，需要预先设定参数值；4) 方法分辨率低，在网络中识别关键节点的能力较差。

针对上述问题，本文提出了一种基于K-shell的复杂网络关键节点识别方法(K-shell based key node recognition method, KBKNR)，相比于传统方法，该方法综合考虑网络的全局和局部结构，在全局范围内应用K-shell方法将网络分层，在局部范围内提出综合度(comprehensive degree, CD)的概念，综合权衡邻居节点和次邻居节点的影响，从而区分节点重要性。由于KBKNR方法不含自由参数且无需预先测试参数值，因此降低了计算开销。该方法不仅在复杂网络中具有较高的准确性和分辨率，而且在网络安全的实际应用中有助于提高网络安全防护和应急处置效率。

1 相关方法及分析 1.1 K-shell方法

K-shell方法^[10]是一种基于网络全局结构的粗粒化分解方法，根据节点在网络中的位置判断节点的重要性。该方法的处理过程如下。

首先，不断删除网络图G中度为1的节点及其连边，直到网络图中不再出现此类节点，此时将所有被删节点归为1-shell层，并为其分配K_s值，该值为1。其次，不断删除网络中度为2的节点及其连边，将所删节点归为2-shell层，并为其分配K_s值，该值为2。重复上述过程，直到网络图中所有节点均被分层、分配K_s值。其中，K_s值最大的节点所属的层为网络的核心层，处于网络核心层的节点具有最大的影响力。

一个小型网络的K-shell分解示例如图 1所示。图 1中的网络由K-shell方法分成3层，节点1、2、3、4、5、6、9、14、16、17被分配相同的K_s值，但是难以区分其重要程度。针对此缺陷，本研究利用K-shell分解过程中同层节点的不同综合度，进一步区分不同节点的重要程度。

1.2 θ方法

为解决K-shell方法难以区分同一壳层关键节点的缺陷，Liu等^[5]提出θ方法，该方法根据节点与网络核心节点(拥有最大K_s值的节点)间最短距离进行排序，节点距离网络核心节点越近，该节点越重要。该方法可表示为

$ \theta\left(i \mid K_{\mathrm{s}}\right)=\left(K_{\mathrm{s}_{\mathrm{Max}}}-K_{\mathrm{s}}+1\right) \sum\limits_{j \in J} d_{i j}, \quad i \in S_{K_{\mathrm{s}}}. $

(1)

其中：K_sMax为网络中K_s最大值，J为拥有最大K_s值的核心节点集，d_ij是节点i和节点j间的最短距离，S_Ks为所有节点的集合，θ(i|K_s)为节点i的重要性值。

1.3 混合度分解方法

Zeng等^[6]提出混合度分解(mixed degree decomposition, MDD)方法。在MDD方法中，用耗尽度衡量已经移除的节点对指定节点的影响，用剩余度衡量剩余的节点对指定节点的影响。这种采用混合K_s值的改进方法增加了网络分层的层数，但针对不同网络需要调节参数λ的值，以使该方法取得区分节点重要性的最佳效果，在本文所做的对比实验中，λ取0.7。该方法可表示为

$ K_{\mathrm{m}}(i)=K_{\mathrm{r}}(i)+\lambda \times K_{\mathrm{e}}(i). $

(2)

其中，K_m(i)为混合K_s值，K_r(i)为剩余度，K_e(i)为耗尽度。

1.4 扩展的K-shell方法

为改进K-shell方法的不足并区分同层节点的重要性，Bae等^[10]提出了扩展的K-shell方法，即K_s+方法，该方法融合节点度及度的最大值对K-shell进行扩展，该方法可表示为

$ K_{\mathrm{s}} \mathrm{p}(i)=K_{\mathrm{s}} \times\left(K_{\mathrm{Max}}+1\right)+K. $

(3)

其中，K为节点度，K_Max为度的最大值，K_sp(i)为扩展的K_s值。

2 关键节点识别方法 2.1 基于K-shell的关键节点识别方法设计

为改进K-shell方法的不足并实现区分节点重要性的目标，本文针对网络的局部结构特点，提出综合度(comprehensive degree, CD)的概念，节点的综合度定义为

$ C(i)=K(i)+\mu_{i} D(i). $

(4)

其中，K(i)为节点的度，D(i)为节点的次邻居节点个数，μ_i为影响系数。

然后以K-shell和综合度为基础，提出一种基于K-shell的复杂网络关键节点识别方法(K-shell based key node recognition method, KBKNR)。在该方法中，全局结构的影响通过采用K-shell方法衡量，局部结构的影响则通过邻居和次邻居节点对指定节点的影响程度(综合度)衡量。

KBKNR的设计思路为：首先，在全局范围内采用K-shell方法将网络分层，得到每个节点的K_s值并通过其衡量网络的全局特性。其次，在局部范围内综合考虑邻居节点和次邻居节点的影响，计算每个节点的综合度并通过其衡量网络的局部特性。对于网络中的节点，不仅与其直接相连的邻居节点会影响该节点，距离较远的节点也会对其产生影响。为了实现有效区分节点重要性的目标，又降低计算的复杂度，在KBKNR中仅考虑两步邻域，即邻居节点和次邻居节点的影响。由于邻居节点距离指定节点较近，对其影响较大，而次邻居节点距离指定节点较远，对其影响较小，因此将影响系数μ_i设定为0~1并可动态调整，使KBKNR更符合实际情况。

KBKNR的具体过程设计如下。

步骤1：采用K-shell方法将网络分层，得到每个节点的K_s值。

步骤2：计算网络中所有节点的度K(i)和两步邻域内的节点总数N(i)。

步骤3：根据步骤2得到的K(i)和N(i)，得到各个节点的影响系数μ_i，

$ \mu_{i}=\frac{K(i)}{N(i)}. $

(5)

步骤4：根据步骤2得到的K(i)和N(i)，得到次邻居节点个数D(i)，即

$ D(i)=N(i)-K(i). $

(6)

步骤5：根据步骤2得到的K(i)和步骤3、4得到的μ_i、D(i)，得到节点的综合度C(i)，即

$ C(i)=K(i)+\mu_{i} D(i). $

(7)

步骤6：由于同层节点的K_s值相同，难以判断其重要性，故将同层节点根据节点的综合度C(i)进一步区分其重要性：对于K_s值相等的节点，综合度较大的节点更重要。该方法伪代码如图 2所示。

由KBKNR的计算过程可见，该方法不含自由参数，无需预先测试参数值，降低了计算复杂度。

2.2 实例分析

以包括14个节点和20条边的无向无权网络为例(如图 3所示)，首先采用KBKNR对图 3中节点进行排序，然后与其他方法的排序效果进行比较。以节点8为例说明KBKNR的处理过程。

1) 计算节点8的K_s值，得到K_s(8)=2。

2) 计算节点8的度K(8)和两步邻域内节点总数N(8)，由于节点8的邻居节点为5、6、7、9、10、11，次邻居节点为3、12、13、14，因此K(8)=6，N(8)=10。

3) 由式(5)得到节点8的影响系数μ₈，μ₈=6/10=0.6。

4) 由式(6)得到次邻居节点个数D(8)，D(8)=10-6=4。

5) 由式(7)得到节点8的综合度C(8)，C(8)=6+0.6×4=8.4。

重复上述过程，得到图 3中网络全部节点的K_s值和综合度，图 3中网络综合度的计算过程如表 1所示。为了与其他方法进行对比，表 2、表 3分别列出度中心性(DC)^[1]、接近中心性(CC)^[2]、θ方法^[5]、混合度分解(MDD)方法^[6]、介数中心性(BC)^[8]、扩展的K-shell方法(K_s+)^[9]、K-shell方法^[10]和本文方法(KBKNR)得到的节点重要性值和排序结果。表 1—3中，节点列的数字代表节点，K(i) 列为节点i的度，K_s列为节点i的K_s值，N(i)列为两步邻域内节点数，D(i)列为次邻居节点个数，μ_i列为影响系数，C(i)列为综合度。

由表 3可知，度中心性、介数中心性、接近中心性、K-shell等方法分辨率均不高，度中心性方法将整个网络划分成6层，K-shell方法将整个网络划分成2层，而本文的KBKNR将整个网络划分成11层，故KBKNR得到的节点重要性排序范围更广且分辨率更高。

3 实验结果与分析 3.1 实验数据集及实验设计

为了对比分析经典方法和KBKNR在不同复杂网络中的节点识别准确性和分辨率，在6个经典复杂网络上进行关键节点识别(节点重要性排序)对比实验。6个经典复杂网络分别为：1) Zachary网络；2) Dolphins网络；3) Jazz Musicians网络；4) Blogs网络；5) NetScience网络；6) Powergrid网络。上述6个复杂网络的信息如表 4所示，其中，V表示网络节点数目，E表示网络边数，β_th为流行阈值，β为感染概率。

在3.2节中，将以Dolphins网络为对象，对不同方法进行比较和分析。在3.3节中，将利用易感感染恢复(susceptible infected recovered, SIR)模型^[11]、Kendall系数指标^[12]以及单调性指标^[13]对不同方法性能进行评价。在3.4节中，将验证KBKNR方法在网络安全应用中的有效性。

3.2 Dolphins网络实验与结果

在识别复杂网络中的关键节点时，许多节点可能具有相同的重要性值，如在K-shell方法中，同一壳层的节点具有相同的K_s值，很难区分这些节点的重要性差异。故对于性能好的方法，不同的节点应该具有不同的重要性值和排序值。节点重要性值和排序值相同的节点越少，方法对节点的重要性排序范围越广，方法的分辨率越高。

为了比较不同方法的性能优劣，选取Dolphins网络作为实验对象，对DC、BC、CC、K-shell、MDD、θ、K_s+、KBKNR 8种方法进行实验分析，得到各节点的8个重要性值和每种方法得到的节点重要性排序结果，通过比较各个方法得到的节点重要性排序的等级数和具有相同重要性值的节点数目评估方法的性能。图 4—11为8种方法得到的Dolphins网络各节点的重要性值，表 5为8种方法得到的Dolphins网络节点重要性排序Top 10的节点。

由图 4—11和表 5可知，K-shell方法难以区分重要节点，多个节点的K_s值相同。DC方法比K-shell方法的排序范围广，但有很多节点(如节点10、16、19、37、44、51、55)重要性值相同，DC方法仅能将全部节点划分成12个等级。CC方法衡量某节点到其他所有节点距离的远近，其最大不足是得到的节点重要性值会比较接近，且该方法对网络拓扑结构的依赖性强。BC方法无法准确识别处于网络边界的节点的重要性，例如节点5、12、13、17、23、32、36、49、59、61的节点重要性值均为0。K_s+方法将62个节点分成15个等级，MDD方法将62个节点分成23个等级，θ方法将全部节点分成45个等级，因此，θ方法性能优于MDD方法和K_s+方法，但该方法分配给节点1、2、34、51相同的重要性值，而本文提出的KBKNR能够对这4个节点进行区分，将全部62个节点划分成51个不同等级，故KBKNR对网络节点的节点重要性排序范围更广、分辨率更高。此外，由实验结果可见，KBKNR相较于其他方法，在Top 10节点中不存在节点具有相同的重要性值，因此KBKNR在Dolphins网络中的性能最为理想。

3.3 方法性能评价

为了评价不同方法的准确性和分辨率，选取DC、BC、CC、K-shell、MDD、θ、K_s+、KBKNR 8种方法在6个典型复杂网络中进行对比实验。首先，利用SIR模型检验网络中单个节点的传播效率，以此判断节点的重要性。其次，将8种方法得到的节点重要性排序结果与SIR模型得出的节点传播效率排序结果进行比较，计算Kendall相关系数。最后，利用单调性指标评估不同方法区分节点重要性的能力，即检验在节点重要性排序结果中是否存在大量节点具有相同重要性值的情况。

1) SIR模型。

SIR模型的目标是衡量节点在流行病传播过程中的相对重要性^[14]。开始时，只有传播起始节点处于被感染状态，其余节点均处于易感染状态。之后，在每个时间步长，被感染节点以感染概率β将感染传播到邻居节点，最初被感染的节点变成恢复状态，处于恢复状态的节点不能再次被感染。当没有新的被感染节点出现时传播过程结束，此时恢复节点的数量反映初始节点的影响力。当感染概率较大时，流行病能在网络中大范围传播，当感染概率较小时，流行病仅能在小范围内传播。若要疾病在网络中传播并流行，感染概率必须大于流行阈值，流行阈值β_th为

$ \beta_{\mathrm{th}} \approx \frac{\langle k\rangle}{\left\langle k^{2}\right\rangle}. $

(8)

其中，〈k〉是网络的平均度，〈k²〉是网络的平均二阶度。

2) Kendall相关系数。

Kendall相关系数用τ表示，用于检验两个排序序列的相关性，其取值范围为-1~1。τ的定义如下：

$ \tau=\frac{2(C-D)}{N \times(N-1)}. $

(9)

其中，C表示两个序列中拥有一致性的序列对数，D表示不一致的序列对数，N是网络的节点数目。

Qiu等^[4]和Berahmand等^[8]通过一个感染概率β，将不同方法和SIR模型仿真得到的排序结果进行比较，计算τ值。为了便于观察感染概率β和相关系数τ的变化趋势和相关程度，本文模拟SIR模型传播过程，使该模型感染概率在β_th~2×β_th变化，每次以0.1×β_th的步长增加，计算τ值。SIR模型的感染概率β为

$ \beta=\beta_{\mathrm{th}}+\delta \times j. $

(10)

其中，δ为每一步感染概率的增量，j为步数，β_th为传染病流行阈值。

3) 方法准确性实验结果。

采用DC、BC、CC、K-shell、MDD、θ、K_s+、KBKNR 8种方法和SIR模型对Zachary、Dolphins、Jazz、Blogs、NetScience和Powergrid网络进行计算，得到6个网络在不同感染概率下的Kendall相关系数τ(如表 7—12所示)。表 7—12中的β为感染概率，τ为Kendall相关系数值。然后，分别对6个网络中10个感染概率对应的τ求平均值得到每个网络的平均Kendall系数τA(如表 6所示)。

由表 6可知，在Zachary、Dolphins、NetScience、Powergrid网络中，KBKNR得到的节点重要性排序结果和SIR模型得到的节点传播效率排序结果最接近，其平均Kendall系数高于其他方法。这是因为KBKNR不仅考虑节点的全局特征(K_s值)，同时融合节点的局部特征(综合度)，从而提高方法的准确性。6个网络中使感染概率β在β_th~2×β_th变化，每次以0.1×β_th的步长增加，τ的变化趋势如图 12—17所示。τ值越大，则表明方法的准确性越高。由图 14和15可知，在Jazz和Blogs网络中，KBKNR与SIR模型的相关程度略低于其他方法，但平均τ值较高，且在Blogs网络中相关系数τ随着感染概率β的增大而升高，总体趋势是上升的，因此KBKNR在不同的复杂网络中具有较高的准确性。

4) 单调性指标。

对于复杂网络中节点的重要性排序，若每个节点具有不同的节点重要性排序值，则说明方法能够清晰地区分节点的重要性，相同节点重要性排序值的节点越少，则表明方法的分辨率越高。在实验中，使用单调性指标M(R)评价不同方法的分辨率。单调性指标M(R)为

$ M(\mathrm{R})=\left[1-\frac{\sum\limits_{\mathrm{r} \in \mathrm{R}} n_{\mathrm{r}}\left(n_{\mathrm{r}}-1\right)}{n(n-1)}\right]^{2}. $

(11)

其中，R代表节点重要性排序结果，n代表节点重要性排序结果中节点的个数，n_r代表节点重要性排序结果中相同的节点个数。

用M(R)衡量节点重要性排序结果的单调性，如果节点重要性排序结果是完全单调的，则M(R)=1；如果节点重要性排序结果全部相同，则M(R)=0。

5) 方法分辨率实验结果。

在本实验中，通过DC、BC、CC、K-shell、MDD、θ、K_s+、KBKNR 8种方法生成的节点重要性排序列表的单调性检验不同方法的分辨率, 如表 13所示。

由表 13可知，KBKNR得到的节点重要性排序结果在5个网络中具有最高的单调性，其中，在Zachary网络中为0.940 312，在Dolphins网络中为0.983 149，在Jazz网络中为0.998 77，在Blogs网络中为0.999 134，在NetScience网络中为0.912 945。在Powergrid网络中，KBKNR得到的节点重要性排序结果的单调性指标值为0.952 429，略低于θ方法和CC方法。可见，在绝大多数情况下，KBKNR对网络节点的分辨率较为理想。

3.4 网络安全应用中的方法性能验证

为验证KBKNR方法在网络安全应用的可行性和有效性，对真实网络进行关键节点识别和风险评估对比验证实验。该实验包括网络节点风险评估和关键节点识别。实验对象为CAUC某系统的局域网，该局域网络由30台PC机、5台接入交换机、1台汇聚交换机、2台服务器组成，该网络的结构如图 18所示。

在关键节点识别实验中，将该网络中的设备抽象为节点，采用KBKNR方法计算各节点的综合度，并对节点进行节点重要性排序，实验结果如表 14所示。由表 14可知，在该网络中，接入交换机(31, 32, 33, 34, 35)的功能相同，但由于接入交换机所连接的设备数量不同，因此各个接入交换机重要程度不同。汇聚交换机在整个网络中处于最重要的位置，一旦汇聚交换机遭受攻击，将影响整个网络的运行。

在风险评估部分，按照风险评估规范^[15]计算得到该局域网中全部节点(设备)的风险值。数据源为4周的网络管理日志中的网络报警、故障信息以及网络安全软件中的网络攻击检测数据。在该部分实验中，依据资产、报警和故障信息、攻击报警信息，采用基于期望损失的风险评估方法^[16]得到网络中各节点面临的威胁和风险严重程度指标，并计算得到每个节点(设备)的风险值。实验结果如表 15所示。

上述两个实验结果的排序对比如表 16所示。由表 16可见，由KBKNR方法得到的该网络的节点重要性排序与由风险评估得到的网络节点风险值排序的TOP 10是相同的。这个结果表明，由KBKNR方法得到的节点重要性排序结果，能够为网络节点的风险评估、重要节点防护和网络中节点的风险处置优先级排序提供依据。以节点重要性排序为依据，有助于提升网络安全防护和应急处置的效率。

4 结论

本文针对现有的复杂网络关键节点识别方法存在准确性不高和计算复杂性高的问题，提出一种识别复杂网络关键节点的方法KBKNR。首先，通过K-shell方法分解网络，得到能够衡量节点在网络中位置信息的K_s值。然后，根据邻居节点和次邻居节点对指定节点的不同影响程度计算节点的综合度。最后，同时考虑节点的K_s值和综合度区分节点的重要性，对于同一壳层(K_s值相同)的节点，综合度较大的节点更重要。通过在6个典型复杂网络中模拟SIR模型传播过程，利用Kendall相关系数评价方法的准确性，单调性指标评价方法的分辨率，在网络安全应用中验证方法的有效性。实验结果表明，与其他方法相比，本文方法不仅计算复杂度较低，而且针对不同复杂网络有着较高的准确性和分辨率，能够有效识别出复杂网络中的关键节点，提升网络安全防护和应急处置的效率，为下一步保护关键节点提高网络的安全性提供理论基础。