你好,游客 登录
背景:
阅读新闻

MapReduce 图算法概述

[日期:2017-07-10] 来源:  作者: [字体: ]

  转自:灯塔大数据;微信:DTbigdata

  编者按:灯塔大数据将每周持续推出《从零开始学大数据算法》的连载,本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作,以对话的形式深入浅出的从何为大数据说到大数据算法再到大数据技术的应用,带我们在大数据技术的海洋里徜徉~每周五定期更新,欢迎来做客呦!

  上期回顾&查看方式:

  在上一期中,我们学习了利用 MapReduce 来增加相似连接的可扩展性,通过计算单元函数值和集合的合取函数值,来求解集合的析取函数值。在这一期中,我们将学习用MapReduce 框架,以并行计算的观点来解决一些图论问题。

  PS:了解上期详细内容,请在自定义菜单栏中点击“灯塔数据”—“技术连载”进行查看;或者滑到文末【往期推荐】查看。

  No.43期

  MapReduce 图算法概述

  Mr.王:MapReduce 作为一种经典的并行编程框架,可以用于解决很多问题,包括一些图论问题。在客观世界中,很多问题都可以抽象为图论问题。前面我们提到过如何用磁盘算法来解决一些图论问题,现在我们尝试用MapReduce 框架,以并行计算的观点来解决一些图论问题。

  还是先举个例子吧。你会经常去使用一些社交网络吧。

  小可:是的,现在通过社交网络,我可以非常方便地与同学联系。社交网络上人与人之间的好友连接关系就可以抽象成一个图。

  Mr.王笑着说:有没有想过,在社交网络上,你的好友的最好朋友是不是你?

  小可:哈哈,我没想过,但是这还真是一个挺有趣的问题。用MapReduce 还可以解决这种问题吗?

  Mr.王:是的,具体怎么做,我们用一个社交网络图来举例吧。

  

每周学点大数据|No.44 MapReduce 图算法概述

 

  小可:嗯,这是一个非常典型的社交网络图,其中包含着我和我的一些朋友,还有一些我关注的公用主页等信息。那么要如何发现一个人最好的朋友是不是我呢?

  Mr.王:这个算法的工作分为以下几个步骤。

  第1 步:去掉无关的边和节点。

  

每周学点大数据|No.44 MapReduce 图算法概述

 

  这一步是对整个图进行一个预处理,将图上的一些与我们研究的问题无关的节点去掉,毕竟来自社交网络上的信息还是比较繁多和杂乱无章的。描述社交网络的图上往往会包含一些与“好友”这种关系无关的边和点,会涉及一些关注的网页、兴趣爱好等这样的数据,这与我们要完成的任务无关,为了更好地解决问题,我们要将与好友关系相关的内容具体地提取出来。

  第2 步:用朋友列表标记每一个节点。

  对于每一个节点,我们都为其标记一个朋友列表,这个朋友列表记录了与之直接相连的朋友节点,以及自己与他们之间的亲密度。

  第3 步:沿着每条边下推标签。

  经过多次下推标签,可以让我们获得关于朋友的朋友的信息。直接与我们具有朋友关系的这些节点是“1 跳朋友”,而与我们不是朋友关系却与1 跳朋友有关系的就是2 跳朋友,想要知道某一个朋友F 是不是和我的关系最紧密,我们就要去发现与朋友F 是1 跳朋友的2 跳朋友,去看看我们和这些2 跳朋友对于朋友F 来说的亲密度如何。这样经过比较,我们就可以知道自己究竟是不是他最好的朋友了。

  小可:这个算法看起来还是挺容易的啊。

  Mr.王:如果这个算法仅仅运行在单机上,而且数据量不那么大的话,那么这就是一个非常简单的问题。但是在实际的社交网络中比如说Facebook,这个朋友关系网络就会是一张非常大的图,不论是顶点(人)还是边(关系)数量都是非常庞大的,图的稠密程度也很高,在一个小的圈子内,经常会出现两两互为朋友这样的子图。所以对于比较大的图来说,我们想要执行前面的算法就会遇到很多困难,处理它就会变得非常慢。此时,我们就需要MapReduce 的帮忙。

  这个问题用MapReduce 去做虽然不那么自然,但却是可以解决的。

  一个比较简单的想法是,我们用邻接表来表示一个图,将节点作为key,而邻接表就是value。

  

每周学点大数据|No.44 MapReduce 图算法概述

 

  Mr.王:这里我们再讨论一个社交网络中常见的功能,那就是朋友推荐。

  小可:这个我知道,我在用社交网络时,经常有一个栏位告诉我有个人与我有很多的共同好友,所以他可能是我的朋友。

  Mr.王:嗯,看来你已经很熟悉这个功能了,这就是一个典型的“谁是我多个好友的好友”问题。在此基础上,还有超过直接朋友的问题,比如在图上经过两三跳与你连接,这也可能是你潜在的朋友。

  小可:嗯,如果不是直接连接的话,所需要的运行开销可能就会更大。

  Mr.王:是这样的。此时我们用一轮MapReduce 已经不足以解决多跳的问题,以至于要使用多轮MapReduce。这种多轮MapReduce 我们称之为迭代MapReduce。

  下面这是一个迭代MapReduce 的基本框架。

  

每周学点大数据|No.44 MapReduce 图算法概述

 

  小可:哦!我看懂了。首先将整个算法的输入内容放入dir 1 中,然后会去执行一轮MapReduce,dir 1 会被输入到Mapper 中,再输出到Reduce中,Reducer 会接收来自Mapper的输出作为输入,在处理之后输出为dir 2。之所以能形成循环,是因为它将dir 2 的结果又送回了dir 1,然后程序框架会把dir 2 再次输入到MapReduce 中。重复执行上述过程,这样整个系统就可以一轮一轮地运行,每一轮的输出都是下一轮的输入,也就构成了MapReduce的迭代。

  Mr.王:你说的对,这就是形成循环和迭代MapReduce 的基本思路。另外,为了让MapReduce 进行得更加高效、顺利,在数据被放入dir 1 中和最终从dir 2 中取出来之前,可以对数据分别进行预处理和后处理。想想在迭代MapReduce 中需要注意什么问题?

  小可:这里有一个循环……所以……

  Mr.王:每一轮循环的输出都会拿去做什么?

  小可:每一轮循环的输出都会是下一轮Map 的输入,所以必须要保证Reduce 的输出符合Map的输入形式。

  Mr.王:很好,这需要对Map 和Reduce 的输入输出进行标准化处理,使得每一轮的输出和下一轮的输入相匹配,这也就要求Reduce 输出的数据格式和Map 的输入格式是严格一致的。

  现在我们来看一看一般的图操作算法是如何实现的。如果我们要执行的这个图操作运行在非并行算法下,那么计算机每次就会处理图中的一个项,或者处理一条边,或者处理一个点。

  也就是说,只有一个访问游标在执行算法,同时只有一个对象在接受算法的处理或者访问。而在MapReduce 框架下的图算法中,处理操作往往是并行的,由多个Mapper 同时处理图的多个部分,以求更快地完成对图的一轮处理。另外,绝大多数的图算法都需要经历多个MapReduce阶段,这意味着整个算法的构成可能是多个相同的MapReduce 过程形成的MapReduce 迭代,或者是由不同的MapReduce 过程形成的MapReduce 链。

  在进行MapReduce 算法设计时,我们需要着眼于两个方面:一是对每一个节点的操作是什么;二是要看对每一个节点执行的操作需要知道哪些信息,以及这些信息在图中距离自己有多远。因为信息往往是沿着边进行推送的,而是在节点上完成计算的,所以要做到对图中的节点有一个透彻的认识。

  小可:就好像我们自己就是一个节点一样?

  Mr. 王:哈哈,没错,就是这种感觉。

  

推荐 打印 | 录入: | 阅读:
相关新闻      
本文评论   
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款