Interactions Rank，挖掘用户的社交图谱

PageRank 是 Google 十年前提出的一种网页评级方法，也是 Google 用来衡量一个网站质量好坏的重要因素。利用 PageRank，Google 不断地改善搜索结果的排序，打造出目前最受欢迎的搜索引擎。相继搜索业的蓬勃发展，互联网领域又出现了一只新秀——社会网络 (SNS)。如今，Facebook 几乎代表了 SNS 的领航者。在 F8 大会上，来自 Facebook 的工程师介绍了关于 news feed 的算法，称之为 Edge rank。Edge rank 考虑了 SNS 网站用户之间的交互行为和交互的时效性，从而计算新鲜事出现权重，达到优化新鲜事排序、以及改变仅按时间排序的现状的目的。Edge rank 算法的好坏还需要时间来验证。

Interactions Rank 是 Google 的科学家最新提出的一种基于用户交互的社交图谱分析算法【1】，它定义用户与好友圈子之间的交互类别，并对不同的交互行为进行打分，找出与用户最亲密的好友圈子。

在 Interactions Rank 算法框架下，社交图谱用带权值的有向图来表示。图的节点代表用户，图的边代表用户之间的交互关系。考虑到用户之间的交互有主动和被动之分，图的边定义为带方向的，并且不同的方向有不同的权重。

从上面的计算公式中可以看出，Interactions Rank 主要考虑了以下三方面的因素：

1. 交互频率： 用户与好友圈的交互频率越高，代表该好友圈相对用户的权重越大。
2. 交互的时效性： 好友圈的权重随着时间不断变化。
3. 交互的方向： 用户主动与好友交互要比被动交互对 Interactions Rank 产生的影响大。

总之，Interactions Rank 从用户的一组交互数据中计算而来，其中和分别表示好友圈子对该用户和该用户对好友圈子发起的互动行为。是当前时间，是发生交互行为的时间戳。可以调节时间因素对 Interactions Rank 的影响大小，可见，时间对 Interactions Rank 的影响是呈指数型衰减的。

好友推荐是 SNS 网站帮助用户拓展人脉关系的有效途径，Interactions Rank 为好友推荐提供了很好的依据。推荐引擎需要分析用户的社交关系，找到用户最可能认识的人。在拓展用户的好友圈子中，Interactions Rank 作为重要因素来衡量与用户发生交互的人之间的相关度，相关度越高，被推荐的概率越大。

Interactions Rank 的方法已被 Google 的电子邮件服务用来为用户推荐可能的收件人。当用户撰写一封电子邮件，在填写收件人名单时，推荐引擎会根据当前填写的名单为邮件撰写人推荐更多的收件人。其原理就是基于 Interactions Rank，对已填写的收件人群组进行扩充。该方法还被用来对用户的收件人列表进行纠错，对拼写错误的收件人地址提供修改建议。

【1】“Suggesting (More) Friends Using the Implicit Social Graph”, Maayan Roth, Tzvika Barenholz, Assaf Ben-David, David Deutscher, Guy Flysher, Avinatan Hassidim, llan Horn, Ari Leichtberg, Naty Leiser, Yossi Matias, Ron Merom, International Conference on Machine Learning (ICML), 2011.

InfoQ 相关内容：

文章：社会化推荐在人人网的应用

视频：社会化推荐算法在人人网的应用实践

作者简介：张叶银，毕业于中科院自动化所，目前担任人人网 Social Graph 算法工程师，主要负责 Social Graph 算法的研发，感兴趣的方向主要有大规模数据挖掘机器学习的应用及社会化计算。