参考资料

1. 《社会媒体挖掘》

中心性（centrality）用来度量结点在网络中的重要性。对于单个结点或由多个结点组成的群体都可以定义中心性。

单个结点中心性

单个结点中心性主要分为度中心性、特征向量的中心性、Katz中心性、PageRank、中间中心性、接近中心性。

度中心性

针对无向图，结点$v_i$的度中心性为$C_d\left(v_i\right)=d_i$，即为结点的度；
针对有向图，中心性既可以是入度（视为声望）$C_d\left(v_i\right)=d_i^{in}$，也可以是出度（视为合群性）$C_d\left(v_i\right)=d_i^{out}$，还可以是二者的和$C_d\left(v_i\right)=d_i^{in}+d_i^{out}$。

特征向量中心性

特征向量中心性是想结合结点邻居的中心性作为该结点的中心性：

$c_e\left(v_i\right)=\frac{1}{\lambda }{\sum }_{j=1}^n{A}_{j,i}{c}_e\left(v_j\right)$

其中，$\lambda$是个常量，$c_e\left(v_i\right)$是结点$v_i$的中心性。
将上式写成矩阵形式，特征向量中心性实际上是对网络的邻接矩阵$A$进行特征分解，选择最大特征值对应的特征向量作为各结点的中心性。

$\lambda C_e=A^T{C}_e$

其中，$C_e$是邻接矩阵$A^T$的特征向量，$\lambda$是对应的特征值。
但是中心性要求大于0，所以引入Perron-Frobenius Theorem：
假设$A\in {\text{R}}^{n\times n}$是[强]连通图的邻接矩阵，或者$A:A_{i,j}>0$（即一个正的$n\times n$的矩阵），存在一个正实数（Perron-Frobenius特征值）${\lambda }_{max}$，满足${\lambda }_{max}$是矩阵$A$的特征值，并且$A$的其余特征值均严格小于${\lambda }_{max}$。${\lambda }_{max}$所对应的特征向量为$\mathbf{v}=\left(v_1,v_2,\cdot \cdot \cdot ,v_n\right)$，满足$\forall v_i>0$。

Katz中心性

对于入度为0的结点，其特征向量中心性为0。为了解决这个问题，加入了一个偏差项$\beta$：

$c_{Katz}\left(v_i\right)=\alpha {\sum }_{j=1}^n{A}_{j,i}{c}_{Katz}\left(v_j\right)+\beta$

写为向量形式：

$C_{Katz}=\alpha A^T{C}_{Katz}+\beta \text{1}$

移项得：

$C_{Katz}=\beta {\left(I-\alpha A^T\right)}^{-1}\cdot \text{1}$

注意：当$\text{det}\left(I-\alpha A^T\right)=0$时，矩阵$I-\alpha A^T$将不可逆。实际中，一般选择$\alpha <1/\lambda$以便正确计算中心性。

PageRank

PageRank则是在Katz中心性的基础上，对结点传递出的中心性对其出度作了归一化，这显然是合理的。

$C_p\left(v_i\right)=\alpha {\sum }_{j=1}^n{A}_{j,i}\frac{C_p\left(v_j\right)}{d_j^{out}}+\beta$

表示为矩阵形式：

$C_p=\alpha A^T{D}^{-1}{C}_p+\beta \text{1}$

改写为：

$C_p=\beta {\left(I-\alpha A^T{D}^{-1}\right)}^{-1}\cdot \text{1}$

类似于Katz中心性，实际上，选取$\alpha <1/\lambda$，其中$\lambda$是矩阵$A^T{D}^{-1}$的最大特征值。在无向图中，由于矩阵$A^T{D}^{-1}$的最大特征值为$\lambda =1$，所以$\alpha <1$。

中间中心性

中间中心性计算其他结点间通过结点$v_i$的最短路径数。

$C_b\left(v_i\right)={\sum }_{s\ne t\ne v_i}^{}\frac{{\sigma }_{st}\left(v_i\right)}{{\sigma }_{st}}$

通俗地讲，结点$s$与结点$t$间存在许多条最短路径，共${\sigma }_{st}$，其中有${\sigma }_{st}\left(v_i\right)$条是通过结点$v_i$的，如果这个数量越大，说明该结点越重要，极端情况下，所有路径都需要经过它，那么它也就是枢纽站，比值就为1。所以结点$v_i$的最大值为：

$C_b\left(v_i\right)={\sum }_{s\ne t\ne v_i}^{}1=2\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$

则归一化后的中间中心性：

$C_b^{norm}\left(v_i\right)=\frac{C_b\left(v_i\right)}{2\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)}$

对无向图，有${\sum }_{s\ne t\ne v_i}^{}\frac{{\sigma }_{st}\left(v_i\right)}{{\sigma }_{st}}=2{\sum }_{s\ne t\ne v_i,s<t}^{}\frac{{\sigma }_{st}\left(v_i\right)}{{\sigma }_{st}}$，所以中心性乘以2。

接近中心性

接近中心性的思想是，趋于中心的结点，满足与其他结点之间有最小平均最短路径。接近中心性定义为：

$C_c\left(v_i\right)=\frac{1}{{\bar{l}}_{v_i}}$

其中，${\bar{l}}_{v_i}=\frac{1}{n-1}{\sum }_{v_j\ne v_i}^{}{l}_{i,j}$是结点$v_i$与其他结点之间的平均最短路径。最短路径越小，那么结点的中心性会越高。

群体中心性

群体中心性的定义与单个结点的中心性相差不大，就是将一个群体视为一个结点。

群体度中心性

群体度中心性，是群体外部的结点连接到群体内部结点的数目。

C d g r o u p ( S ) = ∣ { v i ∈ V − S ∣ v i 连 接 到 v j ∈ S } ∣ C_{d}^{group}left ( Sright )=left | left {v_{i}in V-S|v_{i}连接到v_{j}in Sright }right | Cdgroup​(S)=∣{vi​∈V−S∣vi​连接到vj​∈S}∣

与度中心性相似，可以利用有向图中的入度或出度。同样，该值可以进行归一化。

群体中间中心性

和中间中心性相似，将群体中间中心性定义为：

$C_b^{group}\left(S\right)={\sum }_{s\ne t,s\notin S,t\notin S}^{}\frac{{\sigma }_{st}\left(S\right)}{{\sigma }_{st}}$

群体接近中心性

群体接近中心性定义为：

$C_c^{group}\left(S\right)=\frac{1}{{\bar{l}}_S^{group}}$

其中，${\bar{l}}_S^{group}=\frac{1}{|V-S|}{\sum }_{v_i\notin S}^{}{l}_{S,v_j}$，$l_{S,v_j}$是群体$S$与群体外的元素$v_j$的最短路径的长度。该长度可以以多种方式定义，一种方法是寻找$S$中距离$v_j$最近成员元素，另一种是使用最大距离或平均距离。

最后

以上就是俭朴画板为你收集整理的中心性（centrality）单个结点中心性群体中心性的全部内容，希望文章能够帮你解决中心性（centrality）单个结点中心性群体中心性所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。