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

Question

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

algorithmlinkedin-api

18

如何编写一个高效的算法，以返回两个用户之间的社交“距离”。

例如，在LinkedIn上访问某个用户的资料时，可以查看您与该用户之间的距离。

-> 用户A是用户B的朋友-B是用户C的朋友。当A访问C时（距离为1）

图表很大，因此我想知道如何快速执行它。

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

- JohnJohnGa

你能提供一个示例截图和数据之类的东西，以便那些没有 LinkedIn 的人参考吗？ - Zirak

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

@Zirak，你可以看到我的示例，我编辑了这篇文章。 - JohnJohnGa

3个回答

2

我本以为这可以通过应用最短路径算法来完成，例如使用广度优先搜索应用于图形数据库中。但是根据this的说法，它们似乎将整个图形存储在内存中。

我相信该算法最终归结为对一个图形结构（节点和边）上的某种形式的最短路径算法。

编辑：根据意见更改了算法。

- arunkumar

没错 - 这就是为什么当你有大量用户时 - 我真的不知道它怎么能够[如此快速]完成。 - JohnJohnGa

1

如果图没有权重，为什么要使用Dijkstra算法？我猜只需要使用BFS :) - Grigor Gevorgyan

你可以使用Dijkstra算法，将权重设置为1来解决这个问题。但是在这种情况下，BFS更好。 - Pedro Montoto García

看一下关于Linkedin架构的最后一个链接。标题为“云”的部分描述了他们如何通过投入大量资金和RAM来使其快速运行。 - arunkumar

0

首先需要填充图形。我无法确定您如何从LinkedIn获取图形，可能是通过节点的BFS或DFS发现图形并建立链接。要找到任意两个最佳之间的距离，可以从源节点开始进行BFS，并在找到目标节点时停止。如果没有其他含义，链接没有权重。

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

为了使处理更快，您可以实现并行运行的BFS。请参阅设计和分析非确定性并行广度优先搜索算法。

- phoxis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

假设您没有任何关于到目标的距离的启发式函数，最好的有效解决方案是双向 BFS：
算法思想:同时从源和目标进行BFS搜索：[在两个中同时进行深度为1的BFS，深度为2的BFS，...]
当您找到一个顶点v在两个BFS的前面时，算法将结束。

算法行为:终止算法运行的顶点v恰好位于源和目标的正中间。
在大多数情况下，此算法的结果要比从源开始的BFS好得多[以下是为什么它比BFS更好的解释]，如果存在答案，则一定会提供答案。

为什么它比BFS更好？
假设源到目标的距离为k，分支因子为B[每个顶点都有B条边]。
BFS将打开：1 + B + B^2 + ... + B^k个顶点。
双向BFS将打开：2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2)个顶点。

对于大的B和k，第二个公式显然比第一个好得多。

编辑：
请注意，此解决方案不需要在内存中存储整个图形，它只需要实现一个函数：successor(v)，该函数返回一个顶点的所有后继节点（从v出发可以在1步内到达的所有顶点）。使用这个方法，只有你打开的节点[如上所述2 + 2B + ... + 2B^(k/2)]应该被存储。为了进一步节省内存，你可以使用迭代加深深度优先搜索从一个方向进行搜索，而不是广度优先搜索，但这将消耗更多时间。