代码之家 › 专栏 › 技术社区 › MBCook

计算“凯文·培根”数

kevin-bacon graph algorithm

MBCook · 技术社区 · 16 年前

Kevin Bacon 数字。我有一个网站的数据,为此我们可以考虑一个社交网络。让我们假设它是Facebook(为了简化讨论)。我有人,我有他们朋友的名单,所以我有他们之间的联系。我如何计算从一个人到另一个人的距离(基本上是凯文·培根数)?

我最好的主意是 Bidirectional search

制作一些小的子图(比如相当于Facebook上的群组),计算它们之间的最短距离(也许提前计算),然后尝试使用这些子图来查找链接,这样会更好吗?虽然这需要预先计算,但它可以搜索更少的节点(节点可以是组而不是个体,使图形更小)。不过,这仍然是一个双向搜索。

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

有人能想出一种更简单/更快的方法吗?我希望能够在两个人之间找到最短的长度,所以这不像总是有相同的终点那么容易(比如凯文·培根问题)。

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

4 回复 | 直到 9 年前

tvanfosson 16 年前

这是一个标准 shortest path problem . 有很多解决方案,包括 Dijkstra's algorithm Bellman-Ford . 您可能对查看 A* algorithm 看看它将如何执行与任何特定节点度的倒数相关的代价函数。我们的想法是首先访问更受欢迎的节点(那些拥有更高学位的节点)。

Adam Jaskiewicz 16 年前

听起来像是一份工作 Dijkstra's algorithm .

艾德:呃,我不该这么快扣动扳机。当权重为1时,Dijkstra(和Bellman Ford)的搜索减少为广度优先搜索,因此这不太有用。哦,好吧。

A* algorithm tvanfosson提到的,可能是这方面的理想选择。其思想是,不必按照元素在树的每一层(基于起点或终点)的任何顺序进行搜索和递归,而是使用一些启发式方法来确定要首先尝试的元素。在您的情况下,一个好的赌注可能是节点的度数(“朋友”的数量),但您可能希望使用给定人员任意度数范围内的人数(也就是说,一个有三个朋友,每个朋友都有100个朋友的人可能比一个有20个朋友的人在一个避开外人的小圈子里更容易成为一个节点)。你可以用其他各种东西作为启发(朋友得2分,朋友的朋友得1分;不管怎样,实验)。

结合这一点和深度限制(在6度间隔后切断,或其他),你可以大大改善你的平均情况(最坏情况仍然与基本BFS相同)。

Steven A. Lowe 16 年前

sfossen 16 年前

总的来说,这个可能更好 Floyd-Warshall 所有对的最短距离。