HDC
概述
重叠相似度（Overlap Similarity）是杰卡德相似度的一种延申，也叫Szymkiewicz–Simpson系数。它用两个集合的交集大小除以两个集合中较小集合的大小，以此来表示两个集合的相似程度。
重叠相似度的取值范围是0到1；1意味着其中一个集合是另一个集合的子集或两个集合完全一样，0意味着两个集合没有任何共同元素。
基本概念
重叠相似度
已知集合A和B，它们之间的重叠相似度可以表示为：
在下面的例子中，集合A = {b,c,e,f,g}，集合B = {a,d,b,g}，它们的交集A⋂B = {b,g}，因此A和B的重叠相似度为 2 / 4 = 0.5。
将重叠相似度应用到图上用来判断两个节点之间的相似度时，我们使用目标节点的一步邻域集合来表示节点。这个一步邻域集合：
- 没有重复的节点；
- 不包含两个目标节点。
上图中，节点u和节点v的一步邻域集合分别为：
- Nu = {a,b,c,d,e}
- Nv = {d,e,f}
因此，它们之间的重叠相似度为2 / 3 = 0.666667。
在实践中，为了计算基于共同邻居的相似性指标，比如重叠相似度，有时可能需要将一些点属性转换为点Schema。例如，当考虑两个
@申请点之间的相似性时，申请的电话号码、邮箱、设备IP等信息可能是存储为点属性的。如果要使用这些信息来度量相似性，则应将它们设计为节点加入图中。
加权重叠相似度
加权重叠相似度是经典重叠相似度的扩展，它考虑两个集合中与各元素相关的权重。
加权重叠相似度的计算公式为：
在这个加权图中，一步邻域集合Nu和Nv的并集为{a,b,c,d,e,f}。将该集合中的每个元素设置为目标节点与相应节点间边权重的和；如果它们之间没有边，则设置为0：
| a | b | c | d | e | f | 元素和 | |
|---|---|---|---|---|---|---|---|
| N'u | 1 | 1 | 1 | 1 | 0.5 | 0 | 4.5 |
| N'v | 0 | 0 | 0 | 0.5 | 1.5 + 0.1 =1.6 | 1 | 3.1 |
因此，节点u和节点v的加权重叠相似度为(0+0+0+0.5+0.5+0) / 3.1 = 0.322581.
请确保目标节点与邻居节点之间的边权重之和大于等于0。
特殊说明
- 重叠相似度算法忽略边的方向，按照无向边进行计算。
- 重叠相似度算法忽略自环边。
示例图
在一个空图中运行以下语句定义图结构并插入数据：
ALTER GRAPH CURRENT_GRAPH ADD NODE {
user (),
sport()
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
like ()-[{weight int32}]->()
};
INSERT (userA:user {_id: "userA"}),
(userB:user {_id: "userB"}),
(userC:user {_id: "userC"}),
(userD:user {_id: "userD"}),
(running:sport {_id: "running"}),
(tennis:sport {_id: "tennis"}),
(baseball:sport {_id: "baseball"}),
(swimming:sport {_id: "swimming"}),
(badminton:sport {_id: "badminton"}),
(iceball:sport {_id: "iceball"}),
(userA)-[:like {weight: 2}]->(tennis),
(userA)-[:like {weight: 1}]->(baseball),
(userA)-[:like {weight: 3}]->(swimming),
(userA)-[:like {weight: 2}]->(badminton),
(userB)-[:like {weight: 1}]->(running),
(userB)-[:like {weight: 3}]->(swimming),
(userC)-[:like {weight: 2}]->(swimming),
(userD)-[:like {weight: 1}]->(running),
(userD)-[:like {weight: 2}]->(badminton),
(userD)-[:like {weight: 2}]->(iceball);
create().node_schema("user").node_schema("sport").edge_schema("like");
create().edge_property(@like, "weight", int32);
insert().into(@user).nodes([{_id:"userA"}, {_id:"userB"}, {_id:"userC"}, {_id:"userD"}]);
insert().into(@sport).nodes([{_id:"running"}, {_id:"tennis"}, {_id:"baseball"}, {_id:"swimming"}, {_id:"badminton"}, {_id:"iceball"}]);
insert().into(@like).edges([{_from:"userA", _to:"tennis", weight:2}, {_from:"userA", _to:"baseball", weight:1}, {_from:"userA", _to:"swimming", weight:3}, {_from:"userA", _to:"badminton", weight:2}, {_from:"userB", _to:"running", weight:1}, {_from:"userB", _to:"swimming", weight:3}, {_from:"userC", _to:"swimming", weight:2}, {_from:"userD", _to:"running", weight:1}, {_from:"userD", _to:"badminton", weight:2}, {_from:"userD", _to:"iceball", weight: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")
参数
算法名：similarity
| 参数名 | 类型 | 规范 | 默认值 | 可选 | 描述 | |
|---|---|---|---|---|---|---|
ids/uuids |
_id/_uuid |
是 | 通过_id或_uuid指定参与计算的第一组点；若未设置，则图中所有点均参与计算 |
算法支持两种计算模式：
|
||
ids2/uuids2 |
_id/_uuid |
是 | 通过_id或_uuid指定参与计算的第二组点。如果仅设置ids2/uuids2（并未设置ids/uuids2），算法不返回结果 |
|||
type |
String | overlap |
cosine |
否 | 指定待计算的相似度类型；计算重叠相似度时，设置为overlap |
|
edge_weight_property |
[]"<@schema.?><property>" |
是 | 指定作为权重的数值类型边属性，权重值为所有指定属性值的总和；不包含指定属性的边将被忽略 | |||
return_id_uuid |
String | uuid,id,both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
|
order |
String | asc,desc |
是 | 根据similarity分值对结果排序 |
||
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数。-1表示返回所有结果 |
|
top_limit |
Integer | ≥-1 | -1 |
是 | 在选拔模式下，限制ids/uuids中每个节点返回的结果数。-1表示返回所有相似度大于0的结果。配对模式下，该参数不生效 |
|
文件回写
CALL algo.similarity.write("my_hdc_graph", {
return_id_uuid: "id",
ids: "userC",
ids2: ["userA", "userB", "userD"],
type: "overlap"
}, {
file: {
filename: "overlap"
}
})
algo(similarity).params({
projection: "my_hdc_graph",
return_id_uuid: "id",
ids: "userC",
ids2: ["userA", "userB", "userD"],
type: "overlap"
}).write({
file: {
filename: "overlap"
}
})
结果：
_id1,_id2,similarity
userC,userA,1
userC,userB,1
userC,userD,0
完整返回
配对模式下计算相似度：
CALL algo.similarity.run("my_hdc_graph", {
return_id_uuid: "id",
ids: ["userA","userB"],
ids2: ["userB","userC","userD"],
type: "overlap"
}) YIELD overlap
RETURN overlap
exec{
algo(similarity).params({
return_id_uuid: "id",
ids: ["userA","userB"],
ids2: ["userB","userC","userD"],
type: "overlap"
}) as overlap
return overlap
} on my_hdc_graph
结果：
| _id1 | _id2 | similarity |
|---|---|---|
| userA | userB | 0.5 |
| userA | userC | 1 |
| userA | userD | 0.333333 |
| userB | userC | 1 |
| userB | userD | 0.5 |
流式返回
CALL algo.similarity.stream("my_hdc_graph", {
return_id_uuid: "id",
ids: ["userA"],
type: "overlap",
edge_weight_property: "weight",
top_limit: 2
}) YIELD overlap
RETURN overlap
exec{
algo(similarity).params({
return_id_uuid: "id",
ids: ["userA"],
type: "overlap",
edge_weight_property: "weight",
top_limit: 2
}).stream() as overlap
return overlap
} on my_hdc_graph
结果：
| _id1 | _id2 | similarity |
|---|---|---|
| userA | userC | 1 |
| userA | userB | 0.75 |