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

102

｜

第

6

章

将有向图分解为它的强连通分量是深度优先搜索算法的经典应用之一。

Neo4j

在实现强连通分量算法时在底层要用到深度优先搜索算法。

6.3.1

　何时使用强连通分量算法

强连通分量算法用于在图分析的早期步骤中了解图的构造，或者用于识别可能需要单独研

究的紧密关联簇。对于像推荐引擎这样的应用，强连通分量算法可用于分析群组的相似行

为或趋势。

许多像强连通分量算法这样的社团发现算法用于发现簇，或者将簇分解成单个节点以进行

簇间的分析。也可以使用强连通分量算法来可视化环，以进行如查找死锁进程这样的分

析，出现死锁是因为每个子进程都在等待其他子进程的动作。

示范用例如下。

•

找出每个成员直接或间接拥有其他成员股份的公司集合。

•

在多跳无线网络中测量路由性能时，计算不同网络配置的连通性。可以阅读

Mahesh

K. Marina

和

Samir R. Das

的论文“

Routing Performance in the Presence of Unidirectional

Links in Multihop Wireless Networks

”，了解更多内容。

•

在许多仅对强连通图有效的图算法中充当第一步。在社交网络中，我们发现了许多强连

通的群组，这些群组中的人通常都有相似的偏好，使用强连通分量算法可以查找此类群

组，并向群组中的人推荐其可能喜欢的网页或想购买的产品。

尽管有些算法采用了可避免无限循环的策略，但是在自己编写算法或寻找无

法终止的进程时，也可以使用强连通分量算法来检查环。

6.3.2

　使用

Spark ...