概述
连通分量(Connected Component)算法能识别图中的连通分量,这是考察图的连通性和拓扑特征的重要指标。
图中连通分量的数量可作为一种粗粒度的计量方式。如果对图进行某些操作或修改后,连通分量的数量保持不变,则表明图的宏观连通性和拓扑特征没有发生显着变化。
连通分量信息在各种图分析情景中都很有价值。例如,在社交网络中,如果连通分量的数量随着时间的推移保持不变,则意味着网络内的整体连接模式和社区结构没有发生实质性变化。
基本概念
连通分量
一个连通分量是图中节点的一个最大子集,该子集中的所有节点都可以通过路径相互连接。最大子集意味着在不破坏连接要求的情况下,无法向子集添加其他节点。
连通分量的数量反映全图的连通性以及存在多少不同的子图。如果一个图只有一个连通分量,该连通分量由全图节点组成,这样的图称为连通图(Connected Graph)。
强连通分量,弱连通分量
与连通分量相关有两个重要概念——弱连通分量(Weakly Connected Component, WCC)和强连通分量(Strongly Connected Component, SCC):
- 弱连通分量是指有向或无向图中节点的子集,其中任何一对节点之间存在路径,而不考虑边的方向如何。
- 强连通分量是有向图中节点的子集,其中每对节点之间都存在一个有向路径。换句话说,对于强连通分量中的任意两个节点u和v,既存在从u到v的有向路径,也存在从v到u的有向路径。在有向路径中,所有边的方向一致。
![](https://img.ultipa.cn/draw/draw_2f5f2e1e0d644c729e5b3cd09344fcb5.jpg?v='1684744743791')
上面的例子对同一张图分别进行了强、弱连通分量的计算,结果可划分为3个强连通分量,或2个弱连通分量。由于强连通分量的判断条件更严格,有向图中的强连通分量的个数总是大于或等于弱连通分量的个数。
特殊说明
- 图中的每个孤点都是一个连通分量,既是强连通分量,也是弱连通分量。
语法
- 命令:
algo(connected_component)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
cc_type | int | 1 , 2 |
1 |
是 | 1 代表弱连通分量,2 代表强连通分量 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
order | string | asc , desc |
/ | 是 | 按连通分量中的节点数对结果进行排序(仅在stream() 执行方式mode为2时有效) |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_042ef56059474e65b807a0fece46b87f.jpg?v='1684746408422')
文件回写
配置项 | 回写内容 |
---|---|
filename_community_id | _id ,community_id |
filename_ids | community_id ,_id ,_id ,... |
filename_num | community_id ,count |
algo(connected_component).params({
cc_type: 1
}).write({
file:{
filename_community_id: 'f1',
filename_ids: 'f2',
filename_num: 'f3'
}
})
统计值:community_count = 2
结果:文件f1、f2、f3
Alice,0
Bill,0
Bob,0
Sam,0
Joe,0
Anna,0
Cathy,6
Mike,6
0,Alice,Bill,Bob,Sam,Joe,Anna,
6,Cathy,Mike,
0,6
6,2
属性回写
配置项 | 回写内容 | 回写至 | 数据类型 |
---|---|---|---|
property | community_id |
点属性 | int64 |
algo(connected_component).params().write({
db:{
property: 'wcc_id'
}
})
统计值:community_count = 2
结果:每个节点的社区号回写至名为wcc_id的点属性下
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其社区号 | _uuid , community_id |
1 | KV | 社区数量 | community_count |
algo(connected_component).params({
cc_type: 2
}) as r1, r2
return r1, r2
结果:r1和r2
_uuid | community_id |
---|---|
8 | 0 |
7 | 0 |
6 | 0 |
5 | 3 |
4 | 0 |
3 | 0 |
2 | 6 |
1 | 7 |
community_count |
---|
4 |
流式返回
配置项 | 参数 | 别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|---|---|
mode | 1 或忽略 |
0 | []perNode | 点及其社区号 | _uuid , community_id |
2 |
[]perCommunity | 社区及其节点数 | community_id , count |
algo(connected_component).params({
cc_type: 2
}).stream() as r
return r
结果:r
_uuid | community_id |
---|---|
8 | 0 |
7 | 0 |
6 | 0 |
5 | 3 |
4 | 0 |
3 | 0 |
2 | 6 |
1 | 7 |
algo(connected_component).params({
cc_type: 2,
order: 'asc'
}).stream({
mode: 2
}) as r
return r
结果:r
community_id | count |
---|---|
6 | 1 |
7 | 1 |
3 | 1 |
0 | 5 |
统计返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | KV | 社区数量 | community_count |
algo(connected_component).params().stats() as count
return count
结果:count
community_count |
---|
2 |