python - 使用 igraph 高效计算具有 23000000 个节点的图的最短路径数

Question

我正在尝试计算稀疏图中彼此距离为 2 的 2 个节点之间的最短路径数，该稀疏图中包含 23000000 个顶点和大约 9 X 23000000 条边。现在我正在使用

for v,d,parent in graph.bfsiter(source.index, advanced=True):
        if (0 < d < 3):

循环遍历源节点距离2内的节点(我需要距离1内的节点，但不需要计算它们的所有最短路径)。然后我使用:

len (graph.get_all_shortest_paths(source,v));

获取从源到 v 的所有最短路径的数量(其中 v 是 bfsiter 给我的节点，它距源的最短距离为 2)。

但是这花费的时间太长了。例如，对于上述图表，计算每个(源，v)的最短距离大约需要 1 秒。

我想知道是否有人可以建议一种更有效的方法来使用 igraph 计算所有最短路径的数量

Answer 1

这是评论中建议的答案的实现。该代码最耗时的部分是图形生成。在已经生成的/内存中的图表上运行只需很少的时间。

from igraph import *
import random

# Generate a graph
numnodes = int(1e6)
thegraph = Graph.GRG(numnodes, 0.003)

print("Graph Generated")

# Choose one node randomly and another a distance of 2 away
node1 = random.randint(0, numnodes-1)
node2 = random.sample(set(Graph.neighborhood(thegraph, node1, 2)).difference(
                      set(Graph.neighborhood(thegraph, node1, 1))),1)[0]

# Find the number of nodes in the intersection of the neighborhood
# of order 1.
result = len(set(Graph.neighbors(thegraph, node1)).intersection(
    Graph.neighbors(thegraph, node2)))

print(result)

两个邻域的交集是唯一路径的数量。长度为 2 的路径访问 3 个节点。由于我们知道起点和终点，唯一可能变化的是中间点。由于中间节点与两个端点的距离必须为 1，因此唯一中间点的数量就是节点之间长度为 2 的路径的数量。