分布式环境下大规模图数据的密集子图发现方法研究

论文摘要

随着互联网的应用和科学技术的不断进步,各行各业的数据正以前所未有的规模不断积累。图作为描述数据的重要数据结构被学者们广泛应用于大数据研究,图数据挖掘问题成为学术界重要的研究课题。在大规模的图数据中,图的密集部分往往是图数据中的重要部分,因此,发现大规模图数据中的密集子图成为目前研究的一个热点问题。并且,密集子图问题又可以广泛应用于频繁子图问题,社区发现等问题中,具有重要的研究意义。发现图数据中的密集子图问题是一个著名的NP-难问题。目前已经有一些学者设计了不同的方法来发现密集子图,但其中存在不适用于处理大规模图数据、发现的密集子图不连通、密集子图是局部最优解、算法不适用于在某种类型的图数据中发现密集子图等问题。为解决以上问题,本文利用分布式Hadoop平台强大的存储和计算优势,设计了一种适用于处理不同应用背景下的大规模图数据的密集子图发现算法。本文的密集子图发现算法通过HDFS来实现大数据集的存储,通过MapReduce来实现大数据集的计算。算法首先对图进行预处理,排除图中平行边和环对密集子图发现的影响。其次,为快速地发现大图中的密集子图,使用图剪枝策略快速移除一定不存于密集子图中的顶点,然后在剩余图中提取只包含在三角形中的顶点构成的子图。最后,选择初始子图并通过两个阶段不断对图进行更新,第一个阶段:在每次迭代中从当前图中顶点的邻居节点集中选择一个顶点,使得加入该顶点之后的子图密度最大,直至当前图中顶点的邻居节点集不再有顶点使得子图密度变大时终止迭代。第二个阶段:在每次迭代中,从当前子图中选择一个顶点,使得移除该顶点之后的子图密度最大,直至子图的密度不再增大时终止迭代。本文将此时的子图视为算法发现的密集子图,并且利用Spark平台的优势使用弹性分布式数据集RDD来分析图的连通情况。通过实验表明,本文提出的分布式环境下的密集子图发现算法在处理大规模图数据的运行时间上、发现的密集子图的密度上、密集子图的连通情况上取得了良好的效果,与其他算法对比具有一定的优势。

论文目录

• 致谢
• 摘要
• ABSTRACT
• 序言
• 1 引言
•   1.1 研究背景及意义
•   1.2 国内外研究现状
•   1.3 本文研究的主要内容
•   1.4 论文的组织与安排
• 2 基本知识概述
•   2.1 密集子图基本知识
•     2.1.1 图论相关基本概念
•     2.1.2 图的基本操作和符号定义
•     2.1.3 密度度量方式
•   2.2 密集子图发现算法
•     2.2.1 枚举算法
•     2.2.2 贪心算法
•     2.2.3 启发式算法
•   2.3 Hadoop技术介绍
•     2.3.1 Hadoop的总体架构
•     2.3.2 Hadoop分布式文件系统
•     2.3.3 并行编程框架MapReduce
•   2.4 Spark之弹性分布式数据集RDD
•   2.5 本章小结
• 3 密集子图发现算法
•   3.1 算法所用数据结构和集合类
•     3.1.1 边
•     3.1.2 图
•     3.1.3 三角形
•     3.1.4 路径
•     3.1.5 GNU Trove介绍
•   3.2 关键问题及解决办法
•     3.2.1 密集子图的连通性
•     3.2.2 密集子图发现算法的局部和全局最优解
•     3.2.3 大规模图数据下查找密集子图的效率
•     3.2.4 密集子图发现算法对不同类型图数据的适应性
•   3.3 密集子图发现算法主要思路
•   3.4 图数据预处理
•   3.5 图剪枝
•     3.5.1 剪枝规则（一）
•     3.5.2 证明剪枝规则（一）
•     3.5.3 剪枝规则（二）
•   3.6 密集子图发现
•     3.6.1 初始子图的选择
•     3.6.2 迭代流程
•   3.7 图的连通情况分析
•   3.8 本章小结
• 4 实验结果与分析
•   4.1 实验环境
•   4.2 网络社区概况图NCP
•   4.3 数据集描述
•     4.3.1 社交网络
•     4.3.2 通信网络
•     4.3.3 道路网络
•     4.3.4 引文网络
•     4.3.5 亚马逊产品购买网络
•     4.3.6 Web网络
•     4.3.7 数据集公布信息统计
•   4.4 图数据预处理实验结果与分析
•   4.5 图剪枝实验结果与分析
•     4.5.1 剪枝阶段（一）
•     4.5.2 剪枝阶段（二）
•   4.6 密集子图的密集度比较
•   4.7 算法在单机和分布式环境下的运行时间对比分析
•     4.7.1 图数据预处理阶段
•     4.7.2 图剪枝阶段
•     4.7.3 密集子图发现阶段
•   4.8 图的连通情况分析
•   4.9 本章小结
• 5 总结与展望
•   5.1 本文总结
•   5.2 未来展望
• 参考文献
• 作者简历及攻读硕士学位期间取得的研究成果
• 学位论文数据集

文章来源

类型: 硕士论文

作者: 李荣荣

导师: 艾丽华

关键词: 分布式,密集子图,大规模图数据,连通性

来源: 北京交通大学

年度: 2019

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

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

单位: 北京交通大学

分类号: TP311.13;O157.5

DOI: 10.26944/d.cnki.gbfju.2019.001563

总页数: 74

文件大小: 5143K

下载量: 38