具有 1 亿个节点的图中的连接组件

我正在尝试获取具有 1 亿个节点的图中的连接组件列表。对于较小的图，我通常使用连接组件 http://networkx.lanl.gov/reference/generated/networkx.algorithms.components.connected.connected_components.html#networkx.algorithms.components.connected.connected_componentsPython 中的 Networkx 模块的功能正是这样做的。然而，使用此模块将具有 1 亿个节点（及其边）的图加载到内存中将需要大约 1 亿个节点（及其边）。 110GB内存，我没有。另一种方法是使用具有连接组件功能的图形数据库，但我在 Python 中没有找到任何功能。 Dex（API：Java、.NET、C++）似乎具有此功能，但我不能 100% 确定。理想情况下，我正在寻找 Python 中的解决方案。非常感谢。

SciPy 有一个连通分量算法 http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.connected_components.html。它期望将图的邻接矩阵作为输入之一稀疏矩阵格式 http://docs.scipy.org/doc/scipy/reference/sparse.html并处理有指导和无指导的情况。

从序列构建稀疏邻接矩阵(i, j) pairs adj_list where i and j节点的（从零开始的）索引可以通过以下方式完成

i_indices, j_indices = zip(*adj_list)
adj_matrix = scipy.sparse.coo_matrix((np.ones(number_of_nodes),
                                     (i_indices, j_indices)))

对于无向情况，您必须做一些额外的工作。

如果你的图足够稀疏，这种方法应该是有效的。