概述

杰卡德相似度（Jaccard Similarity）也称杰卡德指数（Jaccard Index），由 Paul Jaccard 于 1901 年提出，是一种基于网络半结构信息定义的节点相似性指标。它用两个集合交集的大小除以并集的大小，以此来表示两个集合的相似程度。在图上，杰卡德相似度是用节点表示集合，用节点的邻居表示集合中的元素，计算两个节点的共同邻居在所有邻居中的数量占比。

集合中的元素通常代表应用场景中实体的一系列属性，例如计算两个信贷申请之间的相似度时，这些元素就是申请表中填写的手机号、邮箱、设备IP、公司名称等。在一般的图应用中，这类信息通常会存储为节点的属性，但是在执行本算法时，这些信息需要设计为节点并入图。

杰卡德相似度的取值范围是 [0,1]，数值越大越相似。

基本概念

集合

集合由多个元素构成；集合中的元素是无序的、互不相同的；集合 A 中元素的数量就是集合 A 的大小，记作|A|。

由所有既属于集合 A 又属于集合 B 的元素构成的集合称作 A 和 B 的交集，记作A⋂B；由所有属于集合 A 或者集合 B 的元素构成的集合称作 A 和 B 的并集，记作A⋃B。

上图中，集合 A 为{b,c,e,f,g}，集合 B 为{a,b,d,g}，交集 A⋂B 为{b,g}，并集 A⋃B 为{a,b,c,d,e,f,g}。

杰卡德相似度

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

根据此定义，可计算前面例子中集合 A 与 B 的杰卡德相似度：2 / 7 = 0.2857。

邻居

用图中节点 x 的邻居集合 Kx 表示集合 A，节点 y 的邻居集合 Ky 表示集合 B。需要注意的是，Kx 和 Ky 均既不包含重复值，也不包含 x 和 y。因此，在图上按边查找邻居时需要排除以下干扰：

• x、y 与邻居之间的多条边
• x、y 的自环边
• x 和 y 之间的边

上图中，红、绿节点的共同邻居数为 2，邻居数总和为 6，这两个节点的杰卡德相似度为 2 / 6 = 0.3333。

特殊处理

孤点、不连通图

在实际应用中很少出现有计算价值的孤点（空集），有孤点则交集为空，杰卡德相似度为 0。

属于不同连通分量的两个点，它们的杰卡德相似度必然为 0。

自环边

节点的自环边不会增加节点的邻居数。

有向边

对于有向边，本算法会忽略边的方向，按照无向边进行计算。

命令和参数配置

• 命令：algo(similarity)
• params() 参数配置项如下：

计算模式

本算法有两种计算模式：

1. 配对模式：配置有效的两组节点时，将第一组与第二组中的节点两两配对（笛卡尔乘积），逐对计算相似度
2. 选拔模式：仅配置（第）一组有效节点时，对于其中每一个节点，计算其与图中其他所有点的相似度，返回相似度大于 0 的结果并按相似度大小降序排列

示例

示例图

示例图展示 4 位用户 userA、userB、userC 和 userD（UUID 依次为 1、2、3、4）对各项体育运动的喜爱情况：

任务回写

1. 文件回写

示例：计算 userC 与 userA、userB、userD 两两之间的杰卡德相似度，将算法结果回写至文件

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

示例：计算用户 UUID = 1,2,3,4 各自与其他所有节点的杰卡德相似度，将算法结果回写至文件

algo(similarity).params({
  uuids: [1,2,3,4],
  type: "jaccard"
}).write({
  file:{ 
    filename: "list"
  }
})

结果：文件 list

userA,userC:0.250000;userB:0.200000;userD:0.166667;
userB,userC:0.500000;userD:0.250000;userA:0.200000;
userC,userB:0.500000;userA:0.250000;
userD,userB:0.250000;userA:0.166667;

2. 属性回写

算法不支持属性回写。

3. 统计回写

算法无统计值。

直接返回

示例：计算用户 UUID = 1 与用户 UUID = 2,3,4 两两之间的杰卡德相似度，并按照相似性大小降序排列结果

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

结果：

示例：分别选拔图中与节点 UUID = 1,2 间杰卡德相似度最高的节点

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

结果：

流式返回

示例：计算用户 UUID = 3 与用户 UUID = 1,2,4 两两之间的杰卡德相似度，仅返回相似度大于 0 的结果

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

结果：

示例：选拔图中与节点 UUID = 1 杰卡德相似度最高的两个节点

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

结果：

实时统计

算法无统计值。