algorithm - 核外连通分量算法

Question

无向图有 4,000,000,000(四十亿)条边。它们在一个大文本文件中表示为成对的节点 ID。我想计算这个图的连通分量。不幸的是，一旦您将带有边缘的节点 ID 加载到内存中，这将占用超过我可用的 128GB RAM。

是否有一种用于查找连接组件且实现起来相对简单的非核心算法？或者更好的是，它可以与 Unix 命令工具和现有的 (python) 库拼凑在一起吗？

Answer 1

根据您提供的问题描述和您在评论中提供的答案，我认为最简单的方法可能是使用@dreamzor 描述的方法。这是该答案的更充实的版本。

基本思想是将数据转换为更适合内存的压缩格式，对该数据运行常规连通分量算法，然后将其解压缩。请注意，如果您为每个节点分配一个 32 位数字 ID，那么存储所有节点所需的总空间最多为 40 亿个节点和 80 亿条边(假设您存储每条边的两个副本)的空间，即120 亿个 32 位整数的空间，只有大约 48GB 的​​空间，低于您的内存阈值。

首先，编写一个读取边文件的脚本，为每个节点分配一个数字 ID(可能按它们出现的顺序依次分配)。让此脚本将此映射写入一个文件，然后写入一个新的边缘文件，该文件使用节点的数字 ID 而不是字符串名称。完成后，您将拥有一个将 ID 映射到名称的名称文件和一个比以前占用更少空间的边缘文件。你在评论中提到你可以将所有节点名称放入内存，所以这一步应该是非常合理的。请注意，您不需要将所有边都存储在内存中 - 您可以通过程序流式传输它们 - 所以这不应该成为瓶颈。

接下来，编写一个程序，将边文件(而不是名称文件)读取到内存中，并使用任何合理的算法(BFS 或 DFS 在这里会很好)找到连接的组件。如果您小心使用您的内存(在这里使用 C 或 C++ 之类的东西会是一个很好的选择)，这应该很适合主内存。完成后，通过数字 ID 将所有簇写入外部文件。您现在有一个按 ID 列出的所有 CC。

最后，编写一个程序，从名称文件中读取 ID 到节点的映射，然后流入集群 ID，并将每个集群中所有节点的名称写入最终文件。

这种方法实现起来应该相对简单，因为关键思想是保留您习惯的现有算法，但只需更改图形的表示形式以提高内存效率。过去，我在处理巨大的图形时使用过类似的方法 (Wikipedia)，即使在内存比您少的系统上，它也能很好地工作。