分布式环境下图坚韧度的计算

发布时间：2017-08-08 02:16

  本文关键词：分布式环境下图坚韧度的计算

  更多相关文章： 分布式计算 图坚韧度 Spark

【摘要】：随着社交网络等应用的飞速发展,图结构数据的理论研究,尤其是大规模图数据在分布式环境计算变得十分必要。图处理作为大数据处理领域的一个分支,形成了独有的特色:包括较差的局部性,I/O操作频繁,难以并行化,大规模的中间结果等等。图坚韧度是表示图结构稳定性的图因子,与图顶点连通度和图边连通度相比,坚韧度可以提供更多关于图的稳定程度的信息。给定任意正实数k,判断一个图是否是k-坚韧的是co NP-完全问题。尽管它的计算是困难的,图坚韧度的概念在交通网络分析,社交网络分析等问题中仍起着重要作用。本文研究了分布式环境下图坚韧度的近似计算问题,结合图坚韧度与图的拉普拉斯特征值的关系,给出了计算图坚韧度的下界的Lower Lap算法。我们设计了图坚韧度求解的分布式近似算法:基于广度优先搜索的算法BFS-T和基于拼接短随机游走PageRank的Page Rank-T算法。我们基于Spark分布式计算平台RDD和Graph X通用图数据处理框架,利用道路交通网络数据和人工合成图数据评测了图坚韧度在交通网络分析和复杂网络分析中的效果,验证了上述算法的有效性。此外,我们设计和实现了资源监测优化系统,通过调整图数据划分,初始点选择,分析系统瓶颈,进一步提升了图坚韧度的计算效率。
【关键词】：分布式计算 图坚韧度 Spark
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• ABSTRACT5-8
• 第1章 绪论8-18
• 1.1 课题背景及研究的目的和意义8-9
• 1.2 相关理论的发展概况9-16
• 1.2.1 图坚韧度理论10
• 1.2.2 相关概念10-13
• 1.2.3 分布式计算系统13-16
• 1.2.4 本文符号16
• 1.3 本文的主要研究内容16-18
• 第2章 图坚韧度的下界估计18-27
• 2.1 图坚韧度18-20
• 2.2 坚韧度下界估计算法20-26
• 2.2.1 坚韧度与独立集20-22
• 2.2.2 基于拉普拉斯特征值的坚韧度下界估计算法22-26
• 2.3 本章小结26-27
• 第3章 分布式坚韧度算法设计27-43
• 3.1 问题定义27-28
• 3.2 基于广度优先搜索的算法28-32
• 3.3 基于随机游走PAGERANK的算法32-35
• 3.4 实验结果及分析35-42
• 3.4.1 实验环境36-38
• 3.4.2 实验数据38-39
• 3.4.3 实验结果及分析39-42
• 3.5 本章小结42-43
• 第4章 基于SPARK的图坚韧度计算43-60
• 4.1 SPARK系统框架43-47
• 4.1.1 弹性分布式数据集RDD43-45
• 4.1.2 图数据处理框架Graph X45-47
• 4.2 系统监测与优化47-59
• 4.2.1 图划分策略47-51
• 4.2.2 磁盘、网络、CPU51-58
• 4.2.3 采样策略58-59
• 4.3 本章小结59-60
• 结论60-61
• 参考文献61-66
• 致谢66

【相似文献】

中国期刊全文数据库 前7条

1 肖恩利,束金龙,闻人凯;图的代数连通度及其点连通度[J];华东师范大学学报(自然科学版);2003年04期

2 喻祥明;黄晓晖;;修正泡序图的限制性点连通度(英文)[J];新疆大学学报(自然科学版);2012年01期

3 侯学慧;;2-边-轨道图的点连通性[J];山西师范大学学报(自然科学版);2012年03期

4 雷澜,王斌;L(G)图的若干性质[J];重庆工商大学学报(自然科学版);2005年01期

5 李峰;曹世鹏;贾媛媛;;两个网络的可靠性比较[J];青海师范大学学报(自然科学版);2008年03期

6 闫飞龙;贾子英;;基于复杂网络的机降作战目标选择方法[J];火力与指挥控制;2014年04期

7 ;[J];;年期

中国硕士学位论文全文数据库 前7条

1 黄达;有向笛卡尔乘积图的圈点连通度[D];新疆大学;2011年

2 吴彭;泡序图的条件点连通度[D];清华大学;2011年

3 韩洋;机会传感网络移动节点连通度及其影响因素的研究[D];南昌航空大学;2014年

4 王国亮;完全对换网络和三角塔网络的若干性质[D];西北师范大学;2014年

5 于志华;完全多部图的一致最可靠性与星图的圈点连通度[D];新疆大学;2010年

6 侯学慧;2-边—轨道图的连通性[D];新疆大学;2011年

7 任强;分布式环境下图坚韧度的计算[D];哈尔滨工业大学;2015年

，

本文编号：637792