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