PySpark图计算算法实例

基于pyspark的图计算实例

• 引入
  • 广度优先搜索
  • 连通分量
  • 强连通分量
  • 标签传播
  • PageRank
  • 最短路径算法
  • 三角形计数

引入

图算法是一种借助特定线条进行计算以获得结果的简化方法。无向图、有向图以及网络结构能够应用多种常见的图算法，这些算法涵盖：各类遍历方式（类似于树的遍历操作），用于确定最短路径的算法，寻找网络中成本最低路径的算法，以及解决一些基础性问题（如判断图是否连通、确定两个顶点之间的最短路径等）的相关算法。图算法可广泛应用于多个场景，例如：管道系统的优化、路由表的构建、快递服务的调度以及通信网站的设计等。

GraphFrames 提供了与 GraphX 相同的标准图算法集合，并新增了一些其他算法。
目前，部分算法是通过 GraphX 的 API 实现的，因此在 GraphFrames 中可能并不具备比 GraphX 更具扩展性的功能。

现阶段，我们的业务涉及企业知识图谱领域，需要实现基于图计算的应用，例如路径搜索、社区发现和标签传播等。尽管 Neo4j 也具备相应的能力，但其分布式版本的成本较高。因此我们考虑采用 Spark 来进行分布式图计算。

本文不会深入探讨具体算法细节，而是重点展示官网提供的示例代码及实际案例中的实现方式。