每周学点大数据 | 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. 王：哈哈，没错，就是这种感觉。

内容来源：灯塔大数据