从好友推荐算法说起

社交网络中,好友推荐随处可见,这里探讨好友推荐是如何做的。

1、三元闭包理论

说到好友推荐,就不得不谈三元闭包理论。

三元闭包定义:在一个社交圈内,若两个人有一个共同好友,则这两个人在未来成为好友的可能性就会提高。

举例说明,若B、C有一个共同好友A,且B、C不认识,则B、C成为好友的几率会增加

这个理论直观自然,可以从机会、信任、动机上来解释:

  1. B、C是A的朋友,那么B、C见面的机会会增加,如果A花时间和B、C相处,那么B、C可能会因此有机会认识
  2. 在友谊形成过程中,基于B、C都是A好友的事实,假定B、C都知道这点,这会为他们提供陌生人之间所缺乏的基本信任
  3. A有将B、C撮合为好友的动机:如果B、C不是朋友,可能会为A和B、C的友谊造成潜在的压力

两个人共同好友的多少决定这两个人关系的强弱,基于共同好友的多少,就可以进行好友推荐。

1)共同好友数

从好友推荐算法说起

其中,Neighbor(i)表示i的好友,也就是网络拓扑上的邻居节点

通过对共同好友数排序,即可产生一个好友推荐列表。

2)对双方好友数加权

为消除双方好友数差距,可以除以双方好友数进行加权,也就是杰卡德系数,计算公式如下:

从好友推荐算法说起

3)对共同好友加权

在1)2)中,相当于对每个共同好友一视同仁,都贡献1分,但是共同好友中,有些人好友多,有些好友少,当某个共同好友的好友数较少时,这个共同好友应该更加重要,所以可以通过除以每个共同好友的好友数进行加权。

从好友推荐算法说起

上式中,通过除以每个共同好友的好友数进行加权,如果好友数相差过大,需要通过开方、对数等方式进行处理,如下:

从好友推荐算法说起
从好友推荐算法说起

下面是y=x,y= x^0.5,y=log2x 的曲线:

从好友推荐算法说起

可以看出,使用开方、对数都可以有效消除差值过大的影响。

2、Facebook

Facebook的数据表明:好友关系建立中,拥有10个共同好友是只有1个共同好友的12倍。

从好友推荐算法说起

Facebook在共同好友的基础上,加入了时间维度;

基于一个假设:用户对新添加的好友更感兴趣。如图:f1和f2是用户u的好友,相对于很久之前添加的好友f2,f1是近期添加,用户对f1近期添加的好友更感兴趣。

从好友推荐算法说起

基于这样的假设,Facebook出了一个经验公式,如下:

从好友推荐算法说起

从这个公式可以看到,对比对共同好友加权的公式,增加了时间特征:

从好友推荐算法说起

时间相差越大,权重越小。其中,δ u,fi 为u与fi建立好友关系的时间, δ fi,fof 为fi与fof建立好友关系的时间,-0.3为惩罚因子,是Facebook的一个经验参数,需要根据具体情况进行调整。

下面是x^a的图,可以直观感受下衰减的程度:

从好友推荐算法说起

根据这个经验公式能直接计算出好友推荐的得分,也可以作为一维特征与其他特征一起做回归。

3、其他

一般情况下,使用二度好友(好友的好友)作为推荐的候选集。

假设平均每人有150个好友,差不多有22500个二度好友,数据量基本满足推荐候选集的需求,并且数据表明,绝大部分(92%左右)的好友关系都建立在二度空间。

基于三元闭包理论进行好友推荐,推荐的用户至少有一个共同好友,也变相的确定使用二度好友进行推荐。

来自:知乎专栏 Data Science

本文采用「CC BY-SA 4.0 CN」协议转载自互联网、仅供学习交流,内容版权归原作者所有,如涉作品、版权和其他问题请给「我们」留言处理。

(0)
张乐的头像张乐编辑
上一篇 2016-06-01 23:25
下一篇 2016-06-13

相关文章

  • 如何牛逼地设计电影推荐系统

    摘要:如何牛逼地设计电影推荐系统 个性化 所谓个性化就是系统在对每个用户进行相关引导时,应该考虑改用户的特点,比如他的历史搜索行为中表现出来的特点,比如是喜欢科幻、或者喜欢文艺,在搜索相关内容时,可以根据这些潜在模式去调整内容的顺序。 精准营销和消费者分群 精准营销是通过用户的个人资料和行为数据,训练特定模型去对用户进行群体划分,这类方法使用的数据能够有效地…

    2016-03-12
    0
  • 抖音推荐体系到底有什么奥妙之处?

    抖音推荐体系到底有什么奥妙之处?

    2020-05-11
    1
  • FB数据丑闻后续:50万英镑,英国对其处以数据保护法最高罚款

    据路透社7月11日报道,在被英国数据保护监管机构查出数据共享违反法律之后,Facebook目前面临来自英国信息专员办公室(ICO)的50万英镑(664,000美元)罚款处理。

    2018-07-14
    0
  • 个性化推荐到底是不是个伪命题?

    最近,有一位网友在微博上说,推荐是不是个伪命题连续几天试用了据说很好的某头条,某资讯以及某快报,感觉逃脱不了看什么就是什么的套路。也有人说,这是Exploitation & Exploration出了问题,没有很好得Exploration导致的结果。那么,个性化推荐到底是不是伪命题呢为什么很多推荐系统过了一段时间以后就老是推荐类似的东西呢本篇文章就要…

    2016-04-12
    0
  • 新浪微博算法技术总监姜贵彬:大数据驱动下的微博社会化推荐

    摘要:不同于搜索,“推荐”通常不是独立的互联网产品,而是互联网产品的核心组件,为该产品的核心目标服务,比如电商网站的推荐是为了达成更多商品交易。微博推荐同样如此,其存在价值就是通过梳理和优化用户关系网络、打通内容传播链条、引爆信息定向传播,从而实现加速高价值用户关系构建、优质内容传播和商业化营收等微博核心目标。 明确了推荐的角色和定位后,设计一个合适的推荐系…

    2016-04-03
    0
关注我们
关注我们
分享本页
返回顶部