特征向量中心性

朱雀 2022-09-07 12:23 212阅读 0赞

特征向量中心性的基本思想是，一个节点的中心性是相邻节点中心性的函数。**也就是说，与你连接的人越重要，你也就越重要。**

特征向量中心性和点度中心性不同，一个点度中心性高即拥有很多连接的节点，但特征向量中心性不一定高，因为所有的连接者有可能特征向量中心性很低。同理，特征向量中心性高并不意味着它的点度中心性高，它拥有很少但很重要的连接者也可以拥有高特征向量中心性。

考虑下面的图，以及相应的5x5的邻接矩阵(Adjacency Matrix)，A。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70]  
 A = \[ 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 \] A=\\left\[\\begin\{array\}\{ccccc\} 0 & 1 & 1 & 1 & 0 \\\\ 1 & 0 & 1 & 0 & 0 \\\\ 1 & 1 & 0 & 1 & 0 \\\\ 1 & 0 & 1 & 0 & 1 \\\\ 0 & 0 & 0 & 1 & 0 \\end\{array\}\\right\] A=⎣⎢⎢⎢⎢⎡0111010100110101010100010⎦⎥⎥⎥⎥⎤  
现在考虑`x`，一个5x1的向量，向量的值对应图中的每个点。在这种情况下，我们计算的是每个点的点度中心性（degree centrality），即以点的连接数来衡量中心性的高低。

矩阵A乘以这个向量的结果是一个5x1的向量：  
 A × x = ( 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 ) ( 3 2 3 3 1 ) = ( 0 × 3 + 1 × 2 + 1 × 3 + 1 × 3 + 0 × 1 1 × 3 + 0 × 2 + 1 × 3 + 0 × 3 + 0 × 1 1 × 3 + 1 × 2 + 0 × 3 + 1 × 3 + 0 × 1 1 × 3 + 0 × 2 + 1 × 3 + 0 × 3 + 1 × 1 0 × 3 + 0 × 2 + 1 × 3 + 0 × 3 + 0 × 1 ) = \[ 8 6 8 7 3 \] \\mathbf\{A\} \\times \\mathbf\{x\}=\\left(\\begin\{array\}\{cccc\} 0 & 1 & 1 & 1 & 0 \\\\ 1 & 0&1 & 0 & 0 \\\\ 1 & 1 & 0&1 & 0 \\\\ 1 & 0 & 1 & 0&1 \\\\ 0 & 0 & 0 & 1&0 \\end\{array\}\\right)\\left(\\begin\{array\}\{l\} 3 \\\\ 2 \\\\ 3 \\\\ 3 \\\\ 1 \\end\{array\}\\right)=\\left(\\begin\{array\}\{l\} 0 \\times 3+1 \\times 2+1 \\times 3+1 \\times 3+0 \\times 1 \\\\ 1 \\times 3+0 \\times 2+1 \\times 3+0 \\times 3+0 \\times 1 \\\\ 1 \\times 3+1 \\times 2+0 \\times 3+1 \\times 3+0 \\times 1 \\\\ 1 \\times 3+0 \\times 2+1 \\times 3+0 \\times 3+1 \\times 1 \\\\ 0 \\times 3+0 \\times 2+1 \\times 3+0 \\times 3+0 \\times 1 \\end\{array\}\\right)=\\left\[\\begin\{array\}\{c\} 8 \\\\ 6 \\\\ 8 \\\\ 7 \\\\ 3 \\end\{array\}\\right\] A×x=⎝⎜⎜⎜⎜⎛0111010100110101010100010⎠⎟⎟⎟⎟⎞⎝⎜⎜⎜⎜⎛32331⎠⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎛0×3\+1×2\+1×3\+1×3\+0×11×3\+0×2\+1×3\+0×3\+0×11×3\+1×2\+0×3\+1×3\+0×11×3\+0×2\+1×3\+0×3\+1×10×3\+0×2\+1×3\+0×3\+0×1⎠⎟⎟⎟⎟⎞=⎣⎢⎢⎢⎢⎡86873⎦⎥⎥⎥⎥⎤  
结果向量的第一个元素是用矩阵A的第一行去“获取”每一个与第一个点有连接的点的值（连接数，点度中心性），也就是第2个、第3个和第4个点的值，然后将它们加起来。

**换句话说，邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。你的朋友的朋友越多，你的特征向量中心性就越高。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 1]  
我们继续用矩阵A乘以结果向量。如何理解呢？

**实际上，我们允许这一中心性数值再次沿着图的边界“扩散”。我们会观察到两个方向上的扩散（点既给予也收获相邻节点）。我们猜测，这一过程最后会达到一个平衡，特定点收获的数量会和它给予相邻节点的数量取得平衡。既然我们仅仅是累加，数值会越来越大，但我们最终会到达一个点，各个节点在整体中的比例会保持稳定。**

A × X = \[ 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 \] \[ x 1 x 2 x 3 x 4 x 5 \] = \[ 0 ⋅ x 1 + 1 ⋅ x 2 + 1 ⋅ x 3 + 1 ⋅ x 4 + 0 ⋅ x 5 1 ⋅ x 1 + 0 ⋅ x 2 + 1 ⋅ x 3 + 0 ⋅ x 4 + 0 ⋅ x 5 1 ⋅ x 1 + 1 ⋅ x 2 + 0 ⋅ x 3 + 1 ⋅ x 4 + 0 ⋅ x 5 1 ⋅ x 1 + 0 ⋅ x 2 + 1 ⋅ x 3 + 0 ⋅ x 4 + 1 ⋅ x 5 0 ⋅ x 1 + 0 ⋅ x 2 + 0 ⋅ x 3 + 1 ⋅ x 4 + 0 ⋅ x 5 \] A \\times X=\\left\[\\begin\{array\}\{ccccc\} 0 & 1 & 1 & 1 & 0 \\\\ 1 & 0 & 1 & 0 & 0 \\\\ 1 & 1 & 0 & 1 & 0 \\\\ 1 & 0 & 1 & 0 & 1 \\\\ 0 & 0 & 0 & 1 & 0 \\end\{array\}\\right\]\\left\[\\begin\{array\}\{l\} x\_\{1\} \\\\ x\_\{2\} \\\\ x\_\{3\} \\\\ x\_\{4\} \\\\ x\_\{5\} \\end\{array\}\\right\]=\\left\[\\begin\{array\}\{l\} 0 \\cdot x\_\{1\}+1 \\cdot x\_\{2\}+1 \\cdot x\_\{3\}+1 \\cdot x\_\{4\}+0 \\cdot x\_\{5\} \\\\ 1 \\cdot x\_\{1\}+0 \\cdot x\_\{2\}+1 \\cdot x\_\{3\}+0 \\cdot x\_\{4\}+0 \\cdot x\_\{5\} \\\\ 1 \\cdot x\_\{1\}+1 \\cdot x\_\{2\}+0 \\cdot x\_\{3\}+1 \\cdot x\_\{4\}+0 \\cdot x\_\{5\} \\\\ 1 \\cdot x\_\{1\}+0 \\cdot x\_\{2\}+1 \\cdot x\_\{3\}+0 \\cdot x\_\{4\}+1 \\cdot x\_\{5\} \\\\ 0 \\cdot x\_\{1\}+0 \\cdot x\_\{2\}+0 \\cdot x\_\{3\}+1 \\cdot x\_\{4\}+0 \\cdot x\_\{5\} \\end\{array\}\\right\] A×X=⎣⎢⎢⎢⎢⎡0111010100110101010100010⎦⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎡x1x2x3x4x5⎦⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎡0⋅x1\+1⋅x2\+1⋅x3\+1⋅x4\+0⋅x51⋅x1\+0⋅x2\+1⋅x3\+0⋅x4\+0⋅x51⋅x1\+1⋅x2\+0⋅x3\+1⋅x4\+0⋅x51⋅x1\+0⋅x2\+1⋅x3\+0⋅x4\+1⋅x50⋅x1\+0⋅x2\+0⋅x3\+1⋅x4\+0⋅x5⎦⎥⎥⎥⎥⎤

我们认为，图中的点存在一个数值集合，对于它，用矩阵A去乘不会改变向量各个数值的相对大小。也就是说，它的数值会变大，但乘以的是同一个因子。用数学符号表示就是：  
 M x = λ x M × \[ x 1 x 2 x 3 . . . x n \] = \[ λ x 1 λ x 2 λ x 3 . . . λ x n \] Mx = \\lambda x \\\\ M \\times \\left\[\\begin\{array\}\{ccccc\} x\_1 \\\\ x\_2 \\\\ x\_3 \\\\ ... \\\\ x\_n \\end\{array\}\\right\]=\\left\[\\begin\{array\}\{ccccc\} \\lambda x\_1 \\\\ \\lambda x\_2 \\\\ \\lambda x\_3 \\\\ ... \\\\ \\lambda x\_n \\end\{array\}\\right\] Mx=λxM×⎣⎢⎢⎢⎢⎡x1x2x3...xn⎦⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎡λx1λx2λx3...λxn⎦⎥⎥⎥⎥⎤

满足这一属性的向量就是矩阵`M`的特征向量。特征向量的元素就是图中每个点的特征向量中心性。

记 x i x\_i xi是 v i v\_i vi的特征向量中心性度量，则：  
 E C ( i ) = x i = c ∑ j = i n a i j x j EC(i) = x\_i=c\\sum\_\{j=i\}^\{n\}a\_\{ij\}x\_j EC(i)=xi=cj=i∑naijxj  
其中`c`表示一个比例常数，记 x = \[ x 1 , x 2 , . . . , x n \] T x=\[x\_1,x\_2,...,x\_n\]^T x=\[x1,x2,...,xn\]T，经过多次迭代达到稳态时，可写成如下形式：  
 x = c A x x = cAx x=cAx  
其中`c`为一个比例常数， a i j a\_\{ij\} aij当且仅当i与j相连，否则为0。  
这里的`x`是矩阵`A`的特征值 c − 1 c^\{-1\} c−1对应的特征向量，也可以表示成如下形式：  
 A x = λ x Ax=\\lambda x Ax=λx  
特征向量中心性的计算需要读者具备矩阵乘法和特征向量的知识，但不影响这里读者对特征向量中心性思想的理解，不再赘述。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70]: /images/20220829/136b66b3fffb43deb327bd053962dc87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 1]: /images/20220829/d66bdcc2edc24337bb2257e055615dd4.png