一种高效的大规模动态图划分算法的研究与实现

论文摘要

大数据时代,很多问题的底层数据模型是顶点或边的数据规模达到千万甚至上亿级别,且顶点和边实时变化的大规模动态图,例如,社交网络图、Web网页图等等。为了高效地进行大规模动态图的分布式/并行计算,必须对大规模动态图进行均衡合理划分,高效的大规模动态图划分是高效的大规模动态图分布式/并行计算的基础和前提。一般而言,高效的大规模动态图划分算法需要满足以下3个要求:1)划分的各分区间的通信代价尽可能小;2)各分区内的顶点/边的数量应尽可能均衡;3)大规模动态图划分算法是大规模动态图分布式/并行计算的预处理,所以大规模动态图划分算法应具有较好的时间性能。由于大规模动态图划分问题的复杂性,它是一个亟待解决的NP难问题。近年来,许多学者开始关注并研究大规模动态图划分问题,也开始涌现了一些创新性的大规模动态图划分算法,但是现有算法普遍存在以下缺陷:1)算法时间性能有待于提高;2)算法不能实时应对大规模动态图中边/顶点的变化;3)现有的算法仅考虑了各个分区上顶点/边的均衡问题,没有考虑动态图中各分区的活跃顶点/边在图计算中的均衡问题;4)算法需要较大的辅助空间。因此,创新研究与实现高效的大规模动态图划分算法,具有重要的理论与现实意义。论文选题来源于国家自然科学基金面上项目,创新研究并实现新的高效的大规模动态图处理框架及划分算法。针对现有算法的缺陷,本文提出了一种高效的大规模动态图处理框架DynGraphX,并基于该框架,提出了一种基于图中顶点中心性的哈希大规模动态图分布式划分算法CBH-DGP。论文的主要工作及创新如下:1)提出了一种新的顶点中心性,即一个顶点在网络中的重要程度。顶点中心性度量方法,它能高效实时地识别大规模动态图中的活跃高中心性顶点;2)提出了一种基于顶点中心性的边散列策略,将活跃的中心顶点尽量散列开,以避免大规模动态图划分计算过程中,各分区上顶点的计算量不均衡问题;3)针对现在尚无公开的适合大规模动态图处理框架问题,基于大规模静态图处理框架GraphX,创新设计并实现了一种新的高效的大规模动态图处理框架DynGraphX。并基于该框架设计与实现了高效的分布式大规模动态图划分算法CBHDGP;4)在大量的大规模动态图数据集上,对所提出的大规模动态图处理框架DynGraphX,以及所提出并实现的大规模动态图分布式划分算法CBH-DGP进行了较充分地仿真实验。大量的实验结果表明:所提出的大规模动态图处理框架DynGraphX可行、高效;所提出并实现的大规模动态图分布式划分算法CBH-DGP优于目前最好的大规模动态图划分算法,其划分质量高,划分速度快,并且可显著提高大规模动态图计算性能。目前算法还存在未充分考虑有向图结构特征和低中心性顶点之间的连接关系等问题。作者后期将进一步改进与完善当前算法,充分考虑有向图结构,使之能在有向图上有更好的划分质量。并且充分考虑低中心性顶点之间的连接关系,进一步降低通信代价。

论文目录

• 摘要
• 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 后续工作展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 硕士论文

作者: 尚宁

导师: 李雁妮

关键词: 大规模动态图,图划分,顶点中心性

来源: 西安电子科技大学

年度: 2019

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

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

单位: 西安电子科技大学

基金: 国家自然科学基金面上项目,海量深网数据源的自动发现与集成研究,2015.1~2018.12

分类号: TP311.13;O157.5

DOI: 10.27389/d.cnki.gxadu.2019.000659

总页数: 90

文件大小: 4133K

下载量: 80