面向分布式图计算的图划分算法研究

发布时间：2021-06-18 16:05

　　随着信息时代的到来,人们在现实生活中积累了大量的图结构数据,分布式图计算框架通过将大规模图数据划分至多台机器上进行并行处理以获得高效的计算效率。图数据的划分作为分布式计算的基础,划分结果的优劣严重影响着分布式图计算的性能,因此,面向分布式图计算的图划分算法成为学者们研究的热点问题。已有的图划分算法根据划分方式的不同可被分为离线图划分算法和流式图划分算法,其中离线图划分算法划分精度较高,但需要依赖完整的图数据信息进行划分操作,而流式图划分算法仅依赖部分图数据信息进行划分,但划分精度较低。本文针对以上问题对图划分算法进行了深入研究并设计新的图划分算法,使得在基于局部图数据信息的情况下可以得到较高的图划分精度。本文研究主要包括以下两个方面:（1）提出两阶段局部图划分算法。针对已有图划分算法的缺点,本文设计了一种新的图划分思想:局部图划分。该划分思想可基于局部图数据信息进行划分操作,同时在划分过程中至多只需保存单个分区的数据信息,有效的降低了对机器性能的要求,更适合大规模图数据的划分问题。基于该划分思想,本文提出了一种两阶段局部图划分算法。该算法引入模块度的概念以量化每个分区的结构紧密程度,并... 

【文章来源】：合肥工业大学安徽省 211工程院校 教育部直属院校

【文章页数】：62 页

【学位级别】：硕士

【部分图文】：

图2.1分布式图计算框架中的PageRank一次迭代Fig2.1OneiterationofPageRankindistributedgraphcomputationsystem通过以上分析可以看出，在分布式图计算框架中，初始图划分的结果会直接影响系统的运行效率

合肥工业大学专业硕士研究生学位论文边分割算法相对易于调度，只需通过跨分区边进行数据的传。但是边分割算法同样存在一些不可避免的缺陷：因为在现实通常要远大于节点的数目，因此边分割方式在进行数据传输的网络开销，降低了系统的运行效率；同时在分布式图计算框负载通常与各分区的边数相关而非节点的数目，因此点分割分区的计算负载，避免系统资源的浪费。因此在后文的图划分能相对较优的点分割方式进行图数据的划分。

边分割算法相对易于调度，只需通过跨分区边进行数据的传。但是边分割算法同样存在一些不可避免的缺陷：因为在现实通常要远大于节点的数目，因此边分割方式在进行数据传输的网络开销，降低了系统的运行效率；同时在分布式图计算框负载通常与各分区的边数相关而非节点的数目，因此点分割分区的计算负载，避免系统资源的浪费。因此在后文的图划分能相对较优的点分割方式进行图数据的划分。图 2.2 图划分中边分割方式Fig 2.2 Edge-cut in graph partitioning

【参考文献】：
期刊论文
[1]MapReduce与Spark用于大数据分析之比较[J]. 吴信东,嵇圣硙.  软件学报. 2018(06)
[2]分布式图处理系统技术综述[J]. 王童童,荣垂田,卢卫,杜小勇.  软件学报. 2018(03)



本文编号：3236964