✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✓ 统计值

概述

连通分量（Connected Component）算法能识别图中的连通分量，这是考察图的连通性和拓扑特征的重要指标。

图中连通分量的数量可作为一种粗粒度的计量方式。如果对图进行某些操作或修改后，连通分量的数量保持不变，则表明图的宏观连通性和拓扑特征没有发生显着变化。

连通分量信息在各种图分析情景中都很有价值。例如，在社交网络中，如果连通分量的数量随着时间的推移保持不变，则意味着网络内的整体连接模式和社区结构没有发生实质性变化。

基本概念

连通分量

一个连通分量是图中节点的一个最大子集，该子集中的所有节点都可以通过路径相互连接。最大子集意味着在不破坏连接要求的情况下，无法向子集添加其他节点。

连通分量的数量反映全图的连通性以及存在多少不同的子图。如果一个图只有一个连通分量，该连通分量由全图节点组成，这样的图称为连通图（Connected Graph）。

强连通分量，弱连通分量

与连通分量相关有两个重要概念——弱连通分量（Weakly Connected Component, WCC）和强连通分量（Strongly Connected Component, SCC）：

• 弱连通分量是指有向或无向图中节点的子集，其中任何一对节点之间存在路径，而不考虑边的方向如何。
• 强连通分量是有向图中节点的子集，其中每对节点之间都存在一个有向路径。换句话说，对于强连通分量中的任意两个节点 u 和 v，既存在从 u 到 v 的有向路径，也存在从 v 到 u 的有向路径。在有向路径中，所有边的方向一致。

上面的例子对同一张图分别进行了强、弱连通分量的计算，结果可划分为 3 个强连通分量，或 2 个弱连通分量。由于强连通分量的判断条件更严格，有向图中的强连通分量的个数总是大于或等于弱连通分量的个数。

特殊说明

• 图中的每个孤点都是一个连通分量，既是强连通分量，也是弱连通分量。

语法

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

示例

示例图如下：

文件回写

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

属性回写

algo(connected_component).params().write({
  db:{ 
    property: 'wcc_id'
  }
})

统计值：community_count = 2
结果：每个节点的社区号回写至名为 wcc_id 的点属性下

直接返回

algo(connected_component).params({
  cc_type: 2
}) as r1, r2
return r1, r2

结果：r1 和 r2

流式返回

algo(connected_component).params({
  cc_type: 2
}).stream() as r
return r

结果：r

algo(connected_component).params({
  cc_type: 2,
  order: 'asc'
}).stream({
  mode: 2
}) as r
return r

结果：r

统计返回

algo(connected_component).params().stats() as count
return count

结果：count