4

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

4

2 回答 2

7

SciPy 有一个连通分量算法。它期望您的图形的邻接矩阵以其一种稀疏矩阵格式作为输入，并处理有向和无向情况。

从一系列(i, j)对中构建稀疏邻接矩阵，adj_list其中i和j是（从零开始的）节点索引可以通过

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

您必须为无向案例做一些额外的工作。

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

于 2012-06-13T13:54:55.817 回答
3

https://graph-tool.skewed.de/performance

从性能上可以看出，这个工具非常快。它是用 C++ 编写的，但接口是用 Python 编写的。

如果这个工具对你来说不够好。（我认为会的）然后您可以尝试 Apache Giraph（http://giraph.apache.org/）。

于 2015-07-31T00:56:07.760 回答