● 摘要
复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的描述自然界中存在的各种复杂系统的网络结构。对复杂网络的分析研究能够挖掘出其描述的复杂系统中蕴含的有用信息。复杂网络中社区结构识别是一种通过网络中节点的行为模式挖掘出节点行为特点关系的一种复杂网络研究方法。通过对网络中社区的挖掘，能够找出一组具有相似行为模式的节点，从而可以为复杂网络挖掘提供基础。现有社区识别方法的不足之处在于其可扩展性，现有算法只适用于中小规模复杂网络。随着网络规模的不断增长，现有方法无法满足大规模复杂网络社区识别计算所带来的时间与空间需求。在这种情况下，基于集群的并行社区结构识别方法无疑对大规模复杂网络的社区识别起着至关重要的作用。本文旨在研究如何设计并实现基于MapReduce计算模型的高效复杂网络并行社区识别方法。MapReduce模型是Google提出的一种被广泛应用的并行计算模型，但由于其设计初衷是解决大规模批处理计算问题，因此，MapReduce模型以及其开源实现Hadoop并没有为任务的迭代执行提供支持，使用它进行迭代地复杂网络社区识别计算只能实现为不断地手动提交任务，这将会不可避免的带来性能上的开销。本文针对Hadoop框架在迭代计算上的不足对其进行改进，使其更好地满足复杂网络并行社区结构识别计算的需要。本文的主要工作如下：1) 针对大规模复杂网络社区结构识别计算的需求，提出了基于MapReduce并行计算模型的社区结构并行识别方法。并通过实验证明，本文提出的并行识别方法具有良好的可扩展性，能够满足大规模复杂网络中社区结构识别的需要；2) MapReduce并行计算模型及其开源实现Hadoop没有提供对任务或任务组迭代计算的支持。针对这一问题，本文对MapReduce开源实现Hadoop进行了改进与完善，使其更好地支持复杂网络统计特征计算与社区结构识别的计算需要；3) 设计实现了复杂网络并行分析计算工具，包括统计特征计算、社区结构识别、计算结果展示等模块，说明了其体系结构、运行原理和执行流程。