HDC
概述
Katz中心性（Katz Centrality）算法用于衡量点的影响力，其考虑因素包括点的直接连接和不同距离下的间接连接，同时为更远距离的点赋予较小的权重。
Katz中心性取值范围为0到1，分值越高，说明点在网络流动和连接性上影响力更大。
参考文献：
- L. Katz, A New Status Index Derived from Sociometric Analysis (1953)
基本概念
Katz中心性
Katz中心性是对特征向量中心性的扩展。特征向量中心性进行第k轮影响力传播时，中心向量更新为c(k) = Ac(k-1)，其中A为邻接矩阵。Katz中心性在此计算过程中引入两个新参数，得到以下更新公式（之后需要重新缩放）：
其中，
α（alpha）为衰减因子，用于控制每轮传播中的影响力衰减。在第k轮，k步外间接邻居带来的影响也会被考虑在内，其总贡献度经αk逐步衰减。为确保c(k)能够收敛，α必须小于1/λmax，其中λmax是邻接矩阵A的最大特征值。β（beta）为基准中心性常数，用于确保每个点的中心性分值均不为零，即便该点未收到任何影响。通常为β取值为1。1为n × 1的向量，所有元素均为1，其中n为图中点总数。
示例图
在一个空图中运行以下语句定义图结构并插入数据：
ALTER GRAPH CURRENT_GRAPH ADD NODE {
web ()
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
link ()-[{value float}]->()
};
INSERT (web1:web {_id: "web1"}),
(web2:web {_id: "web2"}),
(web3:web {_id: "web3"}),
(web4:web {_id: "web4"}),
(web5:web {_id: "web5"}),
(web6:web {_id: "web6"}),
(web7:web {_id: "web7"}),
(web1)-[:link {value: 2}]->(web1),
(web1)-[:link {value: 1}]->(web2),
(web2)-[:link {value: 0.8}]->(web3),
(web3)-[:link {value: 0.5}]->(web1),
(web3)-[:link {value: 1.1}]->(web2),
(web3)-[:link {value: 1.2}]->(web4),
(web3)-[:link {value: 0.5}]->(web5),
(web5)-[:link {value: 0.5}]->(web3),
(web6)-[:link {value: 2}]->(web6);
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上，并命名为 my_hdc_graph：
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static"
}
hdc.graph.create("my_hdc_graph", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static"
}).to("hdc-server-1")
参数
算法名：katz_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 |
alpha |
Float | (0, 1/λmax) | 0.25 |
是 | 衰减因子，必须小于邻接矩阵A的最大特征值（λmax） |
beta |
Float | >0 | 1 |
是 | 基准中心性常数，用于确保每个点的中心性分值均不为零 |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据katz_centrality分值对结果排序 |
文件回写
CALL algo.katz_centrality.write("my_hdc_graph", {
return_id_uuid: "id",
max_loop_num: 50,
tolerance: 0.00001,
direction: "in",
alpha: 0.4
}, {
file: {
filename: "katz_centrality"
}
})
algo(katz_centrality).params({
projection: "my_hdc_graph",
return_id_uuid: "id",
max_loop_num: 50,
tolerance: 0.00001,
direction: "in",
alpha: 0.4
}).write({
file: {
filename: "katz_centrality"
}
})
结果：
_id,katz_centrality
web3,0.458447
web7,0.127183
web1,0.517601
web5,0.310561
web6,0.211972
web2,0.517601
web4,0.310561
数据库回写
将结果中的katz_centrality值写入指定点属性。该属性类型为double。
CALL algo.katz_centrality.write("my_hdc_graph", {
edge_weight_property: "@link.value"
}, {
db: {
property: "kc"
}
})
algo(katz_centrality).params({
projection: "my_hdc_graph",
edge_weight_property: "@link.value"
}).write({
db:{
property: 'kc'
}
})
完整返回
CALL algo.katz_centrality.run("my_hdc_graph", {
return_id_uuid: "id",
max_loop_num: 100,
tolerance: 0.00001,
edge_weight_property: "value",
direction: "in",
alpha: 0.4,
beta: 1,
order: "desc"
}) YIELD r
RETURN r
exec{
algo(katz_centrality).params({
return_id_uuid: "id",
max_loop_num: 100,
tolerance: 0.00001,
edge_weight_property: "value",
direction: "in",
alpha: 0.4,
beta: 1,
order: "desc"
}) as kc
return kc
} on my_hdc_graph
结果：
| _id | katz_centrality |
|---|---|
| web1 | 0.681081665151973 |
| web2 | 0.471519549878494 |
| web6 | 0.419136320993772 |
| web3 | 0.261956715748936 |
| web4 | 0.20956622151173 |
| web5 | 0.136218518184715 |
| web7 | 0.0838273050914304 |
流式返回
CALL algo.katz_centrality.stream("my_hdc_graph", {
return_id_uuid: "id",
max_loop_num: 100,
tolerance: 0.00001,
edge_weight_property: "value",
direction: "in",
alpha: 0.4,
beta: 1,
order: "desc"
}) YIELD kc
RETURN kc
exec{
algo(katz_centrality).params({
return_id_uuid: "id",
max_loop_num: 100,
tolerance: 0.00001,
edge_weight_property: "value",
direction: "in",
alpha: 0.4,
beta: 1,
order: "desc"
}).stream() as kc
return kc
} on my_hdc_graph
结果：
| _id | katz_centrality |
|---|---|
| web1 | 0.681081665151973 |
| web2 | 0.471519549878494 |
| web6 | 0.419136320993772 |
| web3 | 0.261956715748936 |
| web4 | 0.20956622151173 |
| web5 | 0.136218518184715 |
| web7 | 0.0838273050914304 |