中心性（centrality）

参考资料

1. 《社会媒体挖掘》

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

单个结点中心性

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

度中心性

针对无向图，结点 v i v_i vi​的度中心性为 C d ( v i ) = d i C_{d}\left ( v_{i}\right )=d_{i} Cd​(vi​)=di​，即为结点的度；
针对有向图，中心性既可以是入度（视为声望） C d ( v i ) = d i i n C_{d}\left ( v_{i}\right )=d_{i}^{in} Cd​(vi​)=diin​，也可以是出度（视为合群性） C d ( v i ) = d i o u t C_{d}\left ( v_{i}\right )=d_{i}^{out} Cd​(vi​)=diout​，还可以是二者的和 C d ( v i ) = d i i n + d i o u t C_{d}\left ( v_{i}\right )=d_{i}^{in}+d_{i}^{out} Cd​(vi​)=diin​+diout​。

特征向量中心性

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

c e ( v i ) = 1 λ ∑ j = 1 n A j , i c e ( v j ) c_{e}\left ( v_{i}\right )=\frac{1}{\lambda }\sum_{j=1}^{n}A_{j,i}c_{e}\left ( v_{j}\right ) ce​(vi​)=λ1​∑j=1n​Aj,i​ce​(vj​)

其中， λ \lambda λ是个常量， c e ( v i ) c_{e}\left ( v_{i}\right ) ce​(vi​)是结点 v i v_{i} vi​的中心性。
将上式写成矩阵形式，特征向量中心性实际上是对网络的邻接矩阵 A A A进行特征分解，选择最大特征值对应的特征向量作为各结点的中心性。

λ C e = A T C e \lambda C_{e}=A^{T}C_{e} λCe​=ATCe​

其中， C e C_{e} Ce​是邻接矩阵 A T A^{T} AT的特征向量， λ \lambda λ是对应的特征值。
但是中心性要求大于0，所以引入Perron-Frobenius Theorem：
假设 A ∈ R n × n A \in \textrm{R} ^{n\times n} A∈Rn×n是[强]连通图的邻接矩阵，或者 A : A i , j > 0 A:A_{i,j}> 0 A:Ai,j​>0（即一个正的 n × n n\times n n×n的矩阵），存在一个正实数（Perron-Frobenius特征值） λ m a x \lambda_{max} λmax​，满足 λ m a x \lambda _{max} λmax​是矩阵 A A A的特征值，并且 A A A的其余特征值均严格小于 λ m a x \lambda _{max} λmax​。 λ m a x \lambda _{max} λmax​所对应的特征向量为 v = ( v 1 , v 2 , ⋅ ⋅ ⋅ , v n ) \mathbf{v}=\left ( v_{1},v_{2},\cdot \cdot \cdot ,v_{n}\right ) v=(v1​,v2​,⋅⋅⋅,vn​)，满足 ∀ v i > 0 \forall v_{i}> 0 ∀vi​>0。

Katz中心性

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

c K a t z ( v i ) = α ∑ j = 1 n A j , i c K a t z ( v j ) + β c_{Katz}\left ( v_{i}\right )=\alpha \sum_{j=1}^{n}A_{j,i}c_{Katz}\left ( v_{j}\right )+\beta cKatz​(vi​)=α∑j=1n​Aj,i​cKatz​(vj​)+β

写为向量形式：

C K a t z = α A T C K a t z + β 1 C_{Katz}=\alpha A^{T}C_{Katz}+\beta \textbf{1} CKatz​=αATCKatz​+β1

移项得：

C K a t z = β ( I − α A T ) − 1 ⋅ 1 C_{Katz}=\beta \left ( I-\alpha A^{T}\right )^{-1}\cdot \textbf{1} CKatz​=β(I−αAT)−1⋅1

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

PageRank

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

C p ( v i ) = α ∑ j = 1 n A j , i C p ( v j ) d j o u t + β 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 Cp​(vi​)=α∑j=1n​Aj,i​djout​Cp​(vj​)​+β

表示为矩阵形式：

C p = α A T D − 1 C p + β 1 C_{p}=\alpha A^{T}D^{-1}C_{p}+\beta \textbf{1} Cp​=αATD−1Cp​+β1

改写为：

C p = β ( I − α A T D − 1 ) − 1 ⋅ 1 C_{p}=\beta \left ( I-\alpha A^{T}D^{-1}\right )^{-1}\cdot \textbf{1} Cp​=β(I−αATD−1)−1⋅1

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

中间中心性

中间中心性计算其他结点间通过结点 v i v_{i} vi​的最短路径数。

C b ( v i ) = ∑ s ≠ t ≠ v i σ s t ( v i ) σ s t C_{b}\left ( v_{i}\right )=\sum_{s\neq t\neq v_{i}}^{}\frac{\sigma _{st}\left ( v_{i}\right )}{\sigma _{st}} Cb​(vi​)=∑s​=t​=vi​​σst​σst​(vi​)​

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

C b ( v i ) = ∑ s ≠ t ≠ v i 1 = 2 ( n − 1 2 ) C_{b}\left ( v_{i}\right )=\sum_{s\neq t\neq v_{i}}^{}1=2 \binom{n-1}{2} Cb​(vi​)=∑s​=t​=vi​​1=2(2n−1​)

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

C b n o r m ( v i ) = C b ( v i ) 2 ( n − 1 2 ) C_{b}^{norm}\left ( v_{i}\right )=\frac{C_{b}\left ( v_{i}\right )}{2\binom{n-1}{2}} Cbnorm​(vi​)=2(2n−1​)Cb​(vi​)​

对无向图，有 ∑ s ≠ t ≠ v i σ s t ( v i ) σ s t = 2 ∑ s ≠ t ≠ v i , s < t σ s t ( v i ) σ s t \sum_{s\neq t\neq v_{i}}^{}\frac{\sigma _{st}\left ( v_{i}\right )}{\sigma _{st}}=2\sum_{s\neq t\neq v_{i},s< t}^{}\frac{\sigma _{st}\left ( v_{i}\right )}{\sigma _{st}} ∑s​=t​=vi​​σst​σst​(vi​)​=2∑s​=t​=vi​,s<t​σst​σst​(vi​)​，所以中心性乘以2。

接近中心性

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

C c ( v i ) = 1 l ˉ v i C_{c}\left ( v_{i}\right )=\frac{1}{\bar{l}_{v_{i}}} Cc​(vi​)=lˉvi​​1​

其中， l ˉ v i = 1 n − 1 ∑ v j ≠ v i l i , j \bar{l}_{v_{i}}=\frac{1}{n-1}\sum_{v_{j}\neq v_{i}}^{}l_{i,j} lˉvi​​=n−11​∑vj​​=vi​​li,j​是结点 v i v_{i} vi​与其他结点之间的平均最短路径。最短路径越小，那么结点的中心性会越高。

群体中心性

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

群体度中心性

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

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

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

群体中间中心性

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

C b g r o u p ( S ) = ∑ s ≠ t , s ∉ S , t ∉ S σ s t ( S ) σ s t C_{b}^{group}\left ( S\right )=\sum_{s\neq t,s\notin S,t\notin S}^{}\frac{\sigma _{st}\left ( S\right )}{\sigma _{st}} Cbgroup​(S)=∑s​=t,s∈/​S,t∈/​S​σst​σst​(S)​

群体接近中心性

群体接近中心性定义为：

C c g r o u p ( S ) = 1 l ˉ S g r o u p C_{c}^{group}\left ( S\right )=\frac{1}{\bar{l}_{S}^{group}} Ccgroup​(S)=lˉSgroup​1​

其中， l ˉ S g r o u p = 1 ∣ V − S ∣ ∑ v i ∉ S l S , v j \bar{l}_{S}^{group}=\frac{1}{\left | V-S\right |}\sum_{v_{i}\notin S}^{}l_{S,v_{j}} lˉSgroup​=∣V−S∣1​∑vi​∈/​S​lS,vj​​， l S , v j l_{S,v_{j}} lS,vj​​是群体 S S S与群体外的元素 v j v_j vj​的最短路径的长度。该长度可以以多种方式定义，一种方法是寻找 S S S中距离 v j v_{j} vj​最近成员元素，另一种是使用最大距离或平均距离。