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

摘要

网络模体是揭示网络结构设计原则和生长演化机制的重要基础，是复杂网络的基本构建块，近年来已成为复杂网络及复杂系统的研究热点，并取得了显著的研究成果。软件网络作为一种人工复杂网络，展现出了“小世界”和“无尺度”的结构特性，但目前针对软件网络的模体研究相对不足。目前对网络模体查找算法的研究几乎都是基于单机平台的串行算法，而串行算法的查找效率较低并且很难满足大规模网络中模体的查找需求，使得对软件网络模体的研究和分析受限。
　　首先，通过对并行算法和并行编程模型进行介绍和比较，阐明了本文采用MapReduce编程模型的原因，通过对传统串行模体查找算法的执行原理和流程进行分析，并根据模体查找的特点和数据处理顺序探寻了软件网络模体查找过程的并行性。然后，对基于节点扩展的ESU模体查找算法进行了详细的分析，总结出了此算法的树形查找结构及其所具有的潜在并行性，并对模体查找问题按数据划分的形式进行了分解，在此基础上设计出了基于MapReduce的并行模体查找算法——MRESU算法。接下来，我们在Hadoop集群上实现了MRESU算法，并运用不同规模的软件网络实例对算法的效率、加速比和扩展性进行了验证和分析。最后，将本文提出的MRESU算法应用于面向对象软件系统复杂性研究中，运用MRESU算法对具体的软件网络中的模体进行查找，并对具体的软件系统从模体的角度分析其结构特性和演化规律。我们通过对多个软件系统和同一软件系统的不同版本中的模体进行分析，发现了模体出现频率和统计显著性与其结构稳定性之间的关系，以及在软件演化过程中结构稳定的模体的出现规律，得出了面向对象软件系统的宏观结构稳定性和微观结构稳定性之间的关系。
　　本文提出的MRESU算法能够使模体查找效率得到显著的提升，为大规模软件网络中模体的查找提供了一种有效手段。此外，通过将MRESU算法应用到面向对象软件系统复杂性研究中，分析了面向对象软件系统的结构特性和演化规律，这有助于软件开发人员深入理解软件系统结构和生长演化过程，对软件系统迭代开发具有重要的指导意义。

目录

声明

摘要

第1章 绪论

1．1 软件系统的复杂性

1．2 软件网络理论及研究现状

1．2．1 从复杂网络到软件网络

1．2．2 软件网络研究现状

1．3 模体查找研究意义

1．4 本文研究内容与组织结构

第2章 软件网络模体相关问题

2．1 软件网络

2．2 网络模体

2．3 模体查找算法

2．3．1 模体查找算法概述

2．3．2 模体查找算法研究现状

2．5 本章小结

第3章 MapReduce并行编程模型

3．1 并行算法概述

3．2 并行算法设计

3．2．1 并行算法的设计方法

3．2．2 并行算法的问题划分

3．3 MapReduce模型

3．3．1 传统的并行编程模型

3．3．2 MapReduce编程模型

3．4 Hadoop分布式并行计算平台

3．5 本章小结

第4章 基于MapReduce的模体查找算法

4．1 模体查找流程

4．2 ESU算法分析

4．2．1 ESU算法

4．2．2 ESU算法树形结构

4．3 数据划分方法

4．4 MRESU算法设计

4．4．1 Map函数的设计

4．4．2 Reduce函数的设计

4．5 本章小结

第5章 MRESU算法的实现及实验分析

5．1 Hadoop实验集群搭建

5．1．1 实验软件环境和硬件环境

5．1．2 Hadoop集群搭建

5．2 评价指标

5．3 实验结果分析

5．3．1 实验参数与实验测试数据的选择

5．3．2 算法加速效果实验分析

5．3．3 算法可扩展性实验分析

5．4 本章小结

第6章 MRESU算法在面向对象软件分析中的应用

6．1 软件网络中常见的模体结构

6．1．1 软件设计模式与模体

6．1．2 软件系统中的模体结构

6．2 结构稳定性分析

6．3 基于模体的软件演化分析

6．4 软件宏观结构稳定性和微观结构稳定性关系

6．5 本章小结

第7章 总结与展望

7．1 工作及贡献

7．2 不足与展望

参考文献

致谢