计算两个用户之间的社会距离 [英] Compute social distance between two users

问题描述

您将如何code的高效算法可以返回两个用户之间的社会距离。

How you would code an efficient algorithm which can return a social 'distance' between two users.

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

For example, when you visit a profile on LinkedIn you can see what is the distance between you and the user.

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

-> user A is friend with user B - and B is friend with C. when A will visit C (the distance will be 1)

图形是巨大的，所以我不知道如何将它进行得这么快。

The graph is huge and so I'm wondering how it can be perform so fast.

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

推荐答案

假设你没有任何启发式关于到目标的距离函数时，最好的解决方案，是有效的是双向 BFS ：
算法思路：同时做一个BFS搜索从源和目标：[BFS直到深度为1两，直到深度2两，...]。 维基，算法将结束，当你发现一个顶点v，这是两个BFS的面前。

assuming you don't have any heuristic function about the distance to the target, the best solution that is valid is bi-directional BFS:
Algorithm idea: do a BFS search simultaneously from the source and the target: [BFS until depth 1 in both, until depth 2 in both, ....].
The algorithm will end when you find a vertex v, which is in both BFS's front.

<强>算法行为：该顶点v终止该算法的运行将完全在源和目标之间的中间。
该算法将产生更好的结果，在大多数情况下，那么BFS从源头[解释为什么它是更好然后BFS说明]，必将提供一个答案，如果存在。

Algorithm behavior: The vertex v that terminates the algorithm's run will be exactly in the middle between the source and the target.
This algorithm will yield much better result in most cases then BFS from the source [explanation why it is better then BFS follows], and will surely provide an answer, if one exist.

为什么会优于BFS从源头？
假设源到目标之间的距离 K ，分支系数 B [每个顶点带B边缘。
BFS将打开： 1 + B + B ^ 2 + ... + B ^氏/ code>顶点。
双向BFS将打开： 2 + 2B + 2B ^ 2 + 2B ^ 3 + ... + 2B ^（K / 2）顶点

why is it better then BFS from the source?
assume the distance between source to target is k, and the branch factor is B [every vertex has B edges].
BFS will open: 1 + B + B^2 + ... + B^k vertices.
bi-directional BFS will open: 2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) vertices.

有大B和k，二是明显比第一好得多。

for large B and k, the second is obviously much better than the first.

编辑：
请注意，这种解决方案并不需要存储在内存中的整个图，只需要实现的功能：的继任者（V）返回一个顶点的所有后继者[所有的顶点，你可以得到，在从V 1步。有了这个，你只打开节点[ 2 + 2B + ... + 2B ^（K / 2）如上所述]应保存。为了进一步节省存储空间，你可以用它代替BFS 迭代深化DFS 从一个方向，但它会消耗更多的时间。

NOTE, that this solution does NOT require storing the whole graph in memory, it only requires implementing a function: successor(v) which returns all the successors of a vertex [all vertices you can get to, within 1 step from v]. With this, only the nodes you open [2 + 2B + ... + 2B^(k/2) as explained above] should be stored. To further save memory, you can use Iterative Deepening DFS from one direction, instead of BFS, but it will consume more time.

这篇关于计算两个用户之间的社会距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！