概述

杰卡德相似度（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。

特殊说明

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

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
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上，并命名为 hdc_sim_nbr：

CALL hdc.graph.create("hdc-server-1", "hdc_sim_nbr", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_sim_nbr", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

参数

算法名：similarity

该算法包含两种计算模式：

1. 配对：同时配置ids/uuids和ids2/uuids2时，ids/uuids中的每个节点与ids2/uuids2中的每个节点配对（自配对除外），并逐对计算相似度。
2. 选拔：若仅配置了ids/uuids，则逐对计算其中各节点与图中所有其他节点间的相似度，返回所有或指定个数的相似度大于0的结果，并按相似度降序排列。

文件回写

CALL algo.similarity.write("hdc_sim_nbr", {
  params: {
    return_id_uuid: "id",
    ids: "userC",
    ids2: ["userA", "userB", "userD"],
    type: "jaccard"
  },
  return_params: {
    file: {
      filename: "jaccard"
    }
  }
})

algo(similarity).params({
  project: "hdc_sim_nbr",
  return_id_uuid: "id",
  ids: "userC",
  ids2: ["userA", "userB", "userD"],
  type: "jaccard"  
}).write({
  file: {
    filename: "jaccard"
  }
})

结果：

_id1,_id2,similarity
userC,userA,0.25
userC,userB,0.5
userC,userD,0

完整返回

CALL algo.similarity("hdc_sim_nbr", {
  params: {
    return_id_uuid: "id",
    ids: ["userA","userB"], 
    ids2: ["userB","userC","userD"],
    type: "jaccard"
  },
  return_params: {}
}) YIELD jacc
RETURN jacc

exec{
  algo(similarity).params({
    return_id_uuid: "id",
    ids: ["userA","userB"], 
    ids2: ["userB","userC","userD"],
    type: "jaccard"
  }) as jacc
  return jacc
} on hdc_sim_nbr

结果：

流式返回

CALL algo.similarity("hdc_sim_nbr", {
  params: {
    return_id_uuid: "id",
    ids: ["userA"], 
    type: "jaccard",
    edge_weight_property: "weight",
    top_limit: 2    
  },
  return_params: {
  	stream: {}
  }
}) YIELD jacc
RETURN jacc

exec{
  algo(similarity).params({
    return_id_uuid: "id",
    ids: ["userA"], 
    type: "jaccard",
    edge_weight_property: "weight",
    top_limit: 2  
  }).stream() as jacc
  return jacc
} on hdc_sim_nbr

结果：