计算两个用户之间的社交距离

如何编码能够返回两个用户之间的社交“距离”的高效算法。计算两个用户之间的社交距离

例如，当您访问个人资料在LinkedIn上，你可以看到什么是你和用户之间的距离。

- >用户A是朋友与用户B - 和B是朋友与C.当A将访问C（的距离将1）

该图是巨大的，所以我不知道如何将它表现得如此之快。

我知道，这个问题很可能被关闭，但我真的认为这是一个编程/算法的问题 - 因为我很感兴趣这个概念我不会指定任何语言。

来源

2011-08-28 JohnJohnGa

你能否提供一个示例截图和数据或者那些没有LinkedIn的东西？ – Zirak

你是指大圆距离吗？ http://en.wikipedia.org/wiki/Great-circle_distance –

@Zirak你可以看到我的例子，我编辑了帖子 – JohnJohnGa

假设你没有要目标，即有效的最佳解决方案的距离任何heuristic function是bi-directional BFS：
算法想法：从源和目标同时做了BFS搜索：[BFS直到两个深度1，直到两个深度2，....]。
当您找到顶点v时，该算法将结束，该顶点v位于BFS的前面。

算法行为：终止算法运行的顶点v将完全位于源和目标之间的中间。
这个算法在大多数情况下会产生好得多的结果，然后BFS从源头[解释为什么它比BFS更好]，并且肯定会提供一个答案，如果存在的话。

为什么它优于BFS从源头？
假设源到目标之间的距离为k，分支因子是B [每个顶点有乙边缘。
BFS将打开：1 + B + B^2 + ... + B^k顶点。
双向BFS将打开：2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2)顶点。

为大B和K，第二个是明显比第一好得多。

编辑：
注意，这种解决方案并不需要存储在内存中的全图，它只需要的功能实现：successor(v)它返回一个顶点的所有的接班人[所有顶点，你可以去，内1步从v]。由此，应该只存储您打开的节点[2 + 2B + ... + 2B^(k/2)，如上所述]。为了进一步节省内存，您可以从一个方向使用Iterative Deepening DFS而不是BFS，但它会消耗更多时间。

来源

2011-08-28 10:16:57 amit

这也意味着整个图需要在内存中吗？ – JohnJohnGa

@JohnJohnGa：没有。所有你需要的是一个'继承者（v）'函数，它可以返回v的所有后继者[也就是说，你可以得到的所有顶点，在一步之内，从v]。只有打开的节点需要存储在内存中。我会把这个添加到我的答案中。 – amit

接受，非常好的答案 - 这就是为什么我喜欢stackoverflow，我们可以得到答案，包括纯粹algorthmic！ – JohnJohnGa

我会假设这可以通过应用最短路径算法，如breadth first search到graph database来完成。但他们似乎将整个图表存储在内存中，至少根据this。

我确信，该算法最终归结为在图结构（节点和边）某些形式的最短路径之一。

编辑：改变了算法按照意见。

来源

2011-08-28 10:12:04 arunkumar

是的 - 这就是为什么当你有大量的用户 - 我真的不知道它是如何完成[如此快] – JohnJohnGa

为什么Dijkstra的算法如果图不加权？只是BFS我猜:) –

你可以在这个案例中使用Dijkstra，使用weight = 1。但是BFS在这种情况下更好。 –

首先需要填充图形。我不能说你如何从链接中获得图形，可能会创建节点的BFS或DFS，发现图形并建立链接。要找到两者之间的最佳距离，请从源节点创建BFS，并在找到目标时停止。如果你不暗示别的东西，我认为这些链接没有权重。

在这种情况下，当源节点不同时，您需要应用BFS来查找每对之间的距离。否则，您可以实现Floyd Warshall算法来获取所有源所有目的地最短路径，并且因为每个链路具有相同的权重，它将获得您想要的。在这种情况下，一旦建立了结构，对于任何来源和目的地，可以找到最短的距离。一个问题是网络总是在变化，因此需要重新处理。所以BFS我认为会很好。

为了加快处理速度，您可以实现BFS并行运行。看看Design and analysis of a nondeterministic parallel breadth-first search algorithm

来源

2011-08-28 10:22:25 phoxis

计算两个用户之间的社交距离

回答

相关问题