概述

重叠相似度（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的一步邻域集合分别为：

• N_u = {a,b,c,d,e}
• N_v = {d,e,f}

因此，它们之间的重叠相似度为2 / 3 = 0.666667。

在实践中，为了计算基于共同邻居的相似性指标，比如重叠相似度，有时可能需要将一些点属性转换为点Schema。例如，当考虑两个@申请点之间的相似性时，申请的电话号码、邮箱、设备IP等信息可能是存储为点属性的。如果要使用这些信息来度量相似性，则应将它们设计为节点加入图中。

加权重叠相似度

加权重叠相似度是经典重叠相似度的扩展，它考虑两个集合中与各元素相关的权重。

加权重叠相似度的计算公式为：

在这个加权图中，一步邻域集合N_u和N_v的并集为{a,b,c,d,e,f}。将该集合中的每个元素设置为目标节点与相应节点间边权重的和；如果它们之间没有边，则设置为0：

因此，节点u和节点v的加权重叠相似度为(0+0+0+0.5+0.5+0) / 3.1 = 0.322581.

请确保目标节点与邻居节点之间的边权重之和大于等于0。

特殊说明

• 重叠相似度算法忽略边的方向，按照无向边进行计算。
• 重叠相似度算法忽略自环边。

语法

• 命令：algo(similarity)
• 参数：

本算法有两种计算模式：

1. 配对：同时配置ids/uuids和ids2/uuids2时，将ids/uuids中的每个节点分别与ids2/uuids2中的每个节点配对（忽略相同节点），逐对计算相似度。
2. 选拔：仅配置ids/uuids时，对于其中的每个节点，计算其与图中其他所有节点的相似度，返回所有或限定个数的与其相似度大于0的结果，并按相似度降序排列。

示例

示例图如下：

文件回写

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

直接返回

algo(similarity).params({ 
  uuids: [1,2], 
  uuids2: [2,3,4],
  type: 'overlap'
}) as overlap
return overlap 

结果：overlap

algo(similarity).params({
  uuids: [1,2],
  type: 'overlap',
  top_limit: 1
}) as top
return top

结果：top

流式返回

algo(similarity).params({ 
  uuids: [3], 
  uuids2: [1,2,4],
  type: 'overlap'
}).stream() as overlap
where overlap.similarity > 0
return overlap

结果：overlap

algo(similarity).params({
  uuids: [1],
  type: 'overlap',
  top_limit: 2
}).stream() as top
return top

结果：top