✓ 文件回写 ✕ 属性回写 ✕ 直接返回 ✕ 流式返回 ✕ 统计值
概述
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 边连通性的最大节点子集 Vi ⊆ V,由 Vi 诱导的子图具有 k 边连通性。
举例来说,在社交网络中,我们可能更感兴趣的是发现那些紧密联系的人群,而不是计算整个社交网络的全局连通性。
特殊说明
- 当 k = 1 时,相当于寻找图的连通分量。
- K 边连通分量算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
algo(kcc)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
k | int | >1 | / | 否 | K 边连通分量中,任意一对节点之间存在 k 条边不相交路径 |
示例
示例图如下:
文件回写
配置项 |
回写内容 |
描述 |
---|---|---|
filename | _id ,_id ,... |
每个 K 边连通分量的节点 ID |
algo(kcc).params({
k: 3
}).write({
file:{
filename: 'result'
}
})
结果:文件 result
F,G,I,H,
J,K,M,L,