分布式环境下的图划分算法研究

论文摘要

自20世纪80年代开始,复杂系统的研究逐渐兴起,它被认为是解决各个领域研究面临的困难的一个重要突破点。而复杂网络是研究复杂系统的一个重要工具,如物流运输、道路规划、社交网络、生物研究等问题在研究的过程中,都可以抽象成由边和顶点组成的复杂网络,借助于复杂网络的相关技术对其进行研究。但系统中基本单元常常达到成千上万甚至是数以亿计,这就使得复杂网络的研究不得不借助于高效的计算工具来解决实时的、规模足够大的计算问题。分布式计算技术是现在最成熟、应用最广、最可行的计算加速技术之一。因此研究复杂网络的分布式计算技术具有十分重要的意义。在做分布式计算之前,需要将原始复杂网络划分成若干个子网络,保证各个子网络规模相对均衡和网络间的通信开销最小化是分布式计算性能好坏的关键。图划分技术就是解决这一问题的有效手段。图划分算法按照划分方式的不同,可以分为点划分算法和边划分算法。数据量的快速增长对图划分算法的划分质量和划分效率提出了新的要求。本文主要工作体现在以下方面:（1）针对当前点划分算法划分质量较低的问题,本文提出了基于滑动窗口的流式图划分模型（Graph Win）,该模型通过引入滑动窗口机制,根据当前划分质量和划分时间,动态调整每次划分时参考的信息量（顶点度信息和邻接信息）,以达到允许损失一定划分效率的前提下尽可能提高划分质量的目的。此外,Graph Win模型的评分函数在传统流式图划分算法的基础上做了改进,它包括自适应均衡评分函数、度评分函数、聚类评分函数,综合考虑了分区均衡性、顶点度、分区聚类系数在图划分中起到的作用。实验结果表明,相较于其他算法,Graph Win模型在一定程度上能够有效降低平均复制度。（2）针对当前边划分算法划分效率较低的问题,本文提出了基于GPU加速的图划分模型（Graph GPU）,Graph GPU模型分为初始划分阶段和优化划分阶段:在初始阶段,使用Boruvka算法对原始图数据做初始聚类,将亲和度较大的顶点尽可能被划分到同一分区;在优化划分阶段,使用桶交换算法对初始划分结果做进一步的优化。因为Boruvka算法和桶交换算法都具有并行性,所以Graph GPU模型建立在CPU+GPU异构并行计算框架基础之上。实验结果表明,Graph GPU模型相较于现有成熟的图划分算法在提高划分效率的同时,也能够降低割边率。

论文目录

文章来源

类型: 硕士论文

作者: 段赛赛

导师: 钟将

关键词: 复杂网络,分布式计算,图划分,负载均衡,通信代价

来源: 重庆大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 重庆大学

分类号: O157.5;TP301.6

DOI: 10.27670/d.cnki.gcqdu.2019.000509

总页数: 58

文件大小: 2390k

下载量: 26

相关论文文献

• [1].基于云聚合理论的城市社区划分算法研究[J]. 计算机应用研究 2017(01)
• [2].面向分布式图计算的平衡图划分算法[J]. 信息与电脑(理论版) 2019(11)
• [3].一种松弛的优化均衡流式图划分算法研究[J]. 计算机科学 2016(04)
• [4].图划分算法综述[J]. 科技信息 2014(04)
• [5].一种重叠可信社团划分算法的设计与实现[J]. 微计算机信息 2011(09)
• [6].基于目标预测的扩展目标量测集划分算法[J]. 计算机工程与应用 2020(08)
• [7].考虑通信成本和硬件碎片利用的簇划分算法[J]. 计算机辅助设计与图形学学报 2015(04)
• [8].大规模图数据划分算法综述[J]. 电信科学 2014(07)
• [9].一种基于点割的电路划分算法[J]. 计算机学报 2014(07)
• [10].有向网络重叠社区的快速划分算法[J]. 计算机科学 2014(S1)
• [11].三种经典复杂网络社区结构划分算法研究[J]. 电脑与信息技术 2011(04)
• [12].一种基于聚集系数的局部社团划分算法[J]. 计算机科学 2010(07)
• [13].基于主题与连接的局部社区划分算法[J]. 数据采集与处理 2016(03)
• [14].一种考虑执行延迟最小化和资源约束的改进层划分算法[J]. 电子学报 2012(05)
• [15].基于任务划分算法的基准程序研究[J]. 科技传播 2011(03)
• [16].VLSI电路划分算法综述[J]. 福州大学学报(自然科学版) 2011(05)
• [17].一种嵌入式系统软硬件划分算法[J]. 计算机仿真 2011(10)
• [18].基于逻辑段划分算法统计的文本信息检索[J]. 电脑知识与技术 2009(32)
• [19].一种动态网络社区划分算法[J]. 北京工业大学学报 2011(02)
• [20].基于表集合划分算法的数据交换方法研究[J]. 计算机工程与设计 2013(06)
• [21].基于适应度的簇划分算法研究[J]. 计算机仿真 2008(02)
• [22].流级别的高速网络流量动态划分算法[J]. 小型微型计算机系统 2013(05)
• [23].多级划分算法的后处理与评价方法[J]. 小型微型计算机系统 2010(01)
• [24].基于无偏Q值反馈的社区划分算法[J]. 东南大学学报(自然科学版) 2011(01)
• [25].自由曲面四边形网格等杆长划分算法[J]. 空间结构 2016(01)
• [26].改进的基于局部模块度的社团划分算法[J]. 计算机应用 2016(05)
• [27].基于模糊聚类的社团划分算法[J]. 计算机工程 2016(08)
• [28].基于子团规模的社团划分算法与地理位置[J]. 东北大学学报(自然科学版) 2012(11)
• [29].一种基于聚集系数的复杂网络社团划分算法[J]. 网络安全技术与应用 2012(09)
• [30].一种新的基于晶体管级的电路划分算法[J]. 电子与信息学报 2009(12)

标签：复杂网络论文;  分布式计算论文;  图划分论文;  负载均衡论文;  通信代价论文;