基于云计算平台的图算法研究

北京邮电大学 杜雅红

【英文题名】 The Research of Graph Algorithm Based on Cloud Computing
【作者】 杜雅红
【导师】 张雷
【学位授予单位】 北京邮电大学
【学科专业名称】 计算机科学与技术
【学位年度】 2011
【论文级别】 硕士
【网络出版投稿时间】 2011-08-09
【关键词】 图挖掘 云计算 连通分量 Betweenness
【英文关键词】 graph mining cloud computing connected component betweenness centrality

本文旨在对基于云计算的图算法进行研究,设计并实现了三个基本的图算法,这三个算法分别为无向图的连通分量算法,有向图的强连通分量算法以及无向图的Betweenness算法。 首先,根据每个算法的特点设计了适当的数据结构。合理的数据结构可以让算法在性能上得到很大的提高。 然后,在对云计算以及图算法进行研究以后,在云计算平台上设计并实现了无向图的连通分量算法,有向图的强连通分量算法以及无向图的Betweenness算法。无向图的连通算法利用了标签传播算法(LPA)的原理,其中还特别提出小连通分量的定义以及求解方法。有向图的强连通分量算法通过标签标记和颜色标记来实现。而无向图的BetweenneSS算法则是在 UlrikBrandS提出的回溯思想的基础上实现的。

temp_11121611078699.zip