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

No.43期

MapReduce 图算法概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面这是一个迭代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. 王:哈哈,没错,就是这种感觉。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-07-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

关于Unity ParticleSystem的一些"冷"知识

  目前的游戏开发中,粒子系统的使用想必是标配了,Unity自然也提供了相应的解决方案:ParticleSystem,网上对ParticleSystem的介绍也...

10110
来自专栏数据科学与人工智能

【数据挖掘】图数据挖掘

互联网发展至今,数据规模越来越大,数据结构越来越复杂,而且对系统的需求越来越高。如果学习过数据结构,那么都知道图是放在最后一个结构,当你学习了图,那么应该感知到...

34480
来自专栏数据结构与算法

博弈论进阶之Anti-SG游戏与SJ定理

前言 在之前,我们初步了解了一下SG函数与SG定理。 今天我们来分析一下SG游戏的变式——Anti-SG游戏以及它所对应的SG定理 首先从最基本的Anti-Ni...

39440
来自专栏java工会

科大讯飞人工智能方向的一次面试经历

28550
来自专栏CDA数据分析师

工具 | R、Python、Scala 和 Java,到底该使用哪一种大数据编程语言?

有一个大数据项目,你知道问题领域(problem domain),也知道使用什么基础设施,甚至可能已决定使用哪种框架来处理所有这些数据,但是有一个决定迟迟未能做...

28880
来自专栏Python中文社区

Python数据分析之基情的择天记

專 欄 ❈ 罗罗攀,Python中文社区专栏作者 专栏地址: http://www.jianshu.com/u/9104ebf5e177 ❈ 人一生都可能无...

23460
来自专栏我是攻城师

Lucene暴走之巧用内存倒排索引高效识别垃圾数据

308100
来自专栏Jerry的SAP技术分享

你的项目刚刚启动?是时候考虑Globalization了!

关于这个很长的定语的由来,请参考这篇文章,里面有王聪的背景介绍,包括他种菜的特长:当我用UI5诊断工具时我用些什么。

12520
来自专栏CDA数据分析师

数据整理中经典的分类汇总问题的Python实现

? 数据分析职场新人,精通一门语言至关重要。写个web服务,可以用python、 写个服务器脚本,可以用python、 数据清洗和网络爬虫,可以用python...

273100
来自专栏牛客网

阿里一面

【每日一语】当你厌恶你身边的人,你表达厌恶最好的方式不是和他们争吵,而是自己勤快点儿,加把劲离开他们。那样,他们就永远从你的生活中消失,和死了差不多。

20730

扫码关注云+社区

领取腾讯云代金券