Hadoop实例：二度人脉与好友推荐的讲解
恍惚恍惚又来到了文章的学习，想必大家又有很多问题吧!
在新浪微博、人人网等社交网站上，为了使用户在网络上认识更多的朋友，社交网站往往提供类似“你可能感兴趣的人”、“间接关注推荐”等好友推荐的功能。一直很好奇这个功能是怎么实现的。
其实，社交网站上的各个用户以及用户之间的相互关注可以抽象为一个图。以下图为例：
顶点A、B、C到I分别是社交网站的用户，两顶点之间的边表示两顶点代表的用户之间相互关注。那么如何根据用户之间相互关注所构成的图，来向每个用户推荐好友呢？可能大家都听说过六度人脉的说法，所谓六度人脉是指：地球上所有的人都可以通过五层以内的熟人链和任何其他人联系起来。通俗地讲：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。”这个理论在社交网络中同样成立。oracle教程
现在我们以上图为例，介绍下如何利用用户之间相互关注所构成的图，来向每个用户推荐好友。首先我们不得不假设的是如果两用户之间相互关注，那么我们认为他们认识或者说是现实中的好友，至少应该认识。假设我们现在需要向用户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度好友。
下面是Python写的N度人脉的算法，可以输出某个用户的N度好友,代码详见这里。oracle视频
下面几点是其与宽度优先搜索的不同之处：
1. 宽度优先搜索搜索的是起始顶点可达的所有顶点，N度人脉不需要，它只需要向外走N步，走到N步的顶点处便停止，不需要再往外走了。
2. 走过N步之后，结果中包含起始顶点往外走1、2……N-1步所能到达的所有顶点，返回结果之前需将这些点删除。
3. 变量pathLenFromStart记录这N步具体的走法。
经李克强总理签批，2015年9月，国务院印发《促进大数据发展行动纲要》（以下简称《纲要》），系统部署大数据发展工作。
《纲要》明确，推动大数据发展和应用，在未来5至10年打造精准治理、多方协作的社会治理新模式，建立运行平稳、安全高效的经济运行新机制，构建以人为本、惠及全民的民生服务新体系，开启大众创业、万众创新的创新驱动新格局，培育高端智能、新兴繁荣的产业发展新生态。
《纲要》部署三方面主要任务。一要加快政府数据开放共享，推动资源整合，提升治理能力。大力推动政府部门数据共享，稳步推动公共数据资源开放，统筹规划大数据基础设施建设，支持宏观调控科学化，推动政府治理精准化，推进商事服务便捷化，促进安全保障高效化，加快民生服务普惠化。二要推动产业创新发展，培育新兴业态，助力经济转型。发展大数据在工业、新兴产业、农业农村等行业领域应用，推动大数据发展与科研创新有机结合，推进基础研究和核心技术攻关，形成大数据产品体系，完善大数据产业链。三要强化安全保障，提高管理水平，促进健康发展。健全大数据安全保障体系，强化安全支撑。[11]
2015年9月18日贵州省启动我国首个大数据综合试验区的建设工作，力争通过3至5年的努力，将贵州大数据综合试验区建设成为全国数据汇聚应用新高地、综合治理示范区、产业发展聚集区、创业创新首选地、政策创新先行区。
围绕这一目标，贵州省将重点构建“三大体系”，重点打造“七大平台”，实施“十大工程”。
“三大体系”是指构建先行先试的政策法规体系、跨界融合的产业生态体系、防控一体的安全保障体系；“七大平台”则是指打造大数据示范平台、大数据集聚平台、大数据应用平台、大数据交易平台、大数据金融服务平台、大数据交流合作平台和大数据创业创新平台；“十大工程”即实施数据资源汇聚工程、政府数据共享开放工程、综合治理示范提升工程、大数据便民惠民工程、大数据三大业态培育工程、传统产业改造升级工程、信息基础设施提升工程、人才培养引进工程、大数据安全保障工程和大数据区域试点统筹发展工程。
此外，贵州省将计划通过综合试验区建设，探索大数据应用的创新模式，培育大数据交易新的做法，开展数据交易的市场试点，鼓励产业链上下游之间的数据交换，规范数据资源的交易行为，促进形成新的业态。
国家发展改革委有关专家表示，大数据综合试验区建设不是简单的建产业园、建数据中心、建云平台等，而是要充分依托已有的设施资源，把现有的利用好，把新建的规划好，避免造成空间资源的浪费和损失。探索大数据应用新的模式，围绕有数据、用数据、管数据，开展先行先试，更好地服务国家大数据发展战略。
#p#分页标题#e#
oracle视频教程
上诉的算法看似可行，其实在实际中并不适用。社交网站上的用户量至少是千万级别的，不可能把所有用户之间相互关注的关系图放进内存中，这个时候就可以依赖 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的代码，详见这里。oracle数据库教程
根据上述两轮的MapReduce的方法，我以部分微博的数据进行了测试，测试的部分结果如下：
通过与我(@Intergret)相互关注的138位好友，两轮的MapReduce向我推荐的二度好友前三位是：2010963993（@可乐要改变），2022127621（@琥珀露珠）和2572979357（@赵鸿泽），他们都是我本科的同学，有很多共同的好友，但我跟他们三目前尚未相互关注，所以推荐结果还算靠谱。
| 更多视频课程文章的课程，可到课课家官网查看。我在等你哟！！！ |
