基于mapreduce的软件网络模体查找算法研究

《基于mapreduce的软件网络模体查找算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文基于MapReduce的软件网络模体查找算法研究作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：李俊徐久强教授东北大学信息科学与工程学院硕士学科类别：工学计算机系统结构2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：高福祥赵海周长春东北大学2014年6月万方数据AThesisinComputerArchitectureResearchonMapReduce--basedAlgorithmforMotifsDiscoveryinSoftwareNetworkBy

2、LiJunSupervisor：ProfessorXuJiuqiangNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：菩褒日期：砌f(f。6。≯J学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留

3、并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口学位论文作者签名：巷锾签字日期：御f甲。∥，≥7两年西导师签名：签字日期：删凄沙陬6r吖万方数据东北大学硕士学位论文摘要基于MapReduce的软件网络模体查找算法研究摘要网络模体是揭示网络结构设计原则和生长演化机制的重要基础，是复杂网络的基本构建块，近年来已成为复杂网络及复杂系统的研究热点，并取得了显著的研究成果。软件网络作为一种人工复杂网络

4、，展现出了“小世界"和“无尺度”的结构特性，但目前针对软件网络的模体研究相对不足。目前对网络模体查找算法的研究几乎都是基于单机平台的串行算法，而串行算法的查找效率较低并且很难满足大规模网络中模体的查找需求，使得对软件网络模体的研究和分析受限。首先，通过对并行算法和并行编程模型进行介绍和比较，阐明了本文采用MapReduce编程模型的原因，通过对传统串行模体查找算法的执行原理和流程进行分析，并根据模体查找的特点和数据处理顺序探寻了软件网络模体查找过程的并行性。然后，对基于节点扩展的ESU模体查找算法进行了详细的分析，总结出了此算法的树形查找结构及其所具

5、有的潜在并行性，并对模体查找问题按数据划分的形式进行了分解，在此基础上设计出了基于MapReduce的并行模体查找算法——MRESU算法。接下来，我们在Hadoop集群上实现了MRESU算法，并运用不同规模的软件网络实例对算法的效率、加速比和扩展性进行了验证和分析。最后，将本文提出的MRESU算法应用于面向对象软件系统复杂性研究中，运用MRESU算法对具体的软件网络中的模体进行查找，并对具体的软件系统从模体的角度分析其结构特性和演化规律。我们通过对多个软件系统和同一软件系统的不同版本中的模体进行分析，发现了模体出现频率和统计显著性与其结构稳定性之间的

6、关系，以及在软件演化过程中结构稳定的模体的出现规律，得出了面向对象软件系统的宏观结构稳定性和微观结构稳定性之间的关系。本文提出的MRESU算法能够使模体查找效率得到显著的提升，为大规模软件网络中模体的查找提供了一种有效手段。此外，通过将MRESU算法应用到面向对象软件系统复杂性研究中，分析了面向对象软件系统的结构特性和演化规律，这有助于软件开发人员深入理解软件系统结构和生长演化过程，对软件系统迭代开发具有重要的指导意义。关键词：软件网络；模体，IMapReduce；并行算法：MRESU万方数据东北大学硕士学位论文AbstractAbstractNet

7、workMotifsareimportantfoundationandbasicbuildingblocksofcomplexnetworkonrevealingthearchitecturedesignprinciplesandevolutionarymechanism，whichhasbeenbecomearesearchhotspotofcomplexnetworkandcomplexsystems．Asanartificialcomplexnetwork，SoftwareNetworkshowsthe“SmallWorld’’and“Scal

8、e-free’’phenomenon，buttheresearchonthemotifsofsoftware