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

来源 :东北大学 | 被引量 : 1次 | 上传用户:laniya82
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
网络模体是揭示网络结构设计原则和生长演化机制的重要基础,是复杂网络的基本构建块,近年来已成为复杂网络及复杂系统的研究热点,并取得了显著的研究成果。软件网络作为一种人工复杂网络,展现出了“小世界”和“无尺度”的结构特性,但目前针对软件网络的模体研究相对不足。目前对网络模体查找算法的研究几乎都是基于单机平台的串行算法,而串行算法的查找效率较低并且很难满足大规模网络中模体的查找需求,使得对软件网络模体的研究和分析受限。首先,通过对并行算法和并行编程模型进行介绍和比较,阐明了本文采用MapReduce编程模型的原因,通过对传统串行模体查找算法的执行原理和流程进行分析,并根据模体查找的特点和数据处理顺序探寻了软件网络模体查找过程的并行性。然后,对基于节点扩展的ESU模体查找算法进行了详细的分析,总结出了此算法的树形查找结构及其所具有的潜在并行性,并对模体查找问题按数据划分的形式进行了分解,在此基础上设计出了基于MapReduce的并行模体查找算法——MRESU算法。接下来,我们在Hadoop集群上实现了MRESU算法,并运用不同规模的软件网络实例对算法的效率、加速比和扩展性进行了验证和分析。最后,将本文提出的MRESU算法应用于面向对象软件系统复杂性研究中,运用MRESU算法对具体的软件网络中的模体进行查找,并对具体的软件系统从模体的角度分析其结构特性和演化规律。我们通过对多个软件系统和同一软件系统的不同版本中的模体进行分析,发现了模体出现频率和统计显著性与其结构稳定性之间的关系,以及在软件演化过程中结构稳定的模体的出现规律,得出了面向对象软件系统的宏观结构稳定性和微观结构稳定性之间的关系。本文提出的MRESU算法能够使模体查找效率得到显著的提升,为大规模软件网络中模体的查找提供了一种有效手段。此外,通过将MRESU算法应用到面向对象软件系统复杂性研究中,分析了面向对象软件系统的结构特性和演化规律,这有助于软件开发人员深入理解软件系统结构和生长演化过程,对软件系统迭代开发具有重要的指导意义。
其他文献
植物的生长发育过程以及各种胁迫反应离不开各种酶的参与。GSNOR(S-nitrosoglutathione reductase)是亚硝基谷胱甘肽(GSNO)的还原酶。GSNOR能够高效特异的催化GSNO的还原反应
本文以分布在甘肃省西北部荒漠地区的荒漠伯劳指名亚种(Lanius isabellinus isabellinus)为研究对象,在2010-2014年对荒漠伯劳的卵大小与窝卵数、卵大小与产卵顺序之间的关系
自1965年Zadeh提出模糊集FS (Fuzzy Sets),以FS为基础概念而形成的模糊数学在理论研究和应用研究上均有长足发展,已经成为当今数学的一个重要分支。模糊集合概念提出后,模糊
本文采用磁控溅射方法在单晶硅衬底和玻璃衬底上制备了Ni-Mn-In-Co磁性形状记忆合金薄膜,采用了扫描电子显微观察、原子力显微镜表面形貌分析、X射线衍射分析和示差扫描热分
在植物适应多种复杂的外界环境中,LRR-RLKs(富含亮氨酸重复序列类受体激酶)在感受细胞外信号并启动细胞内多种反应等方面发挥着极其重要的作用。拟南芥Somatic Embryogenesis
血栓类疾病是当今致死率、致残率最高的疾病之一,严重威胁人类的生活和健康。血栓类疾病的治疗已经成为当今医学界研究的重点问题之一。目前,溶栓药物已经发展至第三代,主要
近年来,寻找复杂网络中的社区结构已经成为复杂网络中研究的热点,社区发现问题也因此成为近年复杂网络领域中的热门问题。由于现实存在的网络社区通常并不是绝对彼此独立的,
模糊逻辑研究的一个重要方向是研究其逻辑代数系统.逻辑代数系统中一般以偏序集和一些运算为模型来建立逻辑与代数的桥梁,用代数方法解决逻辑问题.剩余格是一类比较重要的代
本文利用1979-2009年ERA-Interim再分析资料,诊断分析了平流层准两年振荡(QBO)和残余环流(或称Brewer-Dobson环流,BD环流)的长期变化趋势以及两者之间的相互联系,得到了以下
本文采用集合均方根滤波(EnSRF)和基于奇异值分解(SVD)的集合降维同化方法(SVD-En3DVar)对发生在我国江苏地区夏季的两次强对流天气过程进行雷达资料的同化研究,以WRF中尺度