python - 查找彼此相距 2 到 3 跳的节点对

Question

我有一个包含大约 50,000 个节点和 2,000,000 条边的大图。我需要找到彼此相距 2 到 3 跳的所有节点对。

最简单（也是肮脏）的解决方案是首先创建组合扩展，然后检查每对节点：

import networkx as nx
import itertools

g = nx.erdos_renyi_graph(n=5000, p=0.05)
L = list(G.nodes())
# Create a complete graph
G = nx.Graph()
G.add_nodes_from(L)
G.add_edges_from(itertools.combinations(L, 2))

但是，当我尝试创建一个包含 45,000 个节点和 200 万条边的完整图时，内存不足。

是否有任何其他解决方案可以在合理的时间内检查大图？感谢您的任何建议或指示。

标签： pythonnetworkxgraph-theory

Answer 1

获取您的边缘列表并将其转换为邻接矩阵，请参阅此处的答案以了解如何使用scipy.sparse. 然后使用numpy.linalg.matrix_power将邻接矩阵提高到 2 次方。对于方阵中的每个条目，如果条目不为零，则节点之间存在长度为 2 的路径（实际上，该条目为您提供节点之间长度为 2 的路径数）。在这里查看答案：

邻接矩阵的幂是连接游走。邻接矩阵的 th 次方的ijth 项告诉您从 vertex到 vertexk的长度步行数。kij

您可以对长度为 3 的路径执行相同的操作，方法是将其提高到 3 次方。