计算“凯文培根”数

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

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

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

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

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

我意识到存在一些问题，例如我可以获得200人左右的链子，但由于我愿意搜索的深度受到限制，可以解决此问题。

这是标准的最短路径问题。有很多解决方案，包括Dijkstra算法和Bellman-

Ford。您可能对查看A

*算法并了解其与成本函数（相对于任何特定节点的度数的倒数）的性能表现特别感兴趣。这个想法将是首先访问更流行的节点（具有较高学位的节点）。