Social Network如何推荐好友

“好友推荐”的功能基本上每个社交相关的产品都会需要。相关的方法有很多,例如从网络结构上分析,从用户属性上进行匹配,从用户涉及的内容上挖掘兴趣相同的人,等等。
和一般的推荐系统一样,衡量推荐的结果也主要是从准确性和多样性两个方面考虑。所以实际的产品中,一般会采用多种推荐方法混合的方式,比如新浪微博,它会推荐一些热门大号,还会根据结构信息推荐好友,另外还会根据每个用户分析得到的标签推荐兴趣相同的人,等等。

这里只讨论从网络结构上做推荐,列出的都是最简单的方法,但效果一般不会太差。

Undirected Graph

像facebook此类无向的social graph,最有用的结构特性就是“共同好友”:

1

共同好友数越多,说明两者越有可能是好友。上图中,A和B各有4个好友,而共同好友就有3个,说明A和B称为好友的可能性非常大。
实际操作中,如果只是简单的算共同好友数然后排序,效果会差一些。都会改改算法,比如根据其他feature加进一些权重,等等,但本质的思路还是一样的。

Directed Graph

互惠原则 向用户推荐那些follow了他的用户。别小看这条规则,很有用。希望在微博中涨粉,最简单的办法就是follow尽可能多的人,这些人出于互惠原则往往会refollow:

graph4

“recommending users similar to you”  方法类似于推荐系统中的协同过滤。例如,A和B follow了很多相同的人,A B之间就比较容易成为朋友,见下图:

2

新浪微博的”间接关注”推荐就是这种关系。
另一种关系是,如果同时有很多人关注了A,又关注了B,则A B容易成为好友:

3

此外,也可以将无向图的方法应用到有向图中,如新浪微博的”共同好友”推荐。

“Filtered People” 大致的思路是,如果A follow了很多人,那么我可以找出这些人共同follow的用户B,推荐给A,如下图:

5

不知道为什么,新浪微博没有使用这种方法?

更复杂一些的方法,就是采用类似于PageRank这样的random walk的算法,对节点A附近的节点(例如2度或者3度邻居)计算PR值,PR值高的自然就优先推荐。再复杂些,就是将用户推荐当成一个分类问题来处理,需要使用很多的特征,包括结构拓扑特征和用户的其它特征。

— END. —

Advertisements
相册 | 此条目发表在Social Network分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s