使用 Python 在 CPU/GPU 上加速图论和复杂网络算法的有效方法？
Efficient way to speeding up graph theory and complex network algorithms on CPU/GPU using Python?
P.S.: 我已经提到了我的问题的可能解决方案，但对它们有很多困惑，请给我提供建议。另外，如果这个问题不适合本网站，请将我指向正确的网站，我会将问题移到那里。提前致谢。
我需要执行一些重复的图论和复杂的网络算法来分析大约 2000 个没有自环的无向简单图以用于某些研究工作。每个图有大约 40,000 个节点和大约 600,000 个边（本质上使它们成为稀疏图）。
目前，我正在使用 NetworkX 进行分析，目前 运行ning nx.algorithms.cluster.average_clustering(G) 和 nx.average_shortest_path_length(G) 用于 500 个这样的图表，代码是 运行ning 3 天并且只到达了一半。这让我担心我的完整分析会花费大量意想不到的时间。
在详细说明我的问题和我想到的可能解决方案之前，让我先提一下我的计算机配置，因为它可能会帮助您建议最佳方法。我在 Intel i7-9700K 处理器上 运行ning Windows 10，配备 32GB RAM 和一个 Zotac GeForce GTX 1050 Ti OC 版 ZT-P10510B-10L 4GB PCI Express 显卡。
解释我可能的解决方案和我对它们的困惑：
A) 使用带有邻接矩阵的 GPU 作为图形数据结构： 我可以在 GPU 上放置一个邻接矩阵并通过使用 PyCuda 手动编码来执行我的分析 或 Numba 仅使用循环，因为 GPU 无法处理递归。我能搜索到的最近的是 this on Whosebug 但它没有好的解决方案。
我的期望：我希望加速算法，例如所有对最短路径，两个节点之间的所有可能路径，平均聚类，平均最短路径长度和小世界属性等。如果它能显着提高每个图的速度，我的结果可以非常快地实现。
我的困惑：
- 这些图形算法能否在 GPU 中高效编码？
- 哪个更好用？ PyCuda 还是 Numba？
- 是否有任何其他方法可以更有效地在 GPU 上存储图形，因为我的图形是稀疏图形。
- 我是一个普通的 Python 程序员，没有 GPU 编程经验，所以我将不得不使用 PyCuda/Numba 了解和学习 GPU 编程。哪个比较好学？
B) 在 CPU 上并行化程序本身： 我可以使用 Joblib 或任何其他库并行化 运行 我的 CPU 上的程序] 本身。我可以再安排 2-3 台计算机，在这些计算机上我可以 运行 小的独立程序部分，或者每台计算机可以 运行 500 个图表。
我的期望： 我希望通过在计算机之间并行化和划分任务来加速算法。如果GPU方案不行，我可能还有点希望通过这个方法。
我的困惑：
- 还有哪些其他库可以作为 Joblib 的良好替代品？
- 我应该为我的程序分配所有 CPU 个核心（i7 中的 8 个核心）还是使用更少的核心？
C) 除了我可能的解决方案，您对我还有其他建议吗？ 如果有更好更快的解决方案，除了 C/C+ +，你也可以推荐它们，因为如果没有任何效果，我已经在考虑将 C++ 作为后备计划。
进行中更新
在我的社区中对此问题的评论和讨论的不同建议中，这些是我建议探索的要点。
- GraphBLAS
- boost.graph + 带有 python-wrappers
的扩展
- 图形工具
- Spark/达斯克
- PyCuda/ Numba
- 使用 Pytorch 的线性代数方法
我尝试使用 Joblib 在 CPU（使用 n_job=-1）上 运行 100 个图表，CPU 持续达到100°C。处理器在 运行ning 3 小时后跳闸。 - 作为解决方案，我在多台计算机上使用了 75% 的可用内核（因此，如果可用内核为 8 个，我使用的是 6 个内核）并且程序 运行ning 正常。加速也不错。
这是一个广泛但有趣的问题。让我试着回答一下。
2000 undirected simple graphs [...] Each graph has approx 40,000 nodes and approx 600,000 edges
Currently, I am using NetworkX for my analysis and currently running nx.algorithms.cluster.average_clustering(G) and nx.average_shortest_path_length(G)
NetworkX 使用简单的 Python 实现并且未针对性能进行优化。它非常适合原型制作，但如果遇到性能问题，最好使用其他库重写代码。
除了 NetworkX，两个最流行的图形处理库是 igraph and SNAP. Both are written in C and have Python APIs so you get both good single-threaded performance and ease of use. Their parallelism is very limited but this is not a problem in your use case as you have many graphs, rendering your problem embarrassingly parallel. Therefore, as you remarked in the updated question, you can run 6-8 jobs in parallel using e.g. Joblib or even xargs. If you need parallel processing, look into graph-tool，其中还有一个 Python API.
关于您的 NetworkX 算法，我希望 average_shortest_path_length 在所有库中得到合理优化。 average_clustering 算法很棘手，因为它依赖于节点式三角形计数，并且天真的实现需要 O(|E|^2) 时间，而优化实现将在 O(|E|^1.5) 中完成。您的图表足够大，因此这两种成本之间的差异是运行在图表上用几秒钟对算法进行运算与运行对算法进行数小时运算。
“全对最短路径”(APSP) 问题非常耗时，大多数库使用的 Floyd–Warshall algorithm 运行 时间为 O(|V|^3)。我不确定您要使用“两个节点之间的所有可能路径”算法寻找什么输出 - 枚举所有路径会导致结果呈指数级增长，并且在这种规模下是不可行的。
我不会开始使用 GPU 来完成这项任务：Intel i7-9700K 应该适合这项工作。基于 GPU 的图形处理库的设置具有挑战性，目前不提供显着的加速——使用 GPU 代替 CPU 对图形处理的增益远不及对机器学习算法的显着。您可能获得较大加速的唯一问题是 APSP，但这取决于您选择的库使用的算法。
如果您对基于 GPU 的库感兴趣，可以找到有关该主题的有前途的方向，例如 Gunrock, GraphBLAST，以及正在进行的 SuiteSparse:GraphBLAS 支持 CUDA 的扩展。但是，我估计您应该能够 运行 使用一台计算机及其 CPU.
在几个小时内完成大部分算法（APSP 除外）
P.S.: 我已经提到了我的问题的可能解决方案，但对它们有很多困惑，请给我提供建议。另外，如果这个问题不适合本网站，请将我指向正确的网站，我会将问题移到那里。提前致谢。
我需要执行一些重复的图论和复杂的网络算法来分析大约 2000 个没有自环的无向简单图以用于某些研究工作。每个图有大约 40,000 个节点和大约 600,000 个边（本质上使它们成为稀疏图）。
目前，我正在使用 NetworkX 进行分析，目前 运行ning nx.algorithms.cluster.average_clustering(G) 和 nx.average_shortest_path_length(G) 用于 500 个这样的图表，代码是 运行ning 3 天并且只到达了一半。这让我担心我的完整分析会花费大量意想不到的时间。
在详细说明我的问题和我想到的可能解决方案之前，让我先提一下我的计算机配置，因为它可能会帮助您建议最佳方法。我在 Intel i7-9700K 处理器上 运行ning Windows 10，配备 32GB RAM 和一个 Zotac GeForce GTX 1050 Ti OC 版 ZT-P10510B-10L 4GB PCI Express 显卡。
解释我可能的解决方案和我对它们的困惑：
A) 使用带有邻接矩阵的 GPU 作为图形数据结构： 我可以在 GPU 上放置一个邻接矩阵并通过使用 PyCuda 手动编码来执行我的分析 或 Numba 仅使用循环，因为 GPU 无法处理递归。我能搜索到的最近的是 this on Whosebug 但它没有好的解决方案。
我的期望：我希望加速算法，例如所有对最短路径，两个节点之间的所有可能路径，平均聚类，平均最短路径长度和小世界属性等。如果它能显着提高每个图的速度，我的结果可以非常快地实现。
我的困惑：
- 这些图形算法能否在 GPU 中高效编码？
- 哪个更好用？ PyCuda 还是 Numba？
- 是否有任何其他方法可以更有效地在 GPU 上存储图形，因为我的图形是稀疏图形。
- 我是一个普通的 Python 程序员，没有 GPU 编程经验，所以我将不得不使用 PyCuda/Numba 了解和学习 GPU 编程。哪个比较好学？
B) 在 CPU 上并行化程序本身： 我可以使用 Joblib 或任何其他库并行化 运行 我的 CPU 上的程序] 本身。我可以再安排 2-3 台计算机，在这些计算机上我可以 运行 小的独立程序部分，或者每台计算机可以 运行 500 个图表。
我的期望： 我希望通过在计算机之间并行化和划分任务来加速算法。如果GPU方案不行，我可能还有点希望通过这个方法。
我的困惑：
- 还有哪些其他库可以作为 Joblib 的良好替代品？
- 我应该为我的程序分配所有 CPU 个核心（i7 中的 8 个核心）还是使用更少的核心？
C) 除了我可能的解决方案，您对我还有其他建议吗？ 如果有更好更快的解决方案，除了 C/C+ +，你也可以推荐它们，因为如果没有任何效果，我已经在考虑将 C++ 作为后备计划。
进行中更新
在我的社区中对此问题的评论和讨论的不同建议中，这些是我建议探索的要点。
- GraphBLAS
- boost.graph + 带有 python-wrappers 的扩展
- 图形工具
- Spark/达斯克
- PyCuda/ Numba
- 使用 Pytorch 的线性代数方法
我尝试使用 Joblib 在 CPU（使用
n_job=-1）上 运行 100 个图表，CPU 持续达到100°C。处理器在 运行ning 3 小时后跳闸。 - 作为解决方案，我在多台计算机上使用了 75% 的可用内核（因此，如果可用内核为 8 个，我使用的是 6 个内核）并且程序 运行ning 正常。加速也不错。
这是一个广泛但有趣的问题。让我试着回答一下。
2000 undirected simple graphs [...] Each graph has approx 40,000 nodes and approx 600,000 edges
Currently, I am using NetworkX for my analysis and currently running
nx.algorithms.cluster.average_clustering(G)andnx.average_shortest_path_length(G)
NetworkX 使用简单的 Python 实现并且未针对性能进行优化。它非常适合原型制作，但如果遇到性能问题，最好使用其他库重写代码。
除了 NetworkX，两个最流行的图形处理库是 igraph and SNAP. Both are written in C and have Python APIs so you get both good single-threaded performance and ease of use. Their parallelism is very limited but this is not a problem in your use case as you have many graphs, rendering your problem embarrassingly parallel. Therefore, as you remarked in the updated question, you can run 6-8 jobs in parallel using e.g. Joblib or even xargs. If you need parallel processing, look into graph-tool，其中还有一个 Python API.
关于您的 NetworkX 算法，我希望 average_shortest_path_length 在所有库中得到合理优化。 average_clustering 算法很棘手，因为它依赖于节点式三角形计数，并且天真的实现需要 O(|E|^2) 时间，而优化实现将在 O(|E|^1.5) 中完成。您的图表足够大，因此这两种成本之间的差异是运行在图表上用几秒钟对算法进行运算与运行对算法进行数小时运算。
“全对最短路径”(APSP) 问题非常耗时，大多数库使用的 Floyd–Warshall algorithm 运行 时间为 O(|V|^3)。我不确定您要使用“两个节点之间的所有可能路径”算法寻找什么输出 - 枚举所有路径会导致结果呈指数级增长，并且在这种规模下是不可行的。
我不会开始使用 GPU 来完成这项任务：Intel i7-9700K 应该适合这项工作。基于 GPU 的图形处理库的设置具有挑战性，目前不提供显着的加速——使用 GPU 代替 CPU 对图形处理的增益远不及对机器学习算法的显着。您可能获得较大加速的唯一问题是 APSP，但这取决于您选择的库使用的算法。
如果您对基于 GPU 的库感兴趣，可以找到有关该主题的有前途的方向，例如 Gunrock, GraphBLAST，以及正在进行的 SuiteSparse:GraphBLAS 支持 CUDA 的扩展。但是，我估计您应该能够 运行 使用一台计算机及其 CPU.
在几个小时内完成大部分算法（APSP 除外）