想建个图片网站,论坛建设免费,网站app开发计划书,机械类毕业设计代做网站推荐参考资料
《社会媒体挖掘》
中心性#xff08;centrality#xff09;用来度量结点在网络中的重要性。对于单个结点或由多个结点组成的群体都可以定义中心性。
单个结点中心性
单个结点中心性主要分为度中心性、特征向量的中心性、Katz中心性、PageRank、中间中心性、接近…参考资料
《社会媒体挖掘》
中心性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)diindiout。
特征向量中心性
特征向量中心性是想结合结点邻居的中心性作为该结点的中心性 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_{j1}^{n}A_{j,i}c_{e}\left ( v_{j}\right ) ce(vi)λ1∑j1nAj,ice(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} λCeATCe
其中 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,j0即一个正的 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 ∀vi0。
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_{j1}^{n}A_{j,i}c_{Katz}\left ( v_{j}\right )\beta cKatz(vi)α∑j1nAj,icKatz(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_{j1}^{n}A_{j,i}\frac{C_{p}\left ( v_{j}\right )}{d_{j}^{out}}\beta Cp(vi)α∑j1nAj,idjoutCp(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)∑stviσ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}}^{}12 \binom{n-1}{2} Cb(vi)∑stvi12(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}} ∑stviσstσst(vi)2∑stvi,stσ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ˉvi1
其中 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ˉvin−11∑vjvili,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)∑st,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ˉSgroup1
其中 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∈/SlS,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最近成员元素另一种是使用最大距离或平均距离。
