+1千万节点图中两个节点之间的最短路径

Question

我有自己的知识图表示，从ConceptNet和NELL中读取，包含数千万个节点，其中我想计算两个概念节点之间的最近距离(如果有的话)。应用程序将以最简单、可解释的方式了解两个概念是如何关联的。图的典型连通性在100-1000之间.在这种情况下，我需要一些Dijkstras的变体吗？我希望这个解决方案最多需要10 GBytes的内存。我目前的内存使用量约为2GB。

Answer 1

2立即产生的简单解决办法：

通过类似Johnson的算法预先计算所有内容，或者按照您的建议每次使用标准搜索算法-例如Dijkstra (这可以归结为简单的BFS，因为该图没有加权)。

第一种方法需要太多的存储/RAM来完成。第二是速度慢得令人望而却步。您(可能)需要的是一种混合解决方案，它结合了一些预计算(可能是长的，但不需要太多的存储)，以及更短的每次查询计算。

聚类

一种方法是以某种方式对图进行聚类，并计算出簇的出口顶点之间的距离。然后搜索算法甚至不会考虑集群中的路径(或者使用预先计算好的出口之间的最小路径)，除非该集群包含起始点或结束点。

A星

另一种方法是计算启发式，并使用A* (或任何其他启发式辅助搜索)。您提到过，除了连通性之外，您没有任何关于图的信息，所以您可能需要设计和预先计算这样的启发式。

一个这样的启发可能是一个极小的“阶n生成图”。这可能有一个恰当的术语，但我的大学时代已经太久了，所以我要解释一下我的意思。我称一个“阶n生成图”为顶点集合，这样，原始图中的任何顶点都可以通过长度最多为n的路径从集合中的某个顶点到达。

如果您拥有这样的集合，以及Vertex -> closest vertex in spanning graph + distance to it的映射，以及生成图中任意两个点之间的距离，那么您就有了一个启发式：

两个顶点之间的距离至少是生成树中它们最近的顶点之间的距离+到它们的距离- 2*n。(为什么？因为生成顶点之间的距离最多是A到B+之间的距离)。

这是一个可接受的启发，因此A*将做一个很好的使用它。

集合的顺序越小，启发式越好，搜索速度也越快。但这也意味着生成图会更大，因此你需要一个更大的距离矩阵。我可能会从50级左右的图表开始，但您可以根据图形的确切形状/性质来调整它。

为平均用例优化

同样值得注意的是，您可以对您所拥有的图形进行优化，但可以对您回答的查询进行优化。如果它们通常要计算精确但较小的距离，则可能需要预先计算一些值，但不是所有值(例如，从每个节点到任何可通过3个或更少步骤到达的距离？)。在本例中，您需要回过头来使用上述方法之一，但这可能就足够了。

这也引出了一个问题:对于你来说，在更长的路径上是否真的需要完全精确？也许规范在这个意义上可以放宽？