三角形的并行枚举算法
来源：计算机应用杂志2017年第12期北京时间：
作者：王卓, 索勃, 潘巍
单位：西北工业大学 计算机学院, 西安 710129
摘要：经典GT算法是三角形并行枚举算法的MapReduce实现，然而该算法只能枚举全图的三角形结构，对部分顶点构成的三角形结构无法直接进行枚举。针对此问题，提出一种直接枚举部分顶点构成三角形结构的并行算法。首先，通过分析被选点的分布，给出被选点构成三角形的所有组合集合；然后，通过对该集合的筛选，实现对部分点构成三角形结构的直接枚举；最后，将该算法在Spark系统实现，以实现该算法的高效性和广泛性。在人工生成数据集和真实数据集上与GT算法进行对比实验，实验结果表明，所提改进算法的运行时间只有GT算法运行时间的1/3，在Spark上的运行时间仅是Hadoop上运行时间的1/7。该算法可用于更高效地直接生成图中任意点所构成的三角形数据集。
关键词：三角形枚举,大规模图数据,MapReduce,部分点枚举,Spark
基金资助：中国科技部国家重点研发计划项目（2016YFB1000703）；国家863重大项目（2015AA015307）；国家自然科学基金重点项目（61332006）；国家自然科学基金面上项目（61672432，61472321）；国家自然科学基金青年项目（61502390）。
