使用
MapReduce
实现图的一些算法
随着处理的图规模增长(比如复杂网络),以致图的节点和边信息无法完全载入内存,这给执行在图上的算法带了很大挑战
。而云计算是一种很好的解决方案。《
Graph Twiddling in a MapReduce World
》介绍了将一些图算法分解成一系列
MapReduce
Job
的方案
(
1
)首先给一个简单的例子作为下面将介绍的较复杂的算法的一部分:统计每个节点的度,并加入到每条边的记录中。
输入:图中的每条边,比如:
(FRED, ETHEL)
输出:
Key
为每条边,
Value
为该边两节点的度
执行过程如图所示:
该过程使用两个
Job
。
第一个
Job
的
mapper
读入表示边的节点对记录,将每条边分解成两条记录输出,
Key
为边的每个节点,
Value
为边;
reducer
输入为每个节点,以及包含该节点的所有边;这样即可统计每个节点的度,并可获得边的其中一个节点的度信息。
第二个
Job
仅在
reducer
中合并边的每个节点的度。
(
2
)图简化算法:去掉回路、重复的边。
由
mapper
去掉产生回来的边:先将所有节点排序产生一个列表,对每条边的节点若第一次出现在列表中,则从列表中取得该节点;若列表中少于两个节点,则忽略掉剩余所有边。
然后
mapper
根据边的节点为其产生一个
hashcode
,作为输出的
key
,确保代表相同关系的边具有相同的
key
(有向图可先对边的节点排序)。(这里有个问题:
mapper
中保存的
member list
是局部的,并非被所有的
mapper
共享?
)
reducer
中记录
key
标识下的唯一条边,去掉其他重复边。
(
3
)遍历三元环(计算节点三元环的个数是统计复杂网络聚类系数的重要步骤)
遍历三元环通常分两步:
1.
遍历两条边形成的开三元组(
open
triads
),例如
{(A, B), (B, C)}
;
2.
判断是否存在边闭合每个开三元组形成三元环。
具体的方法:对节点排序,按具有较低次序的节点分组所有边(每条边仅属于一组),然后判断每组边里的每一对边是否形成三元环;对节点可按度排序,具有较低度的节点因为本身相连的边就很少,因此其组内边较少,而度较大的节点,因为与其相连的一些边以分配到度较低的节点的组中,因此确保其组也不会很大。
采用
MapReduce
框架的执行过程:
先采用算法(
1
)添加每条边的节点度信息;再使用两个
Job
处理。
第一个
Job
:在
mapper
中,提取每条边具有较小度的节点作为
Key
,边作为
Value
以输出;
reducer
中成对组合
Value
中的边,形成开三元组,输出以封闭该开三元组的边为
Key
,该开三元组为
Value
。
第二个
Job
:输入为第一个
Job
的输出和边记录文件。对于第一个
Job
的输出
,mapper
输出仍以边为
Key
,开三元组为
Value
;对边记录,
mapper
输出以边为
Key
,
value
为空;
在
reducer
中,若
value
为非空,则
value
中的所有三元组与
key
对应的边组合成三元环。
执行过程如图所示:
Job1
:
Job2:
分享到:
相关推荐
主要为大家详细介绍了基于MapReduce实现决策树算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
使用Hadoop MapReduce实现两个矩阵相乘算法
基于hadoop2.0,mapreduce实现朴素贝叶斯算法,源码,NaieBayes
用MapReduce实现KMeans算法,数据的读写都是在HDFS上进行的,在伪分布下运行没有问题。文档中有具体说明。
云计算MapReduce实现KNN算法,使用环境:在vmware虚拟机上安装unbuntu14系统,系统中安装hadoop。文件中包含有MapReduce以及KNN的java代码、包含训练数据的excel表格以及详细的教程文档,文档中手把手教到如何使用...
hadoop之MapReduce实现二度好友算法,包含输入数据demo,完整运算代码,在windows10下成功运行,输出结果为cat hello:2,hadoop:2,mr:1,world:1类似。
基于MapReduce的矩阵相乘算法代码及其使用
- 该项目实现了KNN算法在Hadoop平台基于***欧拉距离***,***加权欧拉距离***,***高斯函数***的MapReduce实现。 - 特色或创意:在网上KNN实现的例子上添加了基于***欧拉距离***,***加权欧拉距离***,***高斯函数***...
基于哈希技术和MapReduce的大数据集K-近邻算法实现代码
MapReduce实现单元最短路径算法.doc
基于MapReduce的Apriori算法代码及其使用
这是我基于MapReduce实现的Kmeans算法,用Java语言,在一个完全分布式系统运行良好
基于MapReduce的图算法
摘要:为了提高k-nearestneighboralgorithm(KNN)算法处理大数据集的能力,本文利用MapReduce并行编程模型,同时结合KNN算法自
简单的在MapReduce中实现两个表的join连接简单的在MapReduce中实现两个表的join连接简单的在MapReduce中实现两个表的join连接
Hadoop 用mapreduce实现Wordcount实例,绝对能用
mapreduce实现apriori算法,亲测可行!需要自行下载数据集。数据集链接如下http://fimi.ua.ac.be/data/