概述

K边连通分量（k-Edge Connected Components）算法旨在根据图中的边来识别具有强关联的节点组。该算法关注的是边的连接情况，以揭示图中节点之间的紧密关系和群组结构。通过考虑边的连通性，该算法能够识别出在图中形成紧密连接的节点组，这些节点组可能代表着社区、集群或其他相关的结构。

算法的相关资料如下：

• T. Wang, Y. Zhang, F.Y.L. Chin, H. Ting, Y.H. Tsin, S. Poon, A Simple Algorithm for Finding All k-Edge-Connected Components (2015)

基本概念

边连通性

图的边连通性（Edge Connectivity）是指为降低或破坏图的连通性所需移除的最小边数。换句话说，它表示了图在面对边的缺失或故障时能够恢复到连通状态的能力。对于给定的图G=(V, E)，如果在删除任意k-1或更少条边后，图G仍然保持连通，则称图G具有k边连通性。

边连通性也可以理解为图中任意两个节点之间的边不相交路径（Edge-disjoint Paths）的最大数量。如果图的边连通性为k，则表示图中任意一对节点之间存在k条边不相交路径。

下面展示的是一个具有3边连通性的图以及每对节点之间的所有边不相交路径。

一组边不相交路径是指它们没有任何共同边。

K 边连通分量

K边连通分量算法的目标不是确定全图G是否具有k边连通性，而是要找到图中具有k边连通性的最大节点子集V_i⊆V，由V_i诱导的子图具有k边连通性。

举例来说，在社交网络中，我们可能更感兴趣的是发现那些紧密联系的人群，而不是计算整个社交网络的全局连通性。

特殊说明

• 当k=1时，相当于寻找图的连通分量。
• K边连通分量算法忽略边的方向，按照无向边进行计算。

示例图集

创建示例图集：

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

创建HDC图集

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

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

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

参数

算法名：kcc

文件回写

CALL algo.kcc.write("hdc_kcc", {
  params: {
    k: 3,
    return_id_uuid: "id"
  },
  return_params: {
    file: {
      filename: "kcc_result"
    }
  }
})

algo(kcc).params({
  project: "hdc_kcc",
  k: 3,
  return_id_uuid: "id"
}).write({
  file: {
    filename: "kcc_result"
  }
})

_ids
M,J,K,L
G,F,H,I