朋友建议或第二学位相关(linkedin)算法如何工作

Question

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

我认为Facebook的建议还基于个人知识,如学年,我工作的公司或类似的东西.

但除此之外,更具体的是该计划

Case1看起来很简单,但是当朋友数量变大(事件大约300个朋友太多)时效率不高.Case2怎么样？什么样的算法可以做这项工作.

我对Case3一无所知,因为我猜它是facebook的特别之处.但我怎么能发现人4.与哪个学位有关？

Answer 1

我不确定你是在询问如何提出建议或检测朋友距离.提出建议很容易,但往往会大小爆炸.

前两种情况可以用同一算法覆盖,第三种情况可以用小扩展覆盖.

前两个基本上是寻找你知道的朋友相互了解的所有人:

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中,朋友1和2之间的链接可能是一个额外的约束,实际上会使案例实现起来有点复杂.通过要求朋友1和2拥有链接,您需要在迭代朋友对时检测潜在的朋友,而不是在最后一次.

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)

当然可以添加一些可以跳过重复比较的优化.实际上,这可能不是一个有用的搜索.你所要做的就是排除两个不同朋友群体共同的潜在朋友.

最后一个案例通过将朋友建议扩展到已知朋友共同朋友的所有朋友来修改第一个伪代码段:

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

正如Neil Knight评论的那样,您可以过滤每个朋友列表,然后首先查看最活跃的朋友.或者计算一个相似度分数,以促进那些拥有更多朋友的朋友.

如果您实际上正在考虑检测朋友和建议之间的距离,这可能与此无关.