概述
重叠相似度(Overlap Similarity)是杰卡德相似度的一种延申,也叫Szymkiewicz–Simpson系数。它用两个集合的交集大小除以两个集合中较小集合的大小,以此来表示两个集合的相似程度。
重叠相似度的取值范围是0到1;1意味着其中一个集合是另一个集合的子集或两个集合完全一样,0意味着两个集合没有任何共同元素。
基本概念
重叠相似度
已知集合A和B,它们之间的重叠相似度可以表示为:
![](https://img.ultipa.cn/2022-08-08-14-47-36-overlap.jpg)
在下面的例子中,集合A = {b,c,e,f,g},集合B = {a,d,b,g},它们的交集A⋂B = {b,g},因此A和B的重叠相似度为 2 / 4 = 0.5
。
![](https://img.ultipa.cn/draw/draw_643f71d054c34c9d83cd682b0bd74402.jpg?v='1680592080160')
将重叠相似度应用到图上用来判断两个节点之间的相似度时,我们使用目标节点的一步邻域集合来表示节点。这个一步邻域集合:
- 没有重复的节点;
- 不包含两个目标节点。
![](https://img.ultipa.cn/draw/draw_86e6115da2be4ebea513a350b03fee51.jpg?v='1705742284029')
上图中,节点u和节点v的一步邻域集合分别为:
- Nu = {a,b,c,d,e}
- Nv = {d,e,f}
因此,它们之间的重叠相似度为2 / 3 = 0.666667
。
在实践中,为了计算基于共同邻居的相似性指标,比如重叠相似度,有时可能需要将一些点属性转换为点Schema。例如,当考虑两个
@申请
点之间的相似性时,申请的电话号码、邮箱、设备IP等信息可能是存储为点属性的。如果要使用这些信息来度量相似性,则应将它们设计为节点加入图中。
加权重叠相似度
加权重叠相似度是经典重叠相似度的扩展,它考虑两个集合中与各元素相关的权重。
加权重叠相似度的计算公式为:
![](https://img.ultipa.cn/img/2024-01-20-17-53-10-weighted-overlap.jpg)
![](https://img.ultipa.cn/draw/draw_a59802aecd0449ddab9758f8e705ac49.jpg?v='1705740462299')
在这个加权图中,一步邻域集合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。
特殊说明
- 重叠相似度算法忽略边的方向,按照无向边进行计算。
- 重叠相似度算法忽略自环边。
语法
- 命令:
algo(similarity)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 否 | 待计算的第一组节点的ID/UUID |
ids2 / uuids2 | []_id / []_uuid |
/ | / | 是 | 待计算的第二组节点的ID/UUID |
type | string | overlap |
cosine |
否 | 相似度衡量指标;计算重叠相似度时,保持此项为overlap |
edge_weight_property | @<schema>?.<property> |
数值类型,需LTE | / | 是 | 用作边权重的边属性;如果两点之间有多条边,权重值为所有边的指定属性值的和 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
top_limit | int | ≥-1 | -1 |
是 | 在选拔模式下,限制ids /uuids 中每个节点返回的最大结果条数,-1 返回所有相似度大于0的结果;在配对模式下,此参数无效 |
本算法有两种计算模式:
- 配对:同时配置
ids
/uuids
和ids2
/uuids2
时,将ids
/uuids
中的每个节点分别与ids2
/uuids2
中的每个节点配对(忽略相同节点),逐对计算相似度。 - 选拔:仅配置
ids
/uuids
时,对于其中的每个节点,计算其与图中其他所有节点的相似度,返回所有或限定个数的与其相似度大于0的结果,并按相似度降序排列。
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_df4a3744a45d41a19b4eefa57f0d9a7d.jpg?v='1705977879656')
文件回写
配置项 | 回写内容 |
---|---|
filename | node1 ,node2 ,similarity |
algo(similarity).params({
ids: 'userC',
ids2: ['userA', 'userB', 'userD'],
type: 'overlap'
}).write({
file:{
filename: 'sc'
}
})
结果:文件sc
userC,userA,0.25
userC,userB,0.5
userC,userD,0
algo(similarity).params({
uuids: [1,2,3,4],
type: 'overlap'
}).write({
file:{
filename: 'list'
}
})
结果:文件list
userA,userC,1
userA,userB,0.5
userA,userD,0.333333
userB,userC,1
userB,userA,0.5
userB,userD,0.5
userC,userA,1
userC,userB,1
userD,userB,0
userD,userA,0.333333
直接返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNodePair | 各点对及相似度 | node1 , node2 , similarity |
algo(similarity).params({
uuids: [1,2],
uuids2: [2,3,4],
type: 'overlap'
}) as overlap
return overlap
结果:overlap
node1 | node2 | similarity |
---|---|---|
1 | 2 | 0.5 |
1 | 3 | 1 |
1 | 4 | 0.333333333333333 |
2 | 3 | 1 |
2 | 4 | 0.5 |
algo(similarity).params({
uuids: [1,2],
type: 'overlap',
top_limit: 1
}) as top
return top
结果:top
node1 | node2 | similarity |
---|---|---|
1 | 3 | 1 |
2 | 3 | 1 |
流式返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNodePair | 各点对及相似度 | node1 , node2 , similarity |
algo(similarity).params({
uuids: [3],
uuids2: [1,2,4],
type: 'overlap'
}).stream() as overlap
where overlap.similarity > 0
return overlap
结果:overlap
node1 | node2 | similarity |
---|---|---|
3 | 1 | 1 |
3 | 2 | 1 |
algo(similarity).params({
uuids: [1],
type: 'overlap',
top_limit: 2
}).stream() as top
return top
结果:top
node1 | node2 | similarity |
---|---|---|
1 | 3 | 1 |
1 | 2 | 0.5 |