✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

特征向量中心性（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) 各元素的值称为各点的特征向量中心性分值。

特征值和特征向量

给定 n x n 维矩阵 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
}).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',
  order: 'desc'
}) as ec 
return ec

结果：ec

流式返回

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

algo(eigenvector_centrality).params({
  edge_weight_property: '@link.value'
}).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))