计算“凯文培根"数字 [英] Calculating "Kevin Bacon" Numbers

问题描述

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

I've been playing around with some things and thought up the idea of trying to figure out Kevin Bacon numbers. I have data for a site that for this purpose we can consider a social network. Let's pretend that it's Facebook (for simplification of discussion). I have people and I have a list of their friends, so I have the connections between them. How can I calculate the distance from one person to another (basically, a Kevin Bacon number)?

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

My best idea is a Bidirectional search, with a depth limit (to limit computational complexity and avoid the problem of people who simply can't be connected in the graph), but I realize this is rather brute force.

制作小子图(比如类似于 Facebook 上的群组)，计算它们之间的最短距离(可能提前)，然后尝试使用 THOSE 来查找链接会更好吗?虽然这需要预先计算，但它可以使搜索更少的节点成为可能(节点可以是组而不是个人，从而使图更小).尽管如此，这仍然是一个双向搜索.

Could it be better to make little sub-graphs (say something equivalent to groups on Facebook), calculate the shortest distances between them (ahead of time, perhaps) and then try to use THOSE to find a link? While this requires pre-calculation, it could make it possible to search many fewer nodes (nodes could be groups instead of individuals, making the graph much smaller). This would still be a bidirectional search though.

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

I could also pre-calculate the number of people an individual is connected to, searching the nodes for "popular" people first since they could have the best chance of connecting to the given destination individual. I realize this would be a trade-off of speed for possible shortest path. I'd think I'd also want to use a depth-first search instead of the breadth-first search I'd plan to use in the other cases.

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

Can someone think of a simpler/faster way of doing this? I'd like to be able to find the shortest length between two people, so it's not as easy as always having the same end point (such as in the Kevin Bacon problem).

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

I realize that there are problems like I could get chains of 200 people and such, but that can be solved my having a limit to the depth I'm willing to search.

推荐答案

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

This is a standard shortest path problem. There are lots of solutions, including Dijkstra's algorithm and Bellman-Ford. You may be particularly interested in looking at the A* algorithm and seeing how it would perform with the cost function relative to the inverse of any particular node's degree. The idea would be to visit more popular nodes (those with higher degree) first.

这篇关于计算“凯文培根"数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！