概述

特征向量中心性（Eigenvector Centrality）度量网络中节点的影响力或重要性。在图中，节点是互相影响的；具体地，一个节点通过入边接收来自邻居节点的影响力。因此，节点的特征向量中心性分值不仅取决于有多少条入边，还取决于入边邻居有多重要。来自高分值节点的连接比来自低分值节点的连接对节点分值的贡献更大。在疾病传播场景中，特征向量中心性分值高的节点距离传染源近的可能性更大，需要格外防范。

著名的PageRank是特征向量中心性的一个变种。

特征向量中心性的取值范围是0到1，节点的分值越大，影响力越大。

基本概念

特征向量中心性

节点的分值可通过递归的方式计算。以下图为例，邻接矩阵A反映每个节点的入边。将所有节点的分值初始化为1，并用向量s⁽⁰⁾表示。

在每轮影响力传递中，更新每个节点的分值为其入边邻居的分值和。经过一轮，s⁽¹⁾ = As⁽⁰⁾以及经过L2范数归一化处理后的结果如下所示：

经过k轮迭代后，s^(k) = As^(k-1) = A^ks⁽⁰⁾。随着k的增长，s^(k)逐渐达到稳态。在本例中，s^(k)在约20轮后不再改变。

事实上，向量s^(k)朝着矩阵A对应于绝对值最大的特征值的特征向量的方向收敛。因此，s^(k)各元素的值称为各点的特征向量中心性分值。

特征值和特征向量

给定nxn维矩阵A、常数λ以及n维非0向量x，如果满足Ax=λx，那么称λ为A的特征值（Eigenvalue），x为A对应于特征值λ的特征向量（Eigenvector）。

上面的矩阵A有4个特征值λ₁、λ₂、λ₃和λ₄，分别对应特征向量x₁、x₂、x₃和x₄。其中，x₁是对应于主特征值λ₁ 的特征向量，λ₁是主特征值因为其绝对值最大。

根据 Perron-Forbenius定理，如果矩阵 A 有特征值|λ₁|>|λ₂|≥|λ₃|≥...≥|λ_n|，当k→∞，s^(k)=A^ks⁽⁰⁾的方向朝着x₁的方向收敛，s⁽⁰⁾可以是任意非0向量。

幂迭代

为了保证精度的同时也提高计算效率，本算法采用幂迭代法计算矩阵A的主特征向量（x₁）：

• s⁽¹⁾=As⁽⁰⁾
• s⁽²⁾=As⁽¹⁾=A²s⁽⁰⁾
• ...
• s^(k)=As^(k-1)=A^ks⁽⁰⁾

算法在所有节点的变化值小于规定的收敛偏差（tolerance）时停止，若迭代轮数达到限制，算法也会结束。

特殊说明

• 本算法使用邻接矩阵加上单位矩阵后的矩阵（即A=A+I）来进行计算以保证收敛。
• 没有入边的节点的特征向量中心性分值趋近于0。
• 自环边算作一条入边，其权重值只计算一次（权重图）。

语法

• 命令：algo(eigenvector_centrality)
• 参数：

示例

示例是一个网页引用关系图，边属性@link.value的值可用作权重：

文件回写

algo(eigenvector_centrality).params({
  max_loop_num: 15,
  tolerance: 0.01,
  direction: "in"
}).write({
    file: {
      filename: 'rank'
    }
})

结果：文件rank

web7,4.63007e-06
web6,0.0198426
web5,0.255212
web3,0.459901
web4,0.255214
web2,0.573512
web1,0.573511

属性回写

algo(eigenvector_centrality).params({
  edge_weight_property: 'value'  
}).write({
    db: {
      property: 'ec'
    }
})

结果：每个节点的中心性分值回写至名为ec的点属性下

直接返回

algo(eigenvector_centrality).params({
  max_loop_num: 20,
  tolerance: 0.01,
  edge_weight_property: '@link.value',
  direction: "in",
  order: 'desc'
}) as ec 
return ec

结果：ec

流式返回

示例：计算所有点的特征向量中心性，统计分值大于0.4和小于等于0.4的节点数量

algo(eigenvector_centrality).params({
  edge_weight_property: '@link.value',
  direction: "in"
}).stream() as ec
with case
when ec.rank > 0.4 then 'attention'
when ec.rank <= 0.4 then 'normal'
END as r
group by r
return table(r, count(r))

结果：table(r, count(r))