三角形的并行枚举算法

发布时间：2018-04-26 16:23

本文选题：三角形枚举 + 大规模图数据　；参考：《计算机应用》2017年12期

【摘要】：经典GT算法是三角形并行枚举算法的MapReduce实现,然而该算法只能枚举全图的三角形结构,对部分顶点构成的三角形结构无法直接进行枚举。针对此问题,提出一种直接枚举部分顶点构成三角形结构的并行算法。首先,通过分析被选点的分布,给出被选点构成三角形的所有组合集合;然后,通过对该集合的筛选,实现对部分点构成三角形结构的直接枚举;最后,将该算法在Spark系统实现,以实现该算法的高效性和广泛性。在人工生成数据集和真实数据集上与GT算法进行对比实验,实验结果表明,所提改进算法的运行时间只有GT算法运行时间的1/3,在Spark上的运行时间仅是Hadoop上运行时间的1/7。该算法可用于更高效地直接生成图中任意点所构成的三角形数据集。
[Abstract]:The classical GT algorithm is the MapReduce implementation of triangle parallel enumeration algorithm . However , the algorithm can only enumerate the triangle structure of the whole graph , and the triangle structure composed of some vertices can not be enumerated directly . At last , by analyzing the distribution of the selected points , we present a direct enumeration of the triangle structure of the selected points . Finally , the algorithm is implemented in Spark system . The experimental results show that the running time of the proposed improved algorithm is only 1 / 7 of running time of the Hadoop . The algorithm can be used to directly generate the triangle data set of arbitrary points in the graph .

【作者单位】：西北工业大学计算机学院;
【基金】：中国科技部国家重点研发计划项目(2016YFB1000703) 国家863重大项目(2015AA015307) 国家自然科学基金重点项目(61332006);国家自然科学基金面上项目(61672432,61472321);国家自然科学基金青年项目(61502390)~~
【分类号】：TP301.6

【相似文献】