Networkx：如何从一个巨大的图形中创建关联矩阵
Networkx: How to create the incidence matrix from a huge graph
我正在阅读一个非常大的图表，特别是 wiki-topcats (http://snap.stanford.edu/data/wiki-topcats.html)，虽然我可以在可接受的时间内阅读和创建图表：
graph = nx.read_edgelist("C:/.../wiki-topcats.txt", nodetype=int)
然后我需要提取关联矩阵以创建折线图（这是我的目标），但是当我 运行:
C = nx.incidence_matrix(graph)
我遇到了内存错误，我找不到任何有效的方法来处理这个问题，也找不到通过从邻接创建关联矩阵来解决这个问题的方法，但我必须使用 scipy 矩阵由于图表的大小，例如这个邻接矩阵有效。
A = nx.to_scipy_sparse_matrix(graph)
。任何帮助将不胜感激。
NetworkX 显然不是为计算大图而设计的。它的性能也不是很好（对于内存消耗和速度）。图数据库旨在通过将图存储在存储设备上来解决这个问题。 Neo4j 是 Python 中可用的此类数据库的示例。话虽这么说，您要计算的图形并不是那么大，您可以尝试使用更高效的替代 Python 库，例如 graph-tool.
假设您真的 want/need 使用 NetworkX，那么请注意该图需要大约 12 GiB 的 RAM，并且许多 NetworkX 函数 return 一个完整的图会产生几十 GiB 的 RAM allocated 这完全是一种资源浪费。更何况大多数机器没有那么多内存。图形文件只需要大约 400 MiB，紧凑的表示应该能够以不到 100 MiB 的内存存储在 RAM 中。因此，为此使用 12 GiB 需要比预期多 120 倍以上的资源。更不用说 NetworkX 需要很长时间来填充这样的内存 space.
直接在 稀疏矩阵 中加载文件效率更高，前提是仔细选择了稀疏矩阵类型。事实上，CSR 矩阵可以非常有效地存储邻接矩阵，而 DOK 矩阵非常低效（它需要 6 GiB 的 RAM，并且和 NetworkX 一样慢）。
请注意，np.genfromtxt（旨在加载此类文件）在我的机器上使用 45-50 GiB 的 RAM 会变得疯狂。这太疯狂了，因为它实际上比严格需要的大 200 倍！希望 Pandas 中的 df = pd.read_table('wiki-topcats.txt', dtype=np.int32, header=None, sep=' ') 能够使用不到 400 MiB 加载文件。在此基础上，您可以使用 edges = df.to_numpy() 轻松地将数据帧转换为 Numpy，然后构建一个相对快速的 CSR 矩阵。
请注意，您可以使用 Numpy 直接构建（稀疏 CSR）关联矩阵。一种解决方案是使用 idx = np.arange(len(df), dtype=np.int32) 以便为每条边设置一个 ID。然后，您可以直接知道 1 在稀疏矩阵（m[edges[:,0], idx] 和 m[edges[:,1], idx]）中的所有位置，这应该足以构建它（注意可能由于节点连接而导致的重复）对自己）。
我正在阅读一个非常大的图表，特别是 wiki-topcats (http://snap.stanford.edu/data/wiki-topcats.html)，虽然我可以在可接受的时间内阅读和创建图表：
graph = nx.read_edgelist("C:/.../wiki-topcats.txt", nodetype=int)
然后我需要提取关联矩阵以创建折线图（这是我的目标），但是当我 运行:
C = nx.incidence_matrix(graph)
我遇到了内存错误，我找不到任何有效的方法来处理这个问题，也找不到通过从邻接创建关联矩阵来解决这个问题的方法，但我必须使用 scipy 矩阵由于图表的大小，例如这个邻接矩阵有效。
A = nx.to_scipy_sparse_matrix(graph)
。任何帮助将不胜感激。
NetworkX 显然不是为计算大图而设计的。它的性能也不是很好（对于内存消耗和速度）。图数据库旨在通过将图存储在存储设备上来解决这个问题。 Neo4j 是 Python 中可用的此类数据库的示例。话虽这么说，您要计算的图形并不是那么大，您可以尝试使用更高效的替代 Python 库，例如 graph-tool.
假设您真的 want/need 使用 NetworkX，那么请注意该图需要大约 12 GiB 的 RAM，并且许多 NetworkX 函数 return 一个完整的图会产生几十 GiB 的 RAM allocated 这完全是一种资源浪费。更何况大多数机器没有那么多内存。图形文件只需要大约 400 MiB，紧凑的表示应该能够以不到 100 MiB 的内存存储在 RAM 中。因此，为此使用 12 GiB 需要比预期多 120 倍以上的资源。更不用说 NetworkX 需要很长时间来填充这样的内存 space.
直接在 稀疏矩阵 中加载文件效率更高，前提是仔细选择了稀疏矩阵类型。事实上，CSR 矩阵可以非常有效地存储邻接矩阵，而 DOK 矩阵非常低效（它需要 6 GiB 的 RAM，并且和 NetworkX 一样慢）。
请注意，np.genfromtxt（旨在加载此类文件）在我的机器上使用 45-50 GiB 的 RAM 会变得疯狂。这太疯狂了，因为它实际上比严格需要的大 200 倍！希望 Pandas 中的 df = pd.read_table('wiki-topcats.txt', dtype=np.int32, header=None, sep=' ') 能够使用不到 400 MiB 加载文件。在此基础上，您可以使用 edges = df.to_numpy() 轻松地将数据帧转换为 Numpy，然后构建一个相对快速的 CSR 矩阵。
请注意，您可以使用 Numpy 直接构建（稀疏 CSR）关联矩阵。一种解决方案是使用 idx = np.arange(len(df), dtype=np.int32) 以便为每条边设置一个 ID。然后，您可以直接知道 1 在稀疏矩阵（m[edges[:,0], idx] 和 m[edges[:,1], idx]）中的所有位置，这应该足以构建它（注意可能由于节点连接而导致的重复）对自己）。