使用igraph高效计算23000000节点图的最短路径数量

Question

我正在尝试计算在一个稀疏图中，两个节点之间的最短路径数量。这个图有23000000个节点，边的数量大约是9乘以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的路径数量。