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