[数据结构与算法] 节点中心性：度中心性、特征向量中心性、Katz中心性、介数中心性

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 节点中心性：度中心性、特征向量中心性、Katz中心性、介数中心性 -> 正文阅读

[数据结构与算法]节点中心性：度中心性、特征向量中心性、Katz中心性、介数中心性

一、度中心性(Degree Centrality)

????如果有许多其他节点连接到某个节点，那么后者可以被认为是重要的。因此，可以基于一个节点的度测量它的中心性。更具体地说，对于节点 $v_i$ ，其度中心性可以定义为：
$c_d(v_i)=d(v_i)=\sum_{j=1}^NA_{i,j}$
????由上面的公式可以知道，节点 $v_1$ 与 $v_5$ 的度中心性都是3，而节点 $v_2$ 、 $v_3$ 和 $v_4$ 的度中心性都是2。

二、特征向量中心性(Eigenvector Centrality)

????度中心性认为与多个节点相邻的节点是重要的，且认为所有邻居的贡献度是一样的。然而，这些相邻节点本身的重要性是不同的，因此它们对中心节点的影响不同。给定一个节点 $v_i$ ，特征向量中心性用它的相邻节点的中心性来定义 $v_i$ 的中心性：
$c_e(v_i)=\frac{1}{\lambda}\sum_{j=1}^NA_{i,j}{\cdot}c_e(v_j)$ ????也可以表达为矩阵的形式：
$c_e(v_i)=\frac{1}{\lambda}A{\cdot}c_e$ ????式中， $c_e{\in}R^N$ 是一个包含所有节点的特征向量中心性的向量，这个式子也可以表达为：
$\lambda{\cdot}c_e(v_i)=A{\cdot}c_e$ ????显然， $c_e$ 是矩阵的特征向量， $\lambda$ 是其对应的特征值。一个邻接矩阵 $A$ 存在多对特征向量和特征值。中心性的值通常为正数，所以选择中心性需要考虑所有元素均为正数的特征向量。根据Perron-Frobenius定理，一个元素全为正的实方阵具有唯一的最大特征值，其对应的特征向量的元素全为正。因此可以选择最大的特征值 $\lambda$ ，将它的相应的特征向量作为中心性向量。
????通过上面的公式进行计算，可以算出示例图中最大的特征值是2.481，对应的特征向量[1, 0.675, 0.675, 0.806, 1]。因此， $v_1,v_2,v_3,v_4,v_5$ 的特征向量中心性分别是1,0.675,0.675,0.806,1。注意 $v_2$ 、 $v_3$ 和 $v_4$ 的度都是2，但是 $v_4$ 的特征向量中心性比另外两个节点的都要高，因为它和 $v_1$ 、 $v_5$ 两个高特征向量中心性的节点直接相连。

三、Katz中心性(Katz Centrality)

????Katz中心性是特征向量中心性的一个变体，它不仅考虑了邻居的中心性，而且包含了一个常数来考虑中心节点本身。具体来说，节点 $v_i$ 的Katz中心性可以定义为：
$c_k(v_i)={\alpha}\sum_{j=1}^NA_{i,j}c_k(v_j)+\beta$ ????式中， $\beta$ 是一个常数。一个图中所有节点的Katz中心性可以用矩阵形式表示为：
$c_k={\alpha}Ac_k+\beta\\ (I-{\alpha}{\cdot}A)c_k=\beta$ ????式中， $c_k{\in}R^N$ 表示所有节点的Katz中心性的向量； $\beta$ 表示一个包含所有节点的常数项 $\beta$ 的向量； $I$ 表示单位矩阵。值得注意的是，如果令 ${\alpha}=\frac{1}{\lambda_{max}}$ 和 $\beta=0$ ，那么Katz中心性等价于特征向量中心性，其中 ${\lambda}_{max}$ 是邻接矩阵 $A$ 的最大特征值。 $\alpha$ 的选择对于Katz中心性非常关键：大的 $\alpha$ 值可能使矩阵 $I-{\alpha}{\cdot}A$ 变成病态矩阵，而小的 $\alpha$ 可能使中心性变得没有意义，因为它总是给所有节点分配非常相似的分数。在实践中，经常令 ${\alpha}<\frac{1}{\lambda_{max}}$ ，这就保证了矩阵 $I-{\alpha}{\cdot}A$ 的可逆性，那么 $c_k$ 可按如下方式计算：
$c_k=(I-{\alpha}{\cdot}A)^{-1}\beta$ ????令 $\beta=1,\alpha=\frac{1}{5}$ ，经过计算可得示例图中节点 $v_1$ 和 $v_5$ 的Katz中心性都是2.16， $v_2$ 和 $v_3$ 的Katz中心性是1.79， $v_4$ 的Katz中心性是1.87。

四、介数中心性(Betweeness Centrality)

????前面提到的几种中心性基于和相邻节点的连接。另一种度量节点重要性的方法是检查它是否在图中处于重要位置。具体来说，如果有许多路通过同一个节点，那么该节点处于图中的一个重要位置。节点 $v_i$ 的介数中心性的定义如下：
$c_b(v_i)=\sum_{v_s{\neq}v_i{\neq}v_t}\frac{\sigma_{st}(v_i)}{\sigma_{st}}$ ????式中， $\sigma_{st}$ 表示所有从节点 $v_s$ 到节点 $v_t$ 的最短路的数目（此处不区分 $v_s$ 与 $v_t$ ）； $\sigma_{st}(v_i)$ 表示这些路中经过节点 $v_i$ 的路的数目。为了计算介数中心性，需要对所有可能的节点对求和。因此，介数中心性的值会随着图的增大而增大。为了使介数中心性在不同的图中具有可比性，需要对它进行归一化（normalization）。一种有效的方法是将所有节点的中心性除以其中的最大值。由上面介数中心性的公式可知，当任意一对节点之间的最短路都通过节点 $v_i$ 时，介数中心性达到最大值，即 $\frac{\sigma_{st}(v_i)}{\sigma_{st}}=1,{\forall}v_s{\neq}v_i{\neq}v_t$ 。在一个无向图中，共有 $\frac{(N-1)(N-2)}{2}$ 个不包含节点 $v_i$ 的节点对，所以介数中心性的最大值是 $\frac{(N-1)(N-2)}{2}$ 。所以 $v_i$ 归一化后的介数中心性 $c_{nb}(v_i)$ 可以定义为：
$c_nb(v_i)=\frac{2{\times}\sum_{v_s{\neq}v_i{\neq}v_t}\frac{\sigma_{st}(v_i)}{\sigma_{st}}}{(N-1)(N-2)}$ ????在示例图中，节点 $v_1$ 和 $v_5$ 的介数中心性是 $\frac{2}{3}$ ，而它们归一化后的中心性是 $\frac{1}{4}$ 。节点 $v_2$ 和 $v_3$ 的介数中心性是 $\frac{1}{2}$ ，而它们归一化后的中心性是 $\frac{1}{12}$ 。节点 $v_4$ 的介数中心性和归一化的中心性均为0。