论文研究-基于MapReduce的最大团算法.pdf

所需积分/C币:5 2019-09-20 16:47:45 459KB .PDF

论文研究-基于MapReduce的最大团算法.pdf,  随着社会发展,个体之间的关系日益复杂,给传统的社会网络分析方式带来了新的挑战和机遇.MapReduce框架的产生解决了这种问题,它提供了简单的编程接口,隐藏了底层的细节,将程序员从传统的并行编程模式中解放出来.同时它的简单性也存在一些不足,如内在的表达能力较弱,对于一些复杂的算法必须由程序员对其进行分解,分解为可以在MapReduce
152 系统工程理论与实践 第31卷 7: if IsPair(elem)then 8: clcm. members=clem. members U Kcy 9: elem. list=mask n elem. list 10: If clcm. Isit!=0 then 11: Emit(elem. members, elem. list 12: Else 13: Printf(elem. members 算法中,nid表示当前节点的编号. members集合包括了当前极大团中所有的成员,初始为空集.lit表 示邻接链表数据结构.N1表示邻接链表,N2表示与所有极大团成员都具有连接的节点的集合 42 Mapreduce算法伪代码描述 对于上面提到的算法,有一个非常重要的问题需要解决.仝局变量传递的问题.在串行算法中,size的 值是生成之后,其后的所有循环都可以看得到.但是,这在 Mapreduce中是不可能的,因为我们采取一种穷 举方法来应对回溯的问题.所以当计算出sze时,所有现存的团的大小都大于或等于size,从而我们没有必 要也没有时机来传递size 43 Mapreduce剪枝实现 在串行算法中,使用剪枝减小计算量,提高了效率假如已知最大团的成员数目sie>a,我们的剪枝标 准可以变为d+(m-i)≤α.现在我们需要找一个a,1954年,由 Turan提供了一个公式:对于任意一个 图假设有n个节点,m条边有:1262m2m=a,如果图的密度为D,根据密度公式D=m2m,那么: 非剪枝算法的剪枝优化:我们使用a来近似size,首先是a的传递问题,因为a是一个常数,所以有很 多方法可以把它传给 Mapreduce过程,比如环境变量,配置文件,分布式缓存等.其次,对于深度来说,每 次循环深度都会增加1,因为可以预期,所以可以像siκe那样传递,也可以在list结构中增加一个成员变量 Depth,每次 Reduce后将其值增1.最后的两个变量是元素在邻接链表结构中的位置和邻接链表中元素总个 数.由此,剪枝所需的变量都已得到,剩下的就是在Map过程中进行检测.当满足条件d+(m-1)≤a时进 行剪切,否则继续 4.4测试结果 本测试在由3台机器组成集群中完成 表2测试结果 测试1测试2测试3 节点数 100 边数 245 时间 155s 282s 328s 最大团成员数 5 结论 使用 Mapreduce模型实现图算法与单机图算法最主要的区别在于:在单杌模型中总能保冇一些全局变 量数据结构等在内存中,用来加快速度但是对于 Mapreduce模型来说、这是非常困难的,因为它主要的思 想就是数据之间相互独立,没有关联的或者说它没有提供一个内建的机制用来共享全局状态 由于这个限制,使得基于 Map reduce的图算法都有了一个大致模式,先对一个节点进行本地计算,然后 将结果传到它们相邻节点,经过多次的循环将整个图覆盖.另外, Mapreduce框架提供的( combiner机制可 以减少节点之间传递的数据量,提高 Mapreduce工作效率 最后.对基于 Mapreduce框架的图算法的总结如下: 1)将图结构本身由Map传递到 Reduce,在 Reduce过程中每一个节点对应的结构被更新,然后写回,这 样使得输入与输出具有相同的结构,方便下一轮循环的开始. 2)使用邻接表表示图结构.可能是很大的一个数据结构,除了相邻的节点之外,还可能包括很多其它信 增刊2 潘全,等:基于 Map reduce的最大团算法 153 息,如边的属性等 3)我们可以认为,计算是沿着边进行的,在Map过程对每一个邻接链表中的元素做Map操作,所产生 的键值对由相邻的节点组成 4)算法是循环的,前一次 Mapreduce的输出是下一次 Mapreduce的输入,有一个非 Mapreduce驱动 检查退出条件,并采取相应动作 参考文献 1 Venner. Pro HadoopM. Jason APRESS, 2005. 06 2 Wang F, Qiu J, Yang J, et al. Hadoop high availability through metadata replication Cl// Proceeding of the First International Workshop on Cloud Data Management, 2009: 5-8 3 Cohen J. Graph twiddling in a Map Reduce world J. Computing in Science Engineering, 2009: 29-41 4 Dcan J, Ghemawat S. MapRcduce: A fexible data processing tool[J. Communications of the ACM. 2010: 7-9 5 Scott J. Social Network Analysis: A Handbook[M. 2nd ed. London: SAGE Publications, Ltd, 2000 6 GroSs J J L. Yellen Handbook of Graph Theory M. CRCPress, 2004 7 Wu B. Pei X. A parallel algorithm for enumerating all the maximal kPlexesJ. Emerging Technologies in Knowl- edge Discovery and Data Mining, 2007: 476-483 8 Lin J. Exploring large-data issues in the curriculum: A case study with MapReduce(Cl// Proceedings of the Third Workshop on Issues in Teaching Computational Linguistics, 2008: 54-61 9 Kavulya S, Tan J Q, Gandhi R, ct al. An analysis of traces from a production MapReducc cluster[Cl//Pro- ceedings of the 2010 10th IEEE/ACM International Conference ol Cluster, Cloud and Grid CoInlputing, 2010 23-24.

...展开详情
试读 4P 论文研究-基于MapReduce的最大团算法.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于MapReduce的最大团算法.pdf 5积分/C币 立即下载
    1/4
    论文研究-基于MapReduce的最大团算法.pdf第1页
    论文研究-基于MapReduce的最大团算法.pdf第2页

    试读已结束,剩余2页未读...

    5积分/C币 立即下载 >