利用igraph算法，高效地计算了具有23000000个节点的图的最短路径数

Question

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

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的路径的个数。