重叠相似度

概述

重叠相似度（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。

特殊说明

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

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
create().node_schema("user").node_schema("sport").edge_schema("like")
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"}, {_from:"userA", _to:"baseball"}, {_from:"userA", _to:"swimming"}, {_from:"userA", _to:"badminton"}, {_from:"userB", _to:"running"}, {_from:"userB", _to:"swimming"}, {_from:"userC", _to:"swimming"}, {_from:"userD", _to:"running"}, {_from:"userD", _to:"badminton"}, {_from:"userD", _to:"iceball"}])

创建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: "overlap"
  },
  return_params: {
    file: {
      filename: "overlap"
    }
  }
})

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

结果：

_id1,_id2,similarity
userC,userA,1
userC,userB,1
userC,userD,0

完整返回

配对模式下计算相似度：

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

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

结果：

流式返回

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

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

结果：