计算"凯文培根"数字

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

我最好的想法是双向搜索,具有深度限制(以限制计算复杂性并避免在图中无法连接的人的问题),但我意识到这是相当暴力的.

制作小子图(比如说Facebook上的群组等)可以更好,计算它们之间的最短距离(可能提前),然后尝试使用THOSE来查找链接？虽然这需要预先计算,但它可以搜索更少的节点(节点可以是组而不是个体,使图形更小).尽管如此,这仍然是双向搜索.

我还可以预先计算个人所连接的人数,首先在节点中搜索"热门"人,因为他们最有可能连接到给定的目的地个体.我意识到这将是对可能的最短路径的速度的权衡.我想我也想使用深度优先搜索而不是我计划在其他情况下使用的广度优先搜索.

有人可以想到更简单/更快的方法吗？我希望能够找到两个人之间最短的长度,所以它并不像总是具有相同的终点那么容易(例如在Kevin Bacon问题中).

我意识到有一些问题,比如我可以获得200人的连锁等等,但这可以解决我对我愿意搜索的深度的限制.

这是标准的最短路径问题.有很多解决方案,包括Dijkstra的算法和Bellman-Ford.您可能特别感兴趣的是查看A*算法,并了解它如何使用相对于任何特定节点度的倒数的成本函数执行.想法是首先访问更受欢迎的节点(具有更高学位的节点).