数据分析之图算法: 基于Spark和Neo4j

106

｜

第

6

章

6.4

　连通分量算法

连通分量算法

（

connected components algorithm

，也称

联盟查找算法

或

弱连通分量算法

）可

在无向图中发现连通节点集合。与强连通分量算法不同，该算法只需要节点对之间存在单

向路径，而强连通分量算法需要节点对之间存在双向路径。

Bernard A. Galler

和

Michael J.

Fisher

在

1964

年发表的论文“

An Improved Equivalence Algorithm

”中首次阐述了这种算法。

6.4.1

　何时使用连通分量算法

与强连通分量算法一样，连通分量算法通常在分析的早期使用，用于理解图的结构。因为

该算法的伸缩性强，所以可用于需要频繁更新的图。该算法可以快速显示群组间共同的新

节点，这对如欺诈检测这样的分析来说非常有用。

应该养成习惯，将运行连通分量算法作为常规图分析的准备步骤，测试图是否连通。执行

这一快速测试可以避免意外地在图的某个非连通分量上运行算法，导致结果出错。

示范用例如下。

•

追踪数据库记录簇，作为数据去重过程的一部分。去重是主数据管理应用中的一项重

要任务，详见

Alvaro Monge

和

Charles Elkan

的论文“

An Efficient Domain-Independent

Algorithm for Detecting Approximately Duplicate Database Records

”。

•

分析引文网络。这项研究使用连通分量算法来了解网络连通情况，然后看看如果从图

中移走“中心”节点或“权威”节点 ...