计算＆QUOT;凯文·培根QUOT;号码 [英] Calculating "Kevin Bacon" Numbers

问题描述

我一直在玩弄一些事情，并想出了试图找出的想法凯文·培根号码。我有，为了这个目的，我们可以考虑一个社交网络站点的数据。让我们pretend，它是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），计算出它们之间的最短距离（时间提前，也许），然后尝试使用它们来找到一个链接？而这需要$ P $对计算，它可以使人们有可能搜索许多更少的节点（节点可以是组，而不是个人，使图形小很多）。这仍然是一个双向的搜索，但。

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.

我也pre-计算人的个体连接数，搜索流行的人的第一个节点，因为他们可以在连接到指定目的地个人的最好机会。我知道这将是一个权衡速度的可能的最短路径。我想我也想要用一个深度优先搜索，而不是广度优先搜索我计划在其他情况下使用。

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算法和的贝尔曼 - 福特。您可能会在仰望 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.

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