Hadoop实例：二度人脉与好友推荐

在新浪微博、人人网等社交网站上，为了使用户在网络上认识更多的朋友，社交网站往往提供类似“你可能感兴趣的人”、“间接关注推荐”等好友推荐的功能。一直很好奇这个功能是怎么实现的。

其实，社交网站上的各个用户以及用户之间的相互关注可以抽象为一个图。以下图为例：

498)this.width=498;'' onmousewheel = ''javascript:return big(this)'' title="clip_image002" style="cursor: pointer" border="0" alt="clip_image002" src="/uploadfile/201301/9/C49624879.jpg" width="439" height="176" /> 

顶点A、B、C到I分别是社交网站的用户，两顶点之间的边表示两顶点代表的用户之间相互关注。那么如何根据用户之间相互关注所构成的图，来向每个用户推荐好友呢？可能大家都听说过六度人脉的说法，所谓六度人脉是指：地球上所有的人都可以通过五层以内的熟人链和任何其他人联系起来。通俗地讲：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。”这个理论在社交网络中同样成立。

现在我们以上图为例，介绍下如何利用用户之间相互关注所构成的图，来向每个用户推荐好友。首先我们不得不假设的是如果两用户之间相互关注，那么我们认为他们认识或者说是现实中的好友，至少应该认识。假设我们现在需要向用户I推荐好友，我们发现用户I的好友有H、G、C。其中H的好友还有A，G的好友还有 F，C的好友还有B、F。那么用户I、H、G、C、A、B、F极有可能是同一个圈子里的人。我们应该把用户A、B、F推荐给用户I认识。进一步的想，用户 F跟两位I的好友C、G是好友，而用户A、B都分别只跟一位I的好友是好友，那么相对于A、B来说，F当然更应该推荐给用户I认识。

可能你会发现，在上面的分析中，我们使用了用户I的二度人脉作为他的推荐好友，而且我们对用户I的每个二度人脉进行了投票处理，选举出最优推荐。其实，我觉得，二度人脉的结果只能看看某个用户的在社交网站上的人际关系链，而基于投票选举产生的二度人脉才是好友推荐功能中所需要的好友。

另外你也可能已经认识到所谓的N度人脉，其实就是图算法里面的宽度优先搜索。宽度优先搜索的主要思想是From Center To Outer，我们以用户I为起点，在相互关注所构成的图上往外不退回地走N步所能到的顶点，就是用户I的N度好友。

498)this.width=498;'' onmousewheel = ''javascript:return big(this)'' title="无标题" style="cursor: pointer" border="0" alt="无标题" src="/uploadfile/201301/9/CD9624129.png" width="635" height="314" /> 

下面是Python写的N度人脉的算法，可以输出某个用户的N度好友,代码详见这里。

下面几点是其与宽度优先搜索的不同之处：

1. 宽度优先搜索搜索的是起始顶点可达的所有顶点，N度人脉不需要，它只需要向外走N步，走到N步的顶点处便停止，不需要再往外走了。

2. 走过N步之后，结果中包含起始顶点往外走1、2……N-1步所能到达的所有顶点，返回结果之前需将这些点删除。

3. 变量pathLenFromStart记录这N步具体的走法。

上诉的算法看似可行，其实在实际中并不适用。社交网站上的用户量至少是千万级别的，不可能把所有用户之间相互关注的关系图放进内存中，这个时候就可以依赖 Hadoop了。下面的实例中，我们的输入是deg2friend.txt，保存用户之间相互关注的信息。每行有两个用户ID，以逗号分割，表示这两个用户之间相互关注即认识。

二度好友的计算需要两轮的MapReduce。第一轮MapReduce的Map中，如果输入是“H，I”，我们的输出是 key=H，value=“H，I”跟key=I，value=“H，I”两条结果。前者表示I可以通过H去发现他的二度好友，后者表示H可以通过I去发现他的二度好友。

根据第一轮MapReduce的Map，第一轮MapReduce的Reduce 的输入是例如key =I，value={“H，I”、“C，I”、“G，I”} 。其实Reduce 的输入是所有与Key代表的结点相互关注的人。如果H、C、G是与I相互关注的好友，那么H、C、G就可能是二度好友的关系，如果他们之间不是相互关注的。对应最上面的图，H与C是二度好友，G与C是二度好友，但G与H不是二度好友，因为他们是相互关注的。第一轮MapReduce的Reduce的处理就是把相互关注的好友对标记为一度好友（“deg1friend”）并输出，把有可能是二度好友的好友对标记为二度好友（“deg2friend”）并输出。

第二轮MapReduce则需要根据第一轮MapReduce的输出，即每个好友对之间是否是一度好友（“deg1friend”），是否有可能是二度好友（“deg2friend”）的关系，确认他们之间是不是真正的二度好友关系。如果他们有deg1friend的标签，那么不可能是二度好友的关系；如果有deg2friend的标签、没有deg1friend的标签，那么他们就是二度好友的关系。另外，特别可以利用的是，某好友对deg2friend标签的个数就是他们成为二度好友的支持数，即他们之间可以通过多少个都相互关注的好友认识。

两轮MapReduce的代码，详见这里。

根据上述两轮的MapReduce的方法，我以部分微博的数据进行了测试，测试的部分结果如下：

通过与我(@Intergret)相互关注的138位好友，两轮的MapReduce向我推荐的二度好友前三位是：2010963993（@可乐要改变），2022127621（@琥珀露珠）和2572979357（@赵鸿泽），他们都是我本科的同学，有很多共同的好友，但我跟他们三目前尚未相互关注，所以推荐结果还算靠谱。

原文链接：http://www.datalab.sinaapp.com/?p=192