Ch8 网络中节点重要性评价

第8章

网络中节点重要性评价8.1几种经典的节点重要性排序方法8.2网络节点重要性排序方法的分类8.3节点重要性排序方法的评价12在复杂网络理论中，节点重要性评价是一项关键任务，它旨在确定网络中哪些节点在结构上或功能上扮演着核心角色。在很多实际情形中都需要衡量网络中节点的重要性。本章首先介绍几种经典的节点重要性排序方法，其次分别从节点近邻、路径、特征向量以及节点移除和收缩这几方面来介绍节点重要性排序方法的简单分类，最后简述如何评价节点重要性的排序方法。8.1几种经典的节点重要性排序方法38.1.1度中心性4度中心性的基本思想是如果一个节点的邻居数目越多，那么该节点就越重要。相同度值的节点在不同规模的网络中可能具有不同的影响力，为了区分具有相同度值的节点重要性，将节点i的归一化处理后的度中心性定义为：度中心性指标的计算非常简单，但它仅考虑了节点的一阶近邻的数目，并未考虑周围邻居节点的重要性，在很多情况下并不能准确地刻画节点重要性。8.1.2介数中心性5

介数中心性的基本思想是在网络中经过节点i的最短路径数目越多，则该节点就越重要。将节点

i的介数中心性定义为：

若没有任何节点间的最短路径经过节点

i，则节点

i的介数中心性为0。8.1.3特征向量中心性6

矩阵形式8.2网络节点重要性排序方法的分类78.2.1基于节点近邻的排序方法8半局部中心性

半局部中心性指标不仅考虑了节点的一阶邻居信息，还考虑了节点的更高阶邻居信息。

定义

为节点w的所有一阶、二阶邻居的数目，计算可得到：

可以得到节点的半局部中心性，将其定义为：

半局部中心性指标涉及了节点的四阶邻居信息。还可以考虑节点更多阶的邻居信息，而当用到的阶数越多时，所使用的信息越接近全局信息。8.2.1基于节点近邻的排序方法9k-壳分解通过确定节点在网络中的位置来衡量节点的重要性网络的k-壳分解示意图8.2.1基于节点近邻的排序方法10k-壳分解过程:（1）删掉网络中度值为1的节点以及与这些节点相连的边；重新计算网络中剩余节点的度值，并删掉新出现的度值为1的节点以及与这些节点相连的边；循环操作，直到网络中不存在度值为1的节点。此时，把所有被删掉的节点组成一层，称为网络的1-壳。（2）在完成步骤（1）的操作后，网络中所有剩余节点的度值至少为2。删掉网络中度值为2的节点以及与这些节点相连的边；重新计算网络中剩余节点的度值，并删掉新出现的度值不超过2的所有节点以及与这些节点相连的边；循环操作，直到网络中所有剩余节点的度值都超过2。将在步骤（2）中所有删掉的节点所组成的一层，称为网络的2-壳。（3）以此类推，不断重复上面的操作，直至网络中所有节点都被划分到相应的壳中。8.2.2基于路径的排序方法11离心中心性

对于网络中的节点i，可以计算它与网络中任意一个节点的距离，将这些距离中的最大值作为节点中心性的度量，即节点的离心中心性。

离心中心性指标容易受到特殊值的影响，如一个节点与网络中的大多数节点的距离都很小，但是与少数节点的距离特别大，这将使该节点的离心中心性指标取得一个大值。8.2.2基于路径的排序方法12

8.2.2基于路径的排序方法13Katz中心性

基于Katz中心性的方法认为短路径比长路径更重要，它通过一个与路径长度相关的因子对不同长度的路径加权。定义节点的Katz中心性为:Katz中心性指标的排序结果接近于局部路径指标。Katz中心性方法主要用在规模不太大，环路比较少的网络中。8.2.2基于路径的排序方法14流介数中心性

流介数中心性考虑了网络中节点间的所有路径数,并认为每条路径的作用是相同的。基本思想是经过一个节点的路径数越多，该节点就越重要。

节点i的流介数中心性定义为：8.2.2基于路径的排序方法15连通介数中心性

连通介数中心性认为短路径比长路径更加重要，因此在计算指标值时，给短路经赋予更大的权值，而给长路径赋予较小的权值。首先给出节点p与节点q之间连通度的定义：

定义节点r的连通介数中心性为:8.2.3基于特征向量的排序方法16PageRank

一个网页的重要性是由链接到该网页的其他网页的数量和质量决定的，如果该网页被其他重要的网页链接的次数越多，那么该网页就越重要。PageRank算法示意图：8.2.3基于特征向量的排序方法17PageRank算法是一个迭代算法，在初始步会给每个节点赋予相同的PageRank值

，并且

。在下一步每个节点会将其自身的PageRank值均分给它所指向的邻居节点，不断进行迭代，直到网络中所有节点的PageRank值达到稳定状态。节点

i在PageRank算法迭代到第

t步时的PageRank值可被定义为：参数c会影响PageRank算法的收敛速度，它的取值越大，PageRank算法的收敛速度就会越快，它通常取值为0.15。8.2.3基于特征向量的排序方法18LeaderRank

当网络中存在孤立节点或不连通子图时，将PageRank算法应用于节点重要性度量时会发生排序不唯一的问题。而LeaderRank算法通过向网络中引入背景节点的方式解决了这一问题。具体过程为：在初始步时，令背景节点的LeaderRank值为

，网络中其他节点的LeaderRank值为：8.2.3基于特征向量的排序方法19节点

i在LeaderRank算法迭代到第

t步时的LeaderRank值可被定义为：LeaderRank算法按照以上公式进行迭代，直到网络中节点的LeaderRank值在时间步达到稳定。此时，背景节点的LeaderRank值将会均分给网络中的其他节点。网络中节点的最终LeaderRank值为：8.2.3基于特征向量的排序方法20

网页的权威值和枢纽值相互影响，HITS算法认为一个网页的权威值等于所有指向它的网页的枢纽值之和，而一个网页的枢纽值等于它指向的所有网页的权威值之和。

设HITS算法在初始步时所有节点的权威值和枢纽值均为1，而节点在第时间步的权威值和枢纽值分别用

和

表示，则：算法在每一步迭代结束后还需要进行归一化处理：8.2.4基于节点移除和收缩的排序方法21

8.2.4基于节点移除和收缩的排序方法22当网络的规模比较大时，节点的动力学重要性的估计值:具有不同匹配特性的网络节点动力学重要性

与

的关系：8.2.4基于节点移除和收缩的排序方法23节点收缩法

将一个节点和它的邻节点收缩成一个新节点，将一个节点和它的邻节点收缩成一个新节点。从社会学的角度讲，社交网络中人员之间联系越方便，人数越少，网络的凝聚程度就越高。因此定义网络的凝聚度为：8.2.4基于节点移除和收缩的排序方法24

节点收缩法主要考察节点收缩前后网络凝聚度的变化幅度，由此判定网络中节点的重要性，故定义节点的重要性指标为：

节点收缩法中节点的重要程度由节点的邻居数量和节点在网络中的位置共同决定。由于每收缩一个节点，需要计算一次网络的平均路径长度，时间复杂度比较高，所以这种方法不适于大规模网络。8.3节点重要性排序方法的评价2526

如果想了解究竟哪种排序算法的效果更好，需要给出一些评价排序方法表现优劣的标准。第一种常见的评价标准就是将不同评价方法的结果与实际调查的结果进行比较，能与调查结果符合更好的评价方法表现更优。但这种实际调查的方法主要适用于小规模网络。第二种评价标准是通过比较移除不同排序方法所识别出的重要节点前后对特定的动力学过程的影响，对动力学结果影响更大的排序算法的表现更优。27

通过移除不同的排序方法所识别出的重要节点，哪种排序方法所识别出的节点对网络的结构破坏更大，表示所对应的排序方法的表现越好。网络的鲁棒性可使用R-指标来刻画。它的基本思想是通过移除网络中的一部分节点后，计算网络中属于最大连通集团的节点数目的比例，它的定义为：由网络的鲁棒性定义，可将网络的脆弱性定义为：8.3.1基于网络的鲁棒性和脆弱性的评价标准28无标度网络中移除节点数目与网络最大连通集团规模的关系8.3.1基于网络的鲁棒性和脆弱性的评价标准29

将不同的排序方法所识别出的重要节点设置为传播源，根据哪种排序方法所识别出的节点能将疾病、信息等传播得更远更广，将其对应的方法判定为表现更优的排序方法。通常会采用疾病传播模型作为排序方法的评价标准。以SIR模型为例来展示基于疾病传播动力学的评价标准。首先，基于不同的排序方法来度量给