php - friend 建议或二级相关(linkedin)算法是如何工作的

Question

我一直在考虑facebook的建议和其他类似的linkedin系统。

我认为 Facebook 的建议也基于个人知识，例如学年、我工作的公司或类似的东西。

但除此之外，更具体的是这里的方案

案例 1 看起来很简单，但是当 friend 数量增加时(大约 300 个 friend 太多的事件)，它就没有效率了。案例2呢？什么样的算法可以完成这项工作。

我不知道 Case3，因为我猜它对 Facebook 来说很特别。但是我怎么能检测到人 4. 是哪个学位相关的？

Answer 1

我不确定您是在问如何提出建议或检测好友距离。提出建议很容易，但往往会激增。

前两种情况可以用相同的算法来解决，第三种情况可以通过一个小的扩展来解决。

前两个基本上是寻找所有你认识的 friend 相互认识的人:

FriendHash = {}
foreach Friend in me.getFriends()
    foreach FriendOfFriend in Friend.getFriends()
        FriendHash{FriendOfFriend} += 1

foreach PotentialFriend in keys FriendHash
    if FriendHash{PotentialFriend} > 1
        me.suggestFriend(PotentialFriend)

在案例 1 中， friend 1 和 friend 2 之间的联系可能是一个额外的约束，实际上会使案例的实现变得有点复杂。通过要求 friend 1 和 2 有一个链接，您需要在迭代 friend 对时检测潜在的 friend ，而不是在最后一次。

foreach Friend in me.getFriends()
    foreach SecondFriend in me.getFriends()
        # skip already processed friends and Friend == SecondFriend
        if Friend.getFriends() contains SecondFriend
            foreach FriendOfFriend in Friend.getFriends()
                # skip already suggested friends
                if SecondFriend.getFriends() contains FriendOfFriend
                    me.suggestFriend(PotentialFriend)

当然可以在其中添加一些优化，从而跳过重复比较。在实践中，无论如何这可能不是一个有用的搜索。您要做的就是排除两个不同 friend 组共有的潜在 friend 。

最后一个案例修改了第一个伪代码段，将一个好友推荐扩展到所有你认识的好友的共同好友的好友:

foreach PotentialFriend in keys FriendHash
    if FriendHash{PotentialFriend} > 1
        foreach ExtendedFriend in PotentialFriend.getFriends()
            me.suggestFriend(ExtendedFriend)

正如 Neil Knight 评论的那样，您可以过滤每个 friend 列表，首先查看最活跃的 friend 。或者计算一个相似度分数，以提升那些与您有更多共同 friend 的 friend 。

如果您实际上是在检测 friend 和建议之间的距离，这可能不相关。