概述

杰卡德相似度（Jaccard Similarity）也称为杰卡德指数（Jaccard Index），由Paul Jaccard于1901年提出，用于度量两个集合的相似性。在图中，收集节点的邻居节点作为邻域集合，两个节点的邻域集合越相似，这两个节点就越相似。

杰卡德相似度的取值范围是0到1；1意味着两个集合完全一样，0意味着两个集合没有任何共同元素。

基本概念

杰卡德相似度

已知集合A和B，它们之间的杰卡德相似度可表示为：

在下面的例子中，集合A = {b,c,e,f,g}，集合B = {a,d,b,g}，它们的交集A⋂B = {b,g}，并集A⋃B = {a,b,c,d,e,f,g}，因此A和B的杰卡德相似度为2 / 7 = 0.285714。

将杰卡德相似度应用到图上用来判断两个节点之间的相似度时，我们使用目标节点的一步邻域集合来表示节点。这个一步邻域集合：

• 没有重复的节点；
• 不包含两个目标节点。

上图中，节点u和节点v的一步邻域集合分别为：

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

因此，它们之间的杰卡德相似度为2 / 6 = 0.333333。

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

加权杰卡德相似度

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

加权杰卡德相似度的计算公式为：

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

因此，节点u和节点v的加权杰卡德相似度为(0+0+0+0.5+0.5+0) / (1+1+1+1+1.6+1) = 0.151515.

请确保目标节点与邻居节点之间的边权重之和大于等于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: 'jaccard'
}).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: 'jaccard'
}).write({
  file:{ 
    filename: 'list'
  }
})

结果：文件list

userA,userC,0.25
userA,userB,0.2
userA,userD:0.166667
userB,userC:0.5
userB,userD,0.25
userB,userA,0.2
userC,userB,0.5
userC,userA,0.25
userD,userB:0.25
userD,userA:0.166667

直接返回

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

结果：jacc

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

结果：top

流式返回

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

结果：jacc

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

结果：top