论文部分内容阅读
Internet的高速发展,将人们带入“知识爆炸”的时代,海量信息在带给人们方便的同时,也增加了人们在海量数据中获取有用知识的难度。复杂网络是20世纪以来出现的新型学科,随着大数据时代的到来,复杂网络进入快速发展的道路,在节点重要性排序、社团挖掘、传播动力学等方面开展了大量的研究,研究成果广泛应用到政治经济、社交媒体、物理生物等领域。但随着研究方法的深入与研究场景的延伸,复杂网络带给人们一个巨大的挑战是如何在大规模网络数据中有效地进行复杂网络研究分析。为应对这些挑战,人们开始使用Hadoop、Spark和GraphLab等大数据工具来进行大规模复杂网络研究分析。本文旨在针对基于云计算的复杂网络关键算法进行研究,设计并实现了三个具有代表性的复杂网络分析算法,这三个算法分别是:基于云计算的节点重要性排序算法、基于云计算的社团挖掘算法和基于云计算的SIR模型传播算法。首先,在对现有的云计算平台以及复杂网络的经典算法进行深入的研究之后,提出基于云计算,面向海量网络数据,可扩张的复杂网络分析算法。其次,根据每个算法的特点选择合适的云计算平台,设计适当的数据结构。不同的云计算平台有不同的应用场景,在合适的云计算平台上进行算法设计可以明显提高算法效率。最后,通过实验对上述三个算法进行正确性及效率验证。基于云计算的节点重要性排序算法利用LeaderRank中每个顶点只考虑与其邻居进行交互的思想,针对GraphLab和Hadoop两个平台进行算法实现。使用随机构造的小网络测试算法的准确性,使用Stanford SNAP上提供的Twitter、Friendster等顶点规模达到上千万的网络数据集来测试在面对大规模网络时的效率。基于云计算的社团挖掘算法利用标签传播的思想,针对GraphLab平台进行算法设计与实现。使用Zachary’s Karate Club这个真实社团结构以及模块度指标来测试算法的准确性,使用Stanford SNAP上的com-Orkut等公用数据集来测试算法在处理大规模网络时的效率。基于云计算的SIR模型传播算法使用度相关感染方式,模拟SIR模型。通过实验发现,本算法有很强的灵活性,可以模拟包括SI、SIS、SIRS等模型,同时在处理大规模网络时表现出高扩展性。通过大量的实验测试发现,本文提出的这三个算法在处理网络数据规模上表现出很高的扩展性,对进行大规模复杂网络分析有很大的优势。