一种有效的基于GraphX的分布式结构化图聚类算法

来源：计算机科学与探索杂志2018年第10期北京时间：

作者：时生乐，赵宇海，李源，印莹，王国仁

单位：东北大学 计算机科学与工程学院，沈阳 110819

摘要：结构化图聚类是大图数据分析的主要技术之一，在社区检测、生物功能发现和图可视化等许多实际应用中具有重要意义。目前的分布式结构化图聚类算法大多基于Hadoop的MapReduce框架，但该框架需要精确计算图中所有邻接顶点之间的相似性且需要大量的磁盘I/O开销，极大增加了算法的运行时间。针对以上问题，主要工作和贡献点如下：（1）提出两个削减规则，第一个削减规则用来减少邻接顶点之间相似性计算次数，第二个削减规则通过非精确计算邻接顶点间的相似性来减少计算时间。（2）提出一种基于Spark中GraphX的结构化图聚类算法GXDSGC，该算法在运行期间不需要大量的磁盘I/O开销。（3）通过在大量真实数据集和合成数据集上的实验，证实提出的GXDSGC算法的有效性。GXDSGC算法比基于Hadoop中MapReduce框架的算法快30多倍，能够显著提高结构化图聚类在大图数据分析中的效率。

关键词：Spark,GraphX,分布式计算,图聚类,社区结构