论文部分内容阅读
摘要：在网络病毒的传播过程中，攻击者选择重要节点作为传播源。因此识别和保护这些极少的重要节点对于整个网络环境的安全维护有着至关重要的作用。节点近邻排序方法是最简单直观的面向网络病毒传播的方法，本文对度中心性、半局部中心性和k-壳分解法这三种常用的节点近邻排序方法的原理进行了简明的阐述，最后对这三种节点近邻排序方法做了简单的总结。
关键词：节点近邻；度中心性；半局部中心性；k-壳分解法
1 节点近邻排序方法概述
节点近邻排序方法是最简单直观的面向网络病毒传播的方法，度中心性排序方法考察节点的直接邻居数目；半局部中心性排序方法考虑了节点4层邻居的信息；k-壳分解排序方法可以看作度中心性的一种扩展，该方法根据节点在网络中的位置来定义其重要性，认为越是在核心的节点越重要。
2 度中心性排序方法
在大多数时候，节点的重要性可以用称为“中心性”的指标来表示，其主要思想是节点的重要性等价于该节点与其他节点的连接使其具有的显著性[1]。度中心性（degree centrality）认为一个节点的邻居数目越多，其影响力就越大，这是网络中刻画节点重要性最简单的指标。节点vi的度，记为ki，是指与直接相连的节点的数目，是节点最基本的静态特征。在有向网络中，根据连边的方向不同，节点的度有入度和出度之分。在含权网络中节点度又称为节点的强度（strength），定义为与节点相连的边的权重之和。为了进行比较，定义节点vi的归一化度中心性指标为：
3 半局部中心性排序方法
度中心性指标计算方便简单，但实际效果欠佳。基于全局信息的方法，介数中心性和接近中心性指标，虽然具有较好的刻画节点重要性的能力，但计算复杂度太高难以在大规模网络上使用[2]。为了权衡算法的效率和效果，Chen等人提出了一种基于半局部信息的节点重要性排序方法，简称半局部中心性（semi-local centrality）。
首先定义N（w）为节点vw的两层邻居度，其值等于从vw出发2步内可到达的邻居的数目，然后定义
显然，半局部中心性涉及了节点的四阶邻居信息。用D-S证据理论使本方法在含权网络中可得到相应的应用。
4 k-壳分解法排序方法
在网络中，如果一个节点处于网络的核心位置，即使度较小往往也有较高的影响力；而处在边缘的大度节点影响力往往有限。基于此Kitsak等人提出用k-壳分解法（k-shell decomposition）确定网络中节点的位置，将外围的节点层层剥去，处于内层的节点拥有较高的影响力[3]。
这一方法可看成是一种基于节点度的粗粒化排序方法。具体分解过程如下：网络中如果存在度为1的节点，从度中心性的角度看它们就是最不重要的节点。如果把这些度为1的节点及其所连接的边都去掉，剩下的网络中会新出现一些度为1的节点，再将这些度为1的节点去掉，循环操作，直到所剩的网络中没有度为1的节点为止。此时，所有被去掉的节点组成一个层，称为1-壳（记为ks=1）。对一个节点来说，剥掉一层之后在剩下的网络中节点的度就叫该节点的剩余度。按上述方法继续剥壳，去掉网络中剩余度为2的节点，重复这些操作，直到网络中没有节点为止。更广泛地，可定义初始度为0的孤立节点属于0-壳，即ks=0。网络中的每一个节点属于唯一的一层，显然所有节点均满足k≥ks。由此可推出，大度节点有可能因处于核心位置而拥有较大ks 值，也可能因为处于边缘而具有较小的ks值。用k-壳分解法进行排序，大度节点不一定是重要节点。
5 小结
度中心性排序方法拥有简单、直观、计算复杂度低等特点，其缺点是仅考虑了节点的最局部的信息，在很多情况下不够精确[4]。k-壳分解法排序方法计算复杂度低，在分析大规模网络的层级结构等方面有很多应用，然而此方法在很多场景不能发挥应有的作用以及k-壳分解法的排序结果太过粗粒化[5]，导致节点的区分度不大。
参考文献：
[1]任晓龙，吕琳媛.网络重要节点排序方法综述.科学通报，2014，59：1175-1197.
[2]WengJ，LimEP， Jiang J，etal.Twitterrank： finding topic-sensitive influential twitterers. Proceedings of the third ACM international conference on web search and data mining， ACM Press， 2010
[3]Vitali S， Glattfelder JB， Battiston S. The network of global corporate control. PloS one. 2011
[4]呂琳媛，陆君安，张子柯等.复杂网络观察.复杂系统与复杂性科学. 2010
[5]Peng X-L， Xu X-J， Fu X， et al. Vaccination intervention on epidemic dynamics in networks. Physical Review E. 2013
作者简介：谢娜娜（1985-），女，重庆市江津人，重庆航天职业技术学院教师，硕士研究生，助教，主要研究方向：计算机应用技术及网络技术。
蒋文豪（1982-），女，四川省大竹县人，重庆航天职业技术学院教师，硕士研究生，讲师，主要研究方向：计算机网络与网络信息安全。
关键词：节点近邻；度中心性；半局部中心性；k-壳分解法
1 节点近邻排序方法概述
节点近邻排序方法是最简单直观的面向网络病毒传播的方法，度中心性排序方法考察节点的直接邻居数目；半局部中心性排序方法考虑了节点4层邻居的信息；k-壳分解排序方法可以看作度中心性的一种扩展，该方法根据节点在网络中的位置来定义其重要性，认为越是在核心的节点越重要。
2 度中心性排序方法
在大多数时候，节点的重要性可以用称为“中心性”的指标来表示，其主要思想是节点的重要性等价于该节点与其他节点的连接使其具有的显著性[1]。度中心性（degree centrality）认为一个节点的邻居数目越多，其影响力就越大，这是网络中刻画节点重要性最简单的指标。节点vi的度，记为ki，是指与直接相连的节点的数目，是节点最基本的静态特征。在有向网络中，根据连边的方向不同，节点的度有入度和出度之分。在含权网络中节点度又称为节点的强度（strength），定义为与节点相连的边的权重之和。为了进行比较，定义节点vi的归一化度中心性指标为：
3 半局部中心性排序方法
度中心性指标计算方便简单，但实际效果欠佳。基于全局信息的方法，介数中心性和接近中心性指标，虽然具有较好的刻画节点重要性的能力，但计算复杂度太高难以在大规模网络上使用[2]。为了权衡算法的效率和效果，Chen等人提出了一种基于半局部信息的节点重要性排序方法，简称半局部中心性（semi-local centrality）。
首先定义N（w）为节点vw的两层邻居度，其值等于从vw出发2步内可到达的邻居的数目，然后定义
显然，半局部中心性涉及了节点的四阶邻居信息。用D-S证据理论使本方法在含权网络中可得到相应的应用。
4 k-壳分解法排序方法
在网络中，如果一个节点处于网络的核心位置，即使度较小往往也有较高的影响力；而处在边缘的大度节点影响力往往有限。基于此Kitsak等人提出用k-壳分解法（k-shell decomposition）确定网络中节点的位置，将外围的节点层层剥去，处于内层的节点拥有较高的影响力[3]。
这一方法可看成是一种基于节点度的粗粒化排序方法。具体分解过程如下：网络中如果存在度为1的节点，从度中心性的角度看它们就是最不重要的节点。如果把这些度为1的节点及其所连接的边都去掉，剩下的网络中会新出现一些度为1的节点，再将这些度为1的节点去掉，循环操作，直到所剩的网络中没有度为1的节点为止。此时，所有被去掉的节点组成一个层，称为1-壳（记为ks=1）。对一个节点来说，剥掉一层之后在剩下的网络中节点的度就叫该节点的剩余度。按上述方法继续剥壳，去掉网络中剩余度为2的节点，重复这些操作，直到网络中没有节点为止。更广泛地，可定义初始度为0的孤立节点属于0-壳，即ks=0。网络中的每一个节点属于唯一的一层，显然所有节点均满足k≥ks。由此可推出，大度节点有可能因处于核心位置而拥有较大ks 值，也可能因为处于边缘而具有较小的ks值。用k-壳分解法进行排序，大度节点不一定是重要节点。
5 小结
度中心性排序方法拥有简单、直观、计算复杂度低等特点，其缺点是仅考虑了节点的最局部的信息，在很多情况下不够精确[4]。k-壳分解法排序方法计算复杂度低，在分析大规模网络的层级结构等方面有很多应用，然而此方法在很多场景不能发挥应有的作用以及k-壳分解法的排序结果太过粗粒化[5]，导致节点的区分度不大。
参考文献：
[1]任晓龙，吕琳媛.网络重要节点排序方法综述.科学通报，2014，59：1175-1197.
[2]WengJ，LimEP， Jiang J，etal.Twitterrank： finding topic-sensitive influential twitterers. Proceedings of the third ACM international conference on web search and data mining， ACM Press， 2010
[3]Vitali S， Glattfelder JB， Battiston S. The network of global corporate control. PloS one. 2011
[4]呂琳媛，陆君安，张子柯等.复杂网络观察.复杂系统与复杂性科学. 2010
[5]Peng X-L， Xu X-J， Fu X， et al. Vaccination intervention on epidemic dynamics in networks. Physical Review E. 2013
作者简介：谢娜娜（1985-），女，重庆市江津人，重庆航天职业技术学院教师，硕士研究生，助教，主要研究方向：计算机应用技术及网络技术。
蒋文豪（1982-），女，四川省大竹县人，重庆航天职业技术学院教师，硕士研究生，讲师，主要研究方向：计算机网络与网络信息安全。