HDC 分布式
概述
度中心性（Degree Centrality）算法用于衡量网络中节点的重要性，它计算与每个节点相连的入边和/或出边的数量，或边上的权重和。节点度是面向节点一层邻域的计算，是一种最简单、高效的图算法，在科学计算、特征提取、超级节点识别等领域扮演着至关重要的角色。
基本概念
入度和出度
节点的入边数量称为节点的入度（In-degree），出边数量则称为出度（Out-degree），如果忽略边的方向计算所有边的数量，就得到节点的度。
上图中红色节点的入度为4，出度为3，度为7。需要注意的是，有向自环边被视为一条出边和一条入边。
加权度
在很多应用中，图中的边会与一个数字相关联，称为权重（Weight）。在加权图中，一个节点的加权度（Weighted Degree）是指其所有邻边的权重和。不指定边权重时，节点度也可以理解为所有边的权重均为1时的度。
在这个加权图中，红色节点的加权入度为0.5 + 0.3 + 2 + 1 = 3.8，加权出度为1 + 0.2 + 2 = 3.2，加权度为3.2 + 3.8 = 7。
特殊说明
- 孤点的节点度完全取决于其自环边，没有自环边的孤点的度为0。
- 每条自环边为节点贡献的度数2，有向自环边被视为一条入边和一条出边。
示例图
在一个空图中运行以下语句定义图结构并插入数据：
ALTER GRAPH CURRENT_GRAPH ADD NODE {
user ()
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
follow ()-[{score float}]->()
};
INSERT (Mike:user {_id: "Mike"}),
(Cathy:user {_id: "Cathy"}),
(Anna:user {_id: "Anna"}),
(Joe:user {_id: "Joe"}),
(Sam:user {_id: "Sam"}),
(Bob:user {_id: "Bob"}),
(Bill:user {_id: "Bill"}),
(Tim:user {_id: "Tim"}),
(Mike)-[:follow {score: 1.9}]->(Cathy),
(Cathy)-[:follow {score: 1.8}]->(Mike),
(Mike)-[:follow {score: 1.2}]->(Anna),
(Cathy)-[:follow {score: 2.6}]->(Anna),
(Cathy)-[:follow {score: 0.2}]->(Joe),
(Joe)-[:follow {score: 4.2}]->(Anna),
(Bob)-[:follow {score: 1.7}]->(Joe),
(Sam)-[:follow {score: 3.5}]->(Bob),
(Sam)-[:follow {score: 0.8}]->(Anna),
(Bill)-[:follow {score: 2.3}]->(Anna);
create().node_schema("user").edge_schema("follow");
create().edge_property(@follow, "score", float);
insert().into(@user).nodes([{_id:"Mike"},{_id:"Cathy"},{_id:"Anna"},{_id:"Joe"},{_id:"Sam"},{_id:"Bob"},{_id:"Bill"},{_id:"Tim"}]);
insert().into(@follow).edges([{_from:"Mike", _to:"Cathy", score:1.9}, {_from:"Cathy", _to:"Mike", score:1.8}, {_from:"Mike", _to:"Anna", score:1.2},{_from:"Cathy", _to:"Anna", score:2.6},{_from:"Cathy", _to:"Joe", score:0.2},{_from:"Joe", _to:"Anna", score:4.2},{_from:"Bob", _to:"Joe", score:1.7},{_from:"Sam", _to:"Bob", score:3.5},{_from:"Sam", _to:"Anna", score:0.8},{_from:"Bill", _to:"Anna", score:2.3}]);
在HDC图上运行算法
创建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")
参数
算法名：degree
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
ids |
[]_id |
/ | / | 是 | 通过_id指定参与计算的点；若未设置则计算所有点 |
uuids |
[]_uuid |
/ | / | 是 | 通过_uuid指定参与计算的点；若未设置则计算所有点 |
edge_schema_property |
[]"<@schema.?><property>" |
/ | / | 是 | 参与加权度计算的数值类型边属性，权重值为所有指定属性值的总和；不包含指定属性的边将被忽略 |
direction |
String | in, out |
/ | 是 | 指定in计算入度，out计算出度；若未设置则计算总度数 |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据degree_centrality分值对结果排序 |
文件回写
CALL algo.degree.write("my_hdc_graph", {
return_id_uuid: "id",
order: "desc"
}, {
file: {
filename: "degree"
}
})
algo(degree).params({
projection: "my_hdc_graph",
return_id_uuid: "id",
order: "desc"
}).write({
file: {
filename: "degree"
}
})
结果：
_id,degree_centrality
Anna,5
Cathy,4
Joe,3
Mike,3
Bob,2
Sam,2
Bill,1
Tim,0
数据库回写
将结果中的degree_centrality值写入指定点属性。该属性类型为double。
CALL algo.degree.write("my_hdc_graph", {
edge_schema_property: 'score'
}, {
db: {
property: "degree"
}
})
algo(degree).params({
projection: "my_hdc_graph",
edge_schema_property: 'score'
}).write({
db:{
property: 'degree'
}
})
完整返回
CALL algo.degree.run("my_hdc_graph", {
edge_schema_property: 'score',
return_id_uuid: "id",
order: 'desc'
}) YIELD r
RETURN r
exec{
algo(degree).params({
edge_schema_property: 'score',
return_id_uuid: "id",
order: 'desc'
}) as r
return r
} on my_hdc_graph
结果：
| _id | degree_centrality |
|---|---|
| Anna | 11.1 |
| Cathy | 6.5 |
| Joe | 6.1 |
| Bob | 5.2 |
| Mike | 4.9 |
| Sam | 4.3 |
| Bill | 2.3 |
| Tim | 0 |
流式返回
查找出度最高的点的邻居：
CALL algo.degree.stream("my_hdc_graph", {
direction: "out",
order: "desc",
limit: 1
}) YIELD outTop1
MATCH (src WHERE src._uuid = outTop1._uuid)-(neigh)
RETURN DISTINCT neigh._id
exec{
algo(degree).params({
direction: "out",
order: "desc",
limit: 1
}).stream() as outTop1
khop().src({_uuid == outTop1._uuid}).depth(1) as neigh
return neigh._id
} on my_hdc_graph
结果：
| neigh._id |
|---|
| Anna |
| Joe |
| Mike |
在分布式投影上运行算法
创建分布式投影
将图集全部投影到shard服务器上并命名为myProj：
CREATE PROJECTION myProj OPTIONS {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true
}
create().projection("myProj", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true
})
参数
算法名：degree
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
edge_schema_property |
"<@schema.?><property>" |
/ | / | 是 | 参与加权度计算的数值类边属性；不包含指定属性的边将被忽略 |
direction |
String | in, out |
/ | 是 | 指定in计算入度，out计算出度；若未设置则计算总度数 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据degree_centrality对结果排序 |
文件回写
CALL algo.degree.write("myProj", {
order: "desc"
}, {
file: {
filename: "degree"
}
})
algo(degree).params({
projection: "myProj",
order: "desc"
}).write({
file: {
filename: "degree"
}
})
结果：
_id,degree_centrality
Anna,5
Cathy,4
Joe,3
Mike,3
Bob,2
Sam,2
Bill,1
Tim,0
数据库回写
将结果中的degree_centrality值写入指定点属性。该属性类型为double。
CALL algo.degree.write("myProj", {
edge_schema_property: 'score'
}, {
db: {
property: "degree"
}
})
algo(degree).params({
projection: "myProj",
edge_schema_property: 'score'
}).write({
db:{
property: 'degree'
}
})