EdgeRank:给社交网站的新鲜事排个序

社交网站比较知名的有两个,一个是不存在的网站叫facebook,一个是国内的山寨网站叫人人。社交网站首页就是一个个新鲜事,在除了时间顺序的情况下,如何更智能的排序呢?

那个不存在的网站facebook分享过他们的智能排序算法,叫EdgeRank…

这是个很不错的算法,借助它的思想,通过简单的改进优化,就可以适应很多场景。人人的智能排序很有可能用的这个,再比如知乎首页也是用这个。

首先基于一个基本的图结构思想,社交网络的关系是一个巨大的图,你的好友发了个状态、评论了别人的状态,传了张图片,圈了个人,加了个新的好友或者参加一个活动都会产生一条“边”。给每个边计算一个值,最后排个序。当你登录社交网络的时候,这些排好序的边,组成了你首页的好友新鲜事~

一个很简单的公式如下:

\sum_{\mathrm{edges\,}e} u_e w_e d_e

其中包含三项:

  1. u表示两个点之间关系的得分
  2. w表示该关系类型的权重
  3. d表示时间延迟

对于每一项:

  • u针对关联性打分,表示了该用户和该新鲜事的关联程度,该值是由历史数据影响的。对于一个edge,针对edge连接的两个用户考虑以下几点历史数据:
    • 首先是本人的操作行为,包括点击、点赞、评论、收藏、分享,各种行为都有各自的权重,这个权重表现的意义就是该新鲜事被用户感兴趣的程度。比如评论可能代表的感兴趣程度比点赞更高,同时点击表示的感兴趣程度最低。
    • 其次,其他人的操作行为也会影响这个分值。比如某条新鲜事,你的n个好友点了赞,可能表示你也会喜欢这条。当然,你也可以把好友的好友也考虑进去,不过这个情况权重会低很多。
    • 时间关联。从理论上讲就是你过去和某人交互很多,而现在交互很少,那么他的新状态,你可能感兴趣的程度会降低。比如,小情侣分手了,咱们还是智能的帮他们屏蔽下状态吧…
    • 最后,这个u是单向的,用户A到B的u和B到A的u显然是不一样的。
  • w对每个关系类型给出一个权重。几个简单的例子就是评论的权重大于点赞,图片或视频状态的权重大于链接分享。这里还可以有一些小优化,比如最近开发了新功能叫电影打分,在一段时间内,我们就可以把这类打分新鲜事的权重提高,促进新功能的推广。过一段时间以后,在调回正常值。
  • d表示时间延迟性,很直观的想法就是,旧的信息靠后排。时间增长,d减小。

除了上面这个公式,参考一些知名的社交网站,新鲜事排序还会做这样类似的功能:

  • 类似状态整合,比如好多人分享同一件事可以把他们合并起来
  • 热门主题分析,通过语料库和机器学习的办法,把头条找出来,排在新鲜事的前面
  • 增加随机因子,如果有好友过于活跃的话,很有可能你就会被他刷屏了,这当然是不想看到的事,所以提供一个随机因子,适时降低活跃好友部分状态的排名。(知乎好像一直就有这个问题,总是被大号刷屏,不过现在好多了)

最后简单说说工程上我的看法。

虽然这个算法确定了以后实现很简单,但是其实还是很难做的。从前面的分析可以看出,首先这是个图论问题,其次这是个实时性问题。说白了对于海量数据的社交网络来说,就是要解决一个实时大规模图计算的问题。

这方面暂时我还不是很懂,图计算其实就是矩阵运算,我觉得突破点可能就是把大规模的图更新规约到局部更新的增量处理模型来考虑吧,同时还要设计好分布式的算法。(谷歌有个Pregel好像和图计算相关,没仔细看过)

Tags : ,

0 thoughts on “EdgeRank:给社交网站的新鲜事排个序”

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Click the right image To submit your comment: