三角形的并行枚举算法

• 作者: 潘巍 王卓 索勃
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 三角形枚举 大规模图数据 MapReduce 部分点枚举 Spark
• 年，卷（期）: 2017,（12）
• 所属期刊栏目: 先进计算
• 页码范围: 3397-3400
• 页数: 4页
• 分类号: TP311.131
• 字数: 3850字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2017.12.3397

摘要

经典GT算法是三角形并行枚举算法的MapReduce实现,然而该算法只能枚举全图的三角形结构,对部分顶点构成的三角形结构无法直接进行枚举.针对此问题,提出一种直接枚举部分顶点构成三角形结构的并行算法.首先,通过分析被选点的分布,给出被选点构成三角形的所有组合集合;然后,通过对该集合的筛选,实现对部分点构成三角形结构的直接枚举;最后,将该算法在Spark系统实现,以实现该算法的高效性和广泛性.在人工生成数据集和真实数据集上与GT算法进行对比实验,实验结果表明,所提改进算法的运行时间只有GT算法运行时间的1/3,在Spark上的运行时间仅是Hadoop上运行时间的I/7.该算法可用于更高效地直接生成图中任意点所构成的三角形数据集.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘巍	西北工业大学计算机学院	17	221	7.0	14.0
2	王卓	西北工业大学计算机学院	4	44	2.0	4.0
3	索勃	西北工业大学计算机学院	2	31	1.0	2.0