概述
特征向量中心性（Eigenvector Centrality）度量网络中节点的影响力或重要性。在图中，节点是互相影响的；具体地，一个节点通过入边接收来自邻居节点的影响力。因此，节点的特征向量中心性分值不仅取决于有多少条入边，还取决于入边邻居有多重要。来自高分值节点的连接比来自低分值节点的连接对节点分值的贡献更大。在疾病传播场景中，特征向量中心性分值高的节点距离传染源近的可能性更大，需要格外防范。
著名的PageRank是特征向量中心性的一个变种。
特征向量中心性的取值范围是0到1，节点的分值越大，影响力越大。
基本概念
特征向量中心性
节点的分值可通过递归的方式计算。以下图为例，邻接矩阵A反映每个节点的入边。将所有节点的分值初始化为1，并用向量s(0)表示。
在每轮影响力传递中，更新每个节点的分值为其入边邻居的分值和。经过一轮，s(1) = As(0)以及经过L2范数归一化处理后的结果如下所示：
经过k轮迭代后，s(k) = As(k-1) = Aks(0)。随着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个特征值λ1、λ2、λ3和λ4，分别对应特征向量x1、x2、x3和x4。其中，x1是对应于主特征值λ1 的特征向量，λ1是主特征值因为其绝对值最大。
根据 Perron-Forbenius定理，如果矩阵 A 有特征值|λ1|>|λ2|≥|λ3|≥...≥|λn|，当k→∞，s(k)=Aks(0)的方向朝着x1的方向收敛，s(0)可以是任意非0向量。
幂迭代
为了保证精度的同时也提高计算效率，本算法采用幂迭代法计算矩阵A的主特征向量（x1）：
- s(1)=As(0)
- s(2)=As(1)=A2s(0)
- ...
- s(k)=As(k-1)=Aks(0)
算法在所有节点的变化值小于规定的收敛偏差（tolerance）时停止，若迭代轮数达到限制，算法也会结束。
特殊说明
- 本算法使用邻接矩阵加上单位矩阵后的矩阵（即A=A+I）来进行计算以保证收敛。
- 没有入边的节点的特征向量中心性分值趋近于0。
- 自环边算作一条入边，其权重值只计算一次（权重图）。
示例图集
创建示例图集：
// 在空图集中逐行运行以下语句
create().node_schema("web").edge_schema("link")
create().edge_property(@link, "value", float)
insert().into(@web).nodes([{_id:"web1"}, {_id:"web2"}, {_id:"web3"}, {_id:"web4"}, {_id:"web5"}, {_id:"web6"}, {_id:"web7"}])
insert().into(@link).edges([{_from:"web1", _to:"web1",value:2}, {_from:"web1", _to:"web2",value:1}, {_from:"web2", _to:"web3",value:0.8}, {_from:"web3", _to:"web1",value:0.5}, {_from:"web3", _to:"web2",value:1.1}, {_from:"web3", _to:"web4",value:1.2}, {_from:"web3", _to:"web5",value:0.5}, {_from:"web5", _to:"web3",value:0.5}, {_from:"web6", _to:"web6",value:2}])
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_eigenvector：
CALL hdc.graph.create("hdc-server-1", "hdc_eigenvector", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_eigenvector", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名：eigenvector_centrality
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
max_loop_num |
Integer | ≥1 | 20 |
是 | 最大迭代轮数。算法将在完成所有轮次后停止 |
tolerance |
Float | (0,1) | 0.001 |
是 | 某轮迭代后，若所有点的分值变化小于指定tolerance时，表明结果已稳定，算法会停止 |
edge_weight_property |
"<@schema.?><property>" |
/ | / | 是 | 邻接矩阵A中用作权重的数值类型边属性；不包含指定属性的边将被忽略 |
direction |
String | in, out |
/ | 是 | 使用点的入边（in）或出边（out）构建邻接矩阵A |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据eigenvector_centrality分值对结果排序 |
文件回写
CALL algo.eigenvector_centrality.write("hdc_eigenvector", {
params: {
return_id_uuid: "id",
max_loop_num: 15,
tolerance: 0.01,
direction: "in"
},
return_params: {
file: {
filename: "eigenvector_centrality"
}
}
})
algo(eigenvector_centrality).params({
projection: "hdc_eigenvector",
return_id_uuid: "id",
max_loop_num: 15,
tolerance: 0.01,
direction: "in"
}).write({
file: {
filename: "eigenvector_centrality"
}
})
结果：
_id,eigenvector_centrality
web6,0.0183902
web2,0.573482
web4,0.255287
web3,0.459952
web7,6.35024e-06
web1,0.57348
web5,0.255292
数据库回写
将结果中的eigenvector_centrality值写入指定点属性。该属性类型为float。
CALL algo.eigenvector_centrality.write("hdc_eigenvector", {
params: {
edge_weight_property: "@link.value"
},
return_params: {
db: {
property: "ec"
}
}
})
algo(eigenvector_centrality).params({
projection: "hdc_eigenvector",
edge_weight_property: "@link.value"
}).write({
db:{
property: 'ec'
}
})
完整返回
CALL algo.eigenvector_centrality("hdc_eigenvector", {
params: {
return_id_uuid: "id",
max_loop_num: 20,
tolerance: 0.01,
edge_weight_property: "value",
direction: "in",
order: 'desc'
},
return_params: {}
}) YIELD ec
RETURN ec
exec{
algo(eigenvector_centrality).params({
return_id_uuid: "id",
max_loop_num: 20,
tolerance: 0.01,
edge_weight_property: "value",
direction: "in",
order: 'desc'
}) as ec
return ec
} on hdc_eigenvector
结果：
| _id | eigenvector_centrality |
|---|---|
| web1 | 0.777769 |
| web2 | 0.463170 |
| web6 | 0.365171 |
| web3 | 0.185178 |
| web4 | 0.104874 |
| web5 | 0.043697 |
| web7 | 0 |
流式返回
CALL algo.eigenvector_centrality("hdc_eigenvector", {
params: {
return_id_uuid: "id",
edge_weight_property: "@link.value",
direction: "in"
},
return_params: {
stream: {}
}
}) YIELD ec
RETURN CASE
WHEN ec.eigenvector_centrality > 0.4 THEN "important"
ELSE "normal"
END as r, count(r) GROUP BY r
exec{
algo(eigenvector_centrality).params({
return_id_uuid: "id",
edge_weight_property: "@link.value",
direction: "in"
}).stream() as ec
with case
when ec.eigenvector_centrality > 0.4 then "important"
else "normal"
end as r
group by r
return r, count(r)
} on hdc_eigenvector
结果：
| r | count(r) |
|---|---|
| important | 2 |
| normal | 5 |