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，有向自环边被视为一条入边和一条出边。
示例图集
创建示例图集：
// 在空图集中逐行运行以下语句
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上，并命名为 hdc_degree：
CALL hdc.graph.create("hdc-server-1", "hdc_degree", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_degree", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).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("hdc_degree", {
params: {
return_id_uuid: "id",
order: "desc"
},
return_params: {
file: {
filename: "degree"
}
}
})
algo(degree).params({
projection: "hdc_degree",
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("hdc_degree", {
params: {
edge_schema_property: 'score'
},
return_params: {
db: {
property: "degree"
}
}
})
algo(degree).params({
projection: "hdc_degree",
edge_schema_property: 'score'
}).write({
db:{
property: 'degree'
}
})
完整返回
CALL algo.degree("hdc_degree", {
params: {
edge_schema_property: 'score',
return_id_uuid: "id",
order: 'desc'
},
return_params: {}
}) YIELD r
RETURN r
exec{
algo(degree).params({
edge_schema_property: 'score',
return_id_uuid: "id",
order: 'desc'
}) as r
return r
} on hdc_degree
结果：
| _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("hdc_degree", {
params: {
direction: "out",
order: "desc",
limit: 1
},
return_params: {
stream: {}
}
}) 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 hdc_degree
结果：
| neigh._id |
|---|
| Anna |
| Joe |
| Mike |
在分布式投影上运行算法
创建分布式投影
将图集全部投影到shard服务器上并命名为dist_degree：
create().projection("dist_degree", {
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("dist_degree", {
params: {
return_id_uuid: "id",
order: "desc"
},
return_params: {
file: {
filename: "degree"
}
}
})
algo(degree).params({
projection: "dist_degree",
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("dist_degree", {
params: {
edge_schema_property: 'score'
},
return_params: {
db: {
property: "degree"
}
}
})
algo(degree).params({
projection: "dist_degree",
edge_schema_property: 'score'
}).write({
db:{
property: 'degree'
}
})