论文部分内容阅读
网络技术在带给人们大量信息的同时,也极大地增加了人们从海量数据中发现有用知识的难度,而解决这一问题的努力促进了数据挖掘技术的出现和快速发展。目前,数据挖掘技术已被广泛应用到物理、生物、政治经济、互联网络、工程开发和社会生活的各个领域。图挖掘是数据挖掘中重要的一部分,通过图挖掘可以更直观、更便捷的发现数据中隐藏的信息。随着分析方法的成熟和应用场景的延伸,图挖掘带给研究人员的另一个挑战是如何在超大规模数据中进行有效的挖掘。为了应对这些挑战,工业界和学术界越来越倾向于使用云计算平台,如Hadoop等,来进行大规模数据挖掘。本文旨在对基于云计算的图算法进行研究,设计并实现了三个基本的图算法,这三个算法分别为无向图的连通分量算法,有向图的强连通分量算法以及无向图的Betweenness算法。首先,根据每个算法的特点设计了适当的数据结构。合理的数据结构可以让算法在性能上得到很大的提高。然后,在对云计算以及图算法进行研究以后,在云计算平台上设计并实现了无向图的连通分量算法,有向图的强连通分量算法以及无向图的Betweenness算法。无向图的连通算法利用了标签传播算法(LPA)的原理,其中还特别提出了小连通分量的定义以及求解方法。有向图的强连通分量算法通过标签标记和颜色标记来实现。而无向图的Betweenness算法则是在Ulrik Brands提出的回溯思想的基础上实现的。接着,通过实验对上述三个算法进行了正确性验证,并与传统算法进行了性能对比。实验结果表明,本文提出的算法在应对大规模数据时更加有效。最后,作者对Twitster进行了研究,并通过实验将Twister与MapReduce进行了对比。