概述
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边连通性的图以及每对节点之间的所有边不相交路径。
![](https://img.ultipa.cn/draw/draw_516ca76c533f42d59c83973efe95125e.jpg?v='1687142427889')
一组边不相交路径是指它们没有任何共同边。
K 边连通分量
K边连通分量算法的目标不是确定全图G是否具有k边连通性,而是要找到图中具有k边连通性的最大节点子集Vi⊆V,由Vi诱导的子图具有k边连通性。
举例来说,在社交网络中,我们可能更感兴趣的是发现那些紧密联系的人群,而不是计算整个社交网络的全局连通性。
特殊说明
- 当k=1时,相当于寻找图的连通分量。
- K边连通分量算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
algo(kcc)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
k | int | >1 | / | 否 | K边连通分量中,任意一对节点之间存在k条边不相交路径 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_350441442b224f7bad64fb8983024db2.jpg?v='1687145644126')
文件回写
配置项 |
回写内容 |
描述 |
---|---|---|
filename | _id ,_id ,... |
每个K边连通分量的节点 ID |
algo(kcc).params({
k: 3
}).write({
file:{
filename: 'result'
}
})
结果:文件result
F,G,I,H,
J,K,M,L,