摘要：随着复杂系统科学的不断发展,同时受到移动通信网络、社交网络等现实网络的推动作用,人们针对复杂网络的研究逐渐深入。由于复杂网络能够很好地描述许多复杂系统,人们期望通过对复杂网络的研究和分析,揭示并掌握其统计特征、功能特性、演化规律等等,从而能够更深刻地理解复杂系统,指导解决实际问题。在研究中人们发现复杂网络存在社区结构,并且社区结构对于理解复杂网络的结构和功能非常重要,许多研究者因此投入到对社区发现的研究,社区发现问题也因此成为近年复杂网络领域中的热门问题。但是该问题迄今并未被完美解决。本文通过研究近年该领域具有代表性的文献,总结目前典型的一些社区发现算法,并分析它们的优点和不足之处,在此基础上提出一种可以并行化的重叠社区发现算法,以解决当前重叠社区发现算法普遍效率偏低,无法处理超大规模网络的问题。首先,借鉴将clique作为初始社区核心的思想,本文提出了将clique作为标签传播过程中拥有标签的基本单位这一新思路,并以此为基础提出了一种用于发现网络中重叠社区结构的CLPA算法。在人工网络以及真实网络上的实验结果都证明了基于此思想的重叠社区发现算法的有效性,并且在很多网络上该算法比其他一些算法具有更佳的社区发现结果,同时其时间效率也令人满意。其次,本文创新性的将MapReduce分布计算模型与重叠社区发现结合。由于本文提出的算法具备并行化的条件,借助于MapReduce分布计算模型,使得对现实中普遍存在的超大规模网络进行重叠社区发现成为可能,因而具有一定的实际意义。
