Python中基于稀疏矩阵的图顶点间路径与游走数高效计算方法

我需要计算图中顶点v1和v2之间的游走数（允许重复访问同一顶点的路径）。
Mark Newman所著《Networks: An Introduction》中提到了一个非常简洁的算法：长度为n的游走数w(v1,v2)等于邻接矩阵A的n次幂中v1行v2列的元素，即w(v1,v2)=A**n [v1,v2]。
但我的图规模极大，仅能以稀疏矩阵形式存储，无法直接计算A的幂次。我尝试使用networkx库，它支持从稀疏矩阵创建图，但仅能找到计算简单路径（不允许重复访问顶点的游走）的方法，且运行速度极慢。
以下是我的测试代码：

import time
import numpy as np
from numpy.linalg import norm
import networkx as nx


# 计算长度不超过4的、顶点0到顶点1的路径/游走数量
len_of_paths=4
pos1=0
pos2=1


# 生成随机邻接矩阵和对应图结构
np.random.seed(6)
rnd_mat=np.random.rand(250,250)
np.fill_diagonal(rnd_mat,0.1)

A = np.floor(rnd_mat+rnd_mat.transpose())
G = nx.from_numpy_matrix(A)


# 用networkx计算所有简单路径
time_start=time.time()
paths_between=list(nx.all_simple_paths(G, source=pos1, target=pos2, cutoff=len_of_paths))
time_end=time.time()

print('NetworkX耗时: ',(time_end-time_start))



# 用矩阵乘法计算所有游走数
# 稀疏矩阵场景下是否无法使用该方法？
time_start=time.time()
Amult=A
accumulated_paths=Amult[pos1,pos2];
for ii in range(len_of_paths-1):
    Amult=np.dot(Amult,A)
    individual_paths=Amult[pos1,pos2]
    accumulated_paths+=individual_paths
    

time_end=time.time()
print('矩阵乘法耗时: ',(time_end-time_start))

print('networkx计算得到的简单路径数: ', len(paths_between))
print('矩阵乘法计算得到的游走数: ', accumulated_paths)

测试输出结果：

NetworkX耗时:  10.66906476020813
矩阵乘法耗时:  0.003000497817993164

可见NetworkX的运行速度远低于矩阵乘法方案。
请问是否有方法可以加速计算或估算图中两顶点间的简单路径或游走数量？

游走数（允许重复顶点）的稀疏矩阵加速方案 #

你不需要计算完整的邻接矩阵幂，因为你只需要v1到v2的结果，用单向量迭代法即可，内存占用和计算量都比全矩阵乘法低几个量级：

• 初始化一个仅v1位置为1、其余位置为0的稀疏行向量x
• 每轮迭代执行x = x @ A（A为稀疏邻接矩阵），迭代k次后x[v2]的值就是长度为k的v1到v2的游走数
• 累加所有符合长度要求的x[v2]即可得到总游走数

用scipy稀疏矩阵实现的话，即使是千万级节点的稀疏图也能轻松运行，速度和你测试的全矩阵乘法相当甚至更快，内存占用仅为全矩阵方案的数百分之一。

简单路径（不允许重复顶点）的加速/估算方案 #

短路径精确计数 #

你之前用networkx.all_simple_paths慢是因为它会把所有符合要求的路径都存储下来，如果你只需要计数不需要具体路径，可以自己实现带剪枝的BFS/DFS：

• 遍历的时候仅记录当前所在节点和已访问节点集合，走到目标节点且路径长度符合要求就直接计数，不需要存储完整路径
• 路径长度不超过10的场景下，这个方法比原生networkx快至少10倍以上。

长路径估算 #

如果路径长度很大、无法做精确遍历，可以用蒙特卡洛采样法估算：

• 从v1出发，每次随机选择相邻节点前进，遇到已经访问过的节点就终止本次采样
• 统计采样中满足「到达v2且路径长度符合要求」的样本占比，乘以总采样数就能得到近似的路径数量，采样量越大精度越高，时间成本完全可控。

内容的提问来源于stack exchange，提问作者Mario Krenn