作者系阿里巴巴集团1688技术部普通码农
引言
周末看到一篇不错的文章“Graph Twiddling in a MapReduce world” ,介绍MapReduce下一些图算法的实现。文章语言质朴,介绍很多实用图优化技巧。文章2009年发表,至今已经被引用183次,足以证明这篇文章价值。目前这篇文章网上已经有人对这篇文章做了介绍,但仅介绍了其中最简单的两个算法,对其中的所做优化,并没有做分析。为了加深对文章算法的理解,我重新对这篇文章的算法做了翻译,同时加了自己的理解,以及算法在我们工作可能涉及的应用场景。鉴于“一图胜千言”的想法,我增加大量图片,以及实际例子演化算法流程,以增强对算法的理解。
介绍
MapReduce框架非常适合处理大规模的流数据,而图算法的实现一直是MapReduce的难点。已发表这方面的文章也不是特别多。根据“Graph Twiddling in a MapReduce world”,本文详细介绍了 四个图算法的实现,分别是图节点度计算,三元环检测,四元环检测,k-桁结构(k-trusses)检测。
图节点度计算
度是图节点最基本的特征,在Hadoop中求节点度的方法比较简单。以图1为例,需要求其中各个节点的度。
Hadoop算法实现非常简单,如下图2所演示
MapReduce-1: 分别以边的两个节点作为key,边作为键值输出,reducer阶段统计节点关联的边个数,同时输出边中相应节点的度;MapReduce-2:以MapReduce-1的输出作为输入,reducer阶段合并边上两个节点的度。
三元环检测
三元环检测主要思想是先查找所有开三元环(相当于三个节点形成一条链),然后一条边是否可以将这个开三元环闭合(即是否有一条边可以将链的两个端点闭合)。
这里有两个优化点,可以大大提供算法性能。 首先,为了降低计算复杂度,一个三元环,我们只输出一次。如果对三元环中节点排序(最简单的办法就是节点按字母排序),通过逆序或者旋转三元环的节点输出顺序只有一种(例如ABC,BAC, CBA, ACB… 都可以由ABC逆序或者旋转得到)。由于这个性质,每轮mapper reducer过程,输出时候保证节点是按顺序的。 其次,二次爆炸问题,当某一个节点度比较高的时候,那么通过这个节点边就会很多,进而形成的开三元环也会比较多(例如,节点A的度为N,那么通过节点A边有N条边,这N条边任意两条都可以形成一个开三元环,最终A节点将形成N(N-1)/2 个开三元环,当N很大时候性能会有很大影响)。一个解决办法是,使用度较小的节点为key做合并,这样数据被分散到度比较小的节点上。(结合上面的性质,三元环节点序是只有一种,所以不会出现有些三元环没找到的情况)。这两个优化点能大大提高算法性能。
我们以第一节中的图1为例,具体的hadoop算法流程如下
图见下载中的PDF
检测三元环算法包含两个MapReducer过程:
MapReducer-1
Mapper:
input: 带有度的边
output: 以边中度较小的节点为key,边为键值输出;【降低二次爆炸问题】
Reducer:
process:合并节点的开三元环;
output:输出开三元环,输出时候按三元环两端节点字母排序输出。【保证输出顺序】
MapReducer-2
Mapper:
input:a) 所有带有度的边,按字母顺序输出; b) MapReduce-1中产生的所有开三元环;
output:输出边 和开三元环;
Reducer:
process: 判断是否,一条边能将开三元环闭合;能够闭合则是一个三元环;
output: 输出所有三元环
Apache Hadoop 2.2.0 MapReduce1.x向2.x迁移 http://www.linuxidc.com/Linux/2014-06/103209.htm
MapReduce编程实战 http://www.linuxidc.com/Linux/2014-04/100241.htm
MapReduce--如何设置Reducer的个数 http://www.linuxidc.com/Linux/2014-04/99726.htm
Hadoop之MapReduce自定义二次排序流程实例详解 http://www.linuxidc.com/Linux/2014-03/98498.htm
Hadoop 使用 MapReduce 排序 思路 http://www.linuxidc.com/Linux/2014-03/98756.htm
Hadoop之MapReduce框架心跳机制分析 http://www.linuxidc.com/Linux/2014-01/95723.htm
基于MapReduce的图算法 PDF 下载见 下面的地址:
------------------------------------------分割线------------------------------------------
免费下载地址在 http://linux.linuxidc.com/
用户名与密码都是www.linuxidc.com
具体下载目录在 /2014年资料/8月/19日/基于MapReduce的图算法 PDF
下载方法见 http://www.linuxidc.com/Linux/2013-07/87684.htm
------------------------------------------分割线------------------------------------------
本文永久更新链接地址:http://www.linuxidc.com/Linux/2014-08/105692.htm