有一个包含1亿个节点的图，如何找到其中所有的连通分量？

Question

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

- David M.

---

你的图有多密集？平均顶点度数是多少？ - NPE

这个图是有向的吗？如果是的话，你是在寻找强连通分量还是连通分量？另外 - 我假设你正在寻找极大的[强]连通分量，而不是所有的（因为它们的数量是指数级别的）- 这是正确的吗？ - amit

@aix：该图平均每个顶点/节点有1.5个。 - David M.

@amit：这个图是无向的。我正在寻找一种方法来获取连接组件的列表，就像networkx.connected_components一样，但规模更大。 - David M.

Answer 1

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)))

你需要为无向图做一些额外的工作。

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

- Fred Foo

---

我的图形非常稀疏，但这个解决方案仅适用于（相对）小的图形，因为scipy.sparse.csgraph.connected_components的时间惩罚不是线性的。在我的测试中，处理10,000个节点需要0.4秒；100,000个节点需要30秒，而处理1百万个节点需要51分钟（然后我停止测试）。无论如何感谢您提出这个有趣的方法。 - David M.

@user1453508：这很奇怪。我检查了代码，乍一看它似乎应该是线性的，当|E|=O(|V|)时。我必须承认我的图形倾向于更小一些。也许你应该开始寻找MapReduce解决方案来解决你的问题。 - Fred Foo

以防我误解了什么，这是我的代码：i_indices = []; j_indices = []; file = open ('adjacency_file.txt', 'r'); for line in iter(file): i_index, j_index = line.strip('\n').split('\t'); i_indices.append(i_index); j_indices.append(j_index); file.close(); adjacency_matrix = scipy.sparse.coo_matrix((np.ones(len(i_indices)),(i_indices, j_indices)), shape=(10000,10000)); connected_components = scipy.sparse.csgraph.connected_components(adjacency_matrix, directed=False) - David M.

最初我的节点是由10位数字组成的，我已将它们转换为从0到10000的索引，并存储到adjacency_file.txt中（例如，如果节点5链接到节点22，则文件将包含行5[tab]22[\n]）。这样做正确吗？ - David M.

我终于成功地使用并查集算法（例如在此处描述的算法）找到了连通组件。我用Python编写了该算法，但如果需要Hadoop，我可以使用Mr Job（http://packages.python.org/mrjob/writing-and-running.html）。 - David M.

Answer 2

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

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

如果这个工具对您来说不够好（我认为它足够好了），那么您可以尝试Apache Giraph (http://giraph.apache.org/)。

- george