好友推荐算法

某天与国外友人 X 聊起了好友推荐算法,那么好友推荐是如何完成的呢?

三元闭包

事实上解决这类问题有个专门的理论:三元闭包

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

我们可以用无向图来表示这个社交圈,图上的点即为每个人。如果对于A、B两点,它们之间存在一个连线,那么A与B则为好友。

邻里重叠度

我们可以用邻里重叠度来定量表示 A、B 之间联系的强弱,它在数值上等于:A与B的共同好友数 / A与B的好友总数

我们可以通过对邻里重叠度的排序,找出最高邻里重叠度且非好友的两人,并向他们推荐对方。

脸书是如何做的

脸书结合经验:

  1. 通过时间对这个重叠度进行加权。认识更晚的好友的权重更高,因为他代表了目前的兴趣取向或亲密关系。
  2. 通过共同好友的好友数对这个重叠度进行加权。共同好友中,好友数少的权重更高,因为这样更有可能联通两个不同的连通分量(也就是两个本不连通的社交圈)。