HDC
概述
一个点的图中心性（Graph Centrality）是由该点到它可连通的其它各点的最短距离的最大值来衡量的。我们可综合考量这个指标与其它指标（如接近中心性、图直径等），判定一个点是否真正位于图的最中心。
图中心性的取值范围是0到1，节点的分值越大，越靠近中心。
基本概念
最短距离
两个点之间的最短距离是指它们之间最短路径的边数。具体可参看接近中心性。
图中心性
在本算法中，节点的图中心性分值等于该点与其他能够相连的各节点的最短距离最大值的倒数。计算公式为：
其中，x为待计算的目标节点，y为通过边与x相连的任意一个节点（不包含x），d(x,y)为x到y的最短距离。
上图中，各点旁的绿色和红色文字分别是该点到绿、红两个节点的最短距离，绿、红两个节点的图中心性分别为1/4 = 0.25和1/3 = 0.3333。
考虑这两个点的接近中心性，绿色节点的分值为8/(1+1+1+1+2+3+4+3) = 0.5，红色节点的分值为8/(3+3+3+2+1+1+2+1) = 0.5。两个节点的接近中心性分值相同时，图中心性可作为辅助依据判断哪个节点更靠近中心。
图中心性算法会消耗很多计算资源。在一个有V个节点的图中，建议当V>10000时通过采样进行近似计算，推荐的采样个数是节点数以10为底的对数（
log(V)）。
每次执行算法时，只进行一次采样，每个节点的中心性分值是基于该节点到所有样本节点的最短距离计算的。
特殊说明
- 孤点的图中心性分值为0。
- 图中心性算法忽略边的方向，按照无向边进行计算。
示例图集
创建示例图集：
// 在空图集中逐行运行以下语句
create().node_schema("user").edge_schema("vote")
create().edge_property(@vote, "weight", uint32)
insert().into(@user).nodes([{_id:"A"},{_id:"B"},{_id:"C"},{_id:"D"},{_id:"E"},{_id:"F"},{_id:"G"},{_id:"H"},{_id:"I"},{_id:"J"}])
insert().into(@vote).edges([{_from:"A", _to:"B", weight:1}, {_from:"A", _to:"C", weight:2}, {_from:"A", _to:"D", weight:3}, {_from:"E", _to:"A", weight:2}, {_from:"E", _to:"F", weight:1}, {_from:"F", _to:"G", weight:4}, {_from:"F", _to:"I", weight:1}, {_from:"G", _to:"H", weight:2}, {_from:"H", _to:"I", weight:1}])
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_gc：
CALL hdc.graph.create("hdc-server-1", "hdc_gc", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_gc", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名：graph_centrality
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
ids |
[]_id |
/ | / | 是 | 通过_id指定参与计算的点；若未设置则计算所有点 |
uuids |
[]_uuid |
/ | / | 是 | 通过_uuid指定参与计算的点；若未设置则计算所有点 |
direction |
String | in, out |
/ | 是 | 指定最短路径中所有边的方向，in表示仅包含入边，out表示仅包含出边 |
edge_schema_property |
[]"<@schema.?><property>" |
/ | / | 是 | 作为权重的数值类型边属性，权重值为所有指定属性值的总和；不包含指定属性的边将被忽略 |
impl_type |
String | dijkstra, delta_stepping, spfa, beta |
beta |
是 | 指定由算法Dijkstra、 Delta-Stepping、SPFA或嬴图默认最短路径算法beta计算的加权最短路径。仅当使用edge_schema_property时生效 |
sample_size |
Integer | -1, -2, [1, |V|] |
-2 |
是 | 指定采样策略；设置为-1时，采样log(|V|)个点；设置为[1, |V|]区间内的一个数字，采样指定数量的点（|V|是图中总点数）；设置为-2时，不进行采样。该选项仅当所有点参与计算时生效 |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据graph_centrality分值对结果排序 |
文件回写
CALL algo.graph_centrality.write("hdc_gc", {
params: {
return_id_uuid: "id"
},
return_params: {
file: {
filename: "graph_centrality"
}
}
})
algo(graph_centrality).params({
projection: "hdc_gc",
return_id_uuid: "id"
}).write({
file: {
filename: "graph_centrality"
}
})
结果：
_id,graph_centrality
J,0
D,0.2
F,0.333333
H,0.2
B,0.2
A,0.25
E,0.333333
C,0.2
I,0.25
G,0.25
数据库回写
将结果中的graph_centrality值写入指定点属性。该属性类型为float。
CALL algo.graph_centrality.write("hdc_gc", {
params: {},
return_params: {
db: {
property: 'gc'
}
}
})
algo(graph_centrality).params({
projection: "hdc_gc"
}).write({
db:{
property: 'gc'
}
})
完整返回
CALL algo.graph_centrality("hdc_gc", {
params: {
return_id_uuid: "id",
ids: ["A", "B"],
edge_schema_property: "weight"
},
return_params: {}
}) YIELD gc
RETURN gc
exec{
algo(graph_centrality).params({
return_id_uuid: "id",
ids: ["A", "B"],
edge_schema_property: "weight"
}) as gc
return gc
} on hdc_gc
结果：
| _id | graph_centrality |
|---|---|
| A | 0.142857 |
| B | 0.125 |
流式返回
CALL algo.graph_centrality("hdc_gc", {
params: {
return_id_uuid: "id"
},
return_params: {
stream: {}
}
}) YIELD gc
FILTER gc.graph_centrality > 0.25
RETURN gc
exec{
algo(graph_centrality).params({
return_id_uuid: "id"
}).stream() as gc
where gc.graph_centrality > 0.25
return gc
} on hdc_gc
结果：
| _id | graph_centrality |
|---|---|
| E | 0.333333 |
| F | 0.333333 |