概述

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边连通分量算法忽略边的方向，按照无向边进行计算。

语法

• 命令：algo(kcc)
• 参数：

示例

示例图如下：

文件回写

algo(kcc).params({
  k: 3
}).write({
  file:{
    filename: 'result'
  }
})

结果：文件result

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