手机版
你好,游客 登录 注册
背景:
阅读新闻

基于MapReduce的图算法 PDF

[日期:2014-08-19] 来源:Linux社区  作者:dannyPolyu [字体: ]

作者系阿里巴巴集团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

linux
相关资讯       MapReduce  算法  MapReduce算法 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

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