论文部分内容阅读
复杂系统是现实世界的重要组成部分,复杂网络是对复杂系统的抽象。研究并发掘复杂网络的性质可以帮助人们更好的理解复杂系统。随着社会的网络化以及计算机技术的不断发展,人们对现实世界的建模能力较过去有了长足的发展,这使得网络科学的工作者所接触的网络模型越来越复杂,面对的任务也越来越重。而社区结构是人们认识复杂网络的一个有力工具,从而使得解决复杂网络中的社区结构挖掘问题成为一项积极有意义的工作。现实世界中个人在生活工作中所产生的数据急剧增加,同样它们所需要的信息量也随之增加。面对海量数据,如何在一个可接受的时间内挖掘出特定人群所需要的信息是一个重要的挑战,分布式成为人们处理海量数据的主要方式之一。文中首先分析了复杂网络的基本特征并以此引出复杂网络的社区结构特征;然后分析了现有的社区结构挖掘算法,总结了算法的优缺点。基于全局信息的社区结构挖掘算法需要利用网络的全局信息,因此时空复杂度都较高,而且在复杂网络中全局信息并不容易获得。为此本文研究并实现了一种基于局部信息的社区结构挖掘算法,同时将其推广到分布式平台上进行实现。利用分布式平台的优势,达到时间与空间的良好平衡。文中在Clauset提出的局部模块度概念的基础上提出了一个新的衡量节点是否属于特定社区的函数,应用该函数对Bagrow算法进行改进,改进的算法考虑了节点的更多信息,因此在精确度上取得了进展,但是算法的迭代速度并没有提高。随后文中分析了本地社区中节点的特点并提出了两种启发式方法,应用启发式得出了一种新的算法,新算法在保持准确度的同时提高了算法的迭代速度,而后将其以MapReduce的编程模型进行实现,最后在Hadoop开源平台上实现整个算法,并进行了实验验证。实验结果表明改进算法较原始的Bagrow算法在精确度上有了一定的进步。而算法的MapReduce实现则证明了在数据量逐渐增大时,分布式计算是一个有力的武器。