一种高效的大规模动态图划分算法的研究与实现
发布时间：2021-01-01 17:49
大数据时代,很多问题的底层数据模型是顶点或边的数据规模达到千万甚至上亿级别,且顶点和边实时变化的大规模动态图,例如,社交网络图、Web网页图等等。为了高效地进行大规模动态图的分布式/并行计算,必须对大规模动态图进行均衡合理划分,高效的大规模动态图划分是高效的大规模动态图分布式/并行计算的基础和前提。一般而言,高效的大规模动态图划分算法需要满足以下3个要求:1)划分的各分区间的通信代价尽可能小;2)各分区内的顶点/边的数量应尽可能均衡;3)大规模动态图划分算法是大规模动态图分布式/并行计算的预处理,所以大规模动态图划分算法应具有较好的时间性能。由于大规模动态图划分问题的复杂性,它是一个亟待解决的NP难问题。近年来,许多学者开始关注并研究大规模动态图划分问题,也开始涌现了一些创新性的大规模动态图划分算法,但是现有算法普遍存在以下缺陷:1)算法时间性能有待于提高;2)算法不能实时应对大规模动态图中边/顶点的变化;3)现有的算法仅考虑了各个分区上顶点/边的均衡问题,没有考虑动态图中各分区的活跃顶点/边在图计算中的均衡问题;4)算法需要较大的辅助空间。因此,创新研究与实现高效的大规模动态图划分算...
【文章来源】：西安电子科技大学陕西省 211工程院校 教育部直属院校
【文章页数】：90 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
1.1 选题背景与研究意义
1.2 国内外研究现状
1.3 论文的主要工作与组织结构
1.3.1 论文的主要工作与创新
1.3.2 论文组织结构
第二章 基础理论与相关工作综述
2.1 基础理论
2.1.1 相关基本概念及定义
2.1.2 大规模动态图划分的问题模型
2.1.3 顶点局部中心性
2.2 大规模动态图的特征
2.2.1 大规模动态图的拓扑结构演变特征
2.2.2 大规模动态图的拓扑结构特征
2.3 大规模图处理框架
2.3.1 GraphX的数据存储模型
2.3.2 GraphX的图计算模型
2.4 大规模动态图划分算法综述
2.5 本章小结
第三章 CBH-DGP:高效大规模动态图划分算法设计
3.1 算法设计动机
3.2 算法思想与算法框架
3.3 CBH-DGP算法的主要设计策略
3.3.1 局域中心性度量策略
3.3.2 实时局域中心性度量策略
3.3.3 实时近似局域中心性度量策略
3.3.4 基于局域中心性的边散列策略
3.4 CBH-DGP:大规模动态图划分算法设计
3.4.1 CBH-GP:初始图划分算法设计
3.4.2 UCBH-Ins:插入图划分算法设计
3.4.3 CBH-DGP算法设计优化策略
3.4.4 算法分析
3.5 时空复杂度分析
3.6 本章小结
第四章 基于DynGraphX的分布式划分算法实现
4.1 DynGraphX总体设计
4.2 DynGraphX设计与实现
4.2.1 GraphX基础
4.2.2 DynGraphX的分配模块
4.2.3 DynGraphX的图更新模块
4.2.4 DynGraphX的图计算模块
4.3 基于DynGraphX的分布式图划分算法的实现
4.3.1 CBH-DGP:大规模动态图划分算法的实现
4.3.2 CBH-GP:初始图划分算法实现
4.3.3 UCBH-Ins:插入图划分算法实现
4.4 时空复杂度分析
4.5 本章小结
第五章 实验与分析
5.1 实验环境与数据集
5.1.1 实验平台与配置介绍
5.1.2 实验数据集介绍
5.2 实验分析
5.2.1 评估准则
5.2.2 初始图划分算法性能分析
5.2.3 插入图划分算法性能分析
5.2.4 DynGraphX性能分析
5.3 本章小结
第六章 总结与展望
6.1 论文工作总结
6.2 后续工作展望
参考文献
致谢
作者简介
【参考文献】：
期刊论文
[1]社会网络节点影响力分析研究[J]. 韩忠明,陈炎,刘雯,原碧鸿,李梦琪,段大高. 软件学报. 2017(01)
本文编号：2951727
【文章来源】：西安电子科技大学陕西省 211工程院校 教育部直属院校
【文章页数】：90 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
1.1 选题背景与研究意义
1.2 国内外研究现状
1.3 论文的主要工作与组织结构
1.3.1 论文的主要工作与创新
1.3.2 论文组织结构
第二章 基础理论与相关工作综述
2.1 基础理论
2.1.1 相关基本概念及定义
2.1.2 大规模动态图划分的问题模型
2.1.3 顶点局部中心性
2.2 大规模动态图的特征
2.2.1 大规模动态图的拓扑结构演变特征
2.2.2 大规模动态图的拓扑结构特征
2.3 大规模图处理框架
2.3.1 GraphX的数据存储模型
2.3.2 GraphX的图计算模型
2.4 大规模动态图划分算法综述
2.5 本章小结
第三章 CBH-DGP:高效大规模动态图划分算法设计
3.1 算法设计动机
3.2 算法思想与算法框架
3.3 CBH-DGP算法的主要设计策略
3.3.1 局域中心性度量策略
3.3.2 实时局域中心性度量策略
3.3.3 实时近似局域中心性度量策略
3.3.4 基于局域中心性的边散列策略
3.4 CBH-DGP:大规模动态图划分算法设计
3.4.1 CBH-GP:初始图划分算法设计
3.4.2 UCBH-Ins:插入图划分算法设计
3.4.3 CBH-DGP算法设计优化策略
3.4.4 算法分析
3.5 时空复杂度分析
3.6 本章小结
第四章 基于DynGraphX的分布式划分算法实现
4.1 DynGraphX总体设计
4.2 DynGraphX设计与实现
4.2.1 GraphX基础
4.2.2 DynGraphX的分配模块
4.2.3 DynGraphX的图更新模块
4.2.4 DynGraphX的图计算模块
4.3 基于DynGraphX的分布式图划分算法的实现
4.3.1 CBH-DGP:大规模动态图划分算法的实现
4.3.2 CBH-GP:初始图划分算法实现
4.3.3 UCBH-Ins:插入图划分算法实现
4.4 时空复杂度分析
4.5 本章小结
第五章 实验与分析
5.1 实验环境与数据集
5.1.1 实验平台与配置介绍
5.1.2 实验数据集介绍
5.2 实验分析
5.2.1 评估准则
5.2.2 初始图划分算法性能分析
5.2.3 插入图划分算法性能分析
5.2.4 DynGraphX性能分析
5.3 本章小结
第六章 总结与展望
6.1 论文工作总结
6.2 后续工作展望
参考文献
致谢
作者简介
【参考文献】：
期刊论文
[1]社会网络节点影响力分析研究[J]. 韩忠明,陈炎,刘雯,原碧鸿,李梦琪,段大高. 软件学报. 2017(01)
本文编号：2951727
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2951727.html
