概述

传导性是用于评估图中社区或聚类质量的指标。研究表明，基于传导性的评分函数最能反映社区的真实结构。

• J. Yang, J. Leskovec, Defining and Evaluating Network Communities based on Ground-truth (2012)

基本概念

传导性

直观地说，好的社区应当在内部紧密连接，但与图的其他部分连接较弱。

对于社区C和图中其他部分C'，C的传导性定义为切割大小（C和C'之间的边数）与C和C'之间的最小体积（即其中节点度数之和）的比值：

如下例所示，社区C通过3条边与图中其他部分连接，即cut(C, C') = 3。C的传导性为cond(C) = 3/min(19, 17) = 3/17 = 0.176471。

如果调整分割，让社区C多包含一个点，则C的传导性变为cond(C) = 3/min(21, 15) = 3/15 = 0.2。

社区识别中，传导性较小更为理想，这样可以识别内部紧密连接且与外部连接较少的社区。相反，传导性较大，意味着社区内部连接松散，与外部连接较多，表明社区不是紧密连接的。

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
create().node_property(@default, "community_id", uint32)
insert().into(@default).nodes([{_id:"A", community_id: 1}, {_id:"B", community_id: 1}, {_id:"C", community_id: 1}, {_id:"D", community_id: 2}, {_id:"E", community_id: 2}, {_id:"F", community_id: 2}, {_id:"G", community_id: 1}, {_id:"H", community_id: 3}, {_id:"I", community_id: 3}, {_id:"J", community_id: 3}, {_id:"K", community_id: 3}])
insert().into(@default).edges([{_from:"A", _to:"B"}, {_from:"A", _to:"C"}, {_from:"A", _to:"D"}, {_from:"A", _to:"E"}, {_from:"A", _to:"G"}, {_from:"D", _to:"E"}, {_from:"D", _to:"F"}, {_from:"E", _to:"F"}, {_from:"G", _to:"D"}, {_from:"G", _to:"H"}, {_from:"J", _to:"D"}, {_from:"I", _to:"H"}, {_from:"I", _to:"J"}, {_from:"H", _to:"K"}, {_from:"J", _to:"K"}])

创建HDC图集

将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_cond：

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

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

参数

算法名：conductance

文件回写

CALL algo.conductance.write("hdc_cond", {
  params: {
    community_property: "community_id"
  },
  return_params: {
    file: {
      filename: "conductance"
    }
  }
})

algo(conductance).params({
  project: "hdc_cond",
  community_property: "community_id"
}).write({
  file: {
	filename: "conductance"
  }
})

完整返回

CALL algo.conductance("hdc_cond", {
  params: {
    community_property: "community_id"
  },
  return_params: {}
}) YIELD r
RETURN r

exec{
  algo(conductance).params({
    community_property: "community_id"
  }) as r
  return r
} on hdc_cond

流式返回

CALL algo.conductance("hdc_cond", {
  params: {
    community_property: "community_id"
  },
  return_params: {
    stream: {}
  }
}) YIELD r
RETURN r

exec{
  algo(conductance).params({
    community_property: "community_id"
  }).stream() as r
  return r
} on hdc_cond