algorithm - 计算“凯文培根”数字

Question

我一直在玩一些东西，并想出了试图找出凯文培根数字的想法。我有一个网站的数据，为此我们可以考虑一个社交网络。让我们假设它是 Facebook（为了简化讨论）。我有人，我有他们朋友的名单，所以我有他们之间的联系。如何计算一个人到另一个人的距离（基本上是凯文培根数）？

我最好的想法是具有深度限制的双向搜索（以限制计算复杂性并避免在图中根本无法连接的人的问题），但我意识到这是相当蛮力的。

制作小的子图（比如 Facebook 上的群组），计算它们之间的最短距离（也许是提前），然后尝试使用 THOSE 来查找链接会更好吗？虽然这需要预先计算，但它可以搜索更少的节点（节点可以是组而不是个人，使图更小）。不过，这仍然是双向搜索。

我还可以预先计算个人连接的人数，首先在节点中搜索“受欢迎”的人，因为他们最有可能连接到给定的目标个人。我意识到这将是可能的最短路径的速度权衡。我想我还想使用深度优先搜索，而不是我计划在其他情况下使用的广度优先搜索。

有人能想出一种更简单/更快的方法吗？我希望能够找到两个人之间的最短距离，所以这并不像总是有相同的终点那么容易（例如在凯文培根问题中）。

我意识到有一些问题，比如我可以得到 200 人的连锁店之类的，但这可以解决我对我愿意搜索的深度的限制。

Answer 1

这是一个标准的最短路径问题。有很多解决方案，包括Dijkstra 算法和Bellman-Ford。您可能特别有兴趣查看A* 算法，并了解它如何使用成本函数相对于任何特定节点的度数的倒数执行。这个想法是首先访问更流行的节点（那些具有更高程度的节点）。

Answer 2

听起来像是 Dijkstra 算法的工作。

ED：呃，我不应该这么快扣动扳机。当权重为 1 时，Dijkstra（和 Bellman-Ford）简化为广度优先搜索，因此这不是太有用。那好吧。

tvanfosson 提到的A* 算法可能是理想的选择。这个想法是，不是以任何顺序搜索和递归树的每个级别中的元素（根植于您的起点或终点），而是使用一些启发式方法来确定您将首先尝试哪个元素。在您的情况下，一个不错的选择可能是节点的度数（“朋友”的数量），但您可能希望使用给定人的任意度数内的人数（即拥有有 3 个朋友，每个人有 100 个朋友，这可能比在一个避开外人的小圈子里有 20 个朋友的人更好）。还有各种其他的东西可以用作启发式（朋友得到 2 分，朋友的朋友得到 1 分；无论如何，实验）。

将此与深度限制相结合（在 6 度分离后切断，或其他），您可以大大改善您的平均情况（最坏情况仍然与基本 BFS 相同）。

Answer 3

在两个方向（从每个端点）运行广度优先搜索，并在有连接或达到深度限制时停止

Answer 4

这可能是更好的整体Floyd-Warshall所有对最短距离。