FSMBUS：一种基于Spark的大规模频繁子图挖掘算法

来源：计算机研究与发展杂志2015年第8期北京时间：

作者：严玉良,董一鸿,何贤芒,汪卫,

摘要：随着社交网络用户数的快速增加，大规模单图上频繁子图挖掘的需求越来越强烈.单机算法对大规模图的运行效率较低，难以支撑支持度较低的频繁子图的挖掘;现有的分布式环境下单图的频繁子图挖掘算法不支持子图增长模式的挖掘，它们所使用的Hadoop框架也不适合运行迭代式算法.提出了一种基于Spark的大规模单图频繁子图挖掘算法FSMBUS，通过次优树构建并行计算的候选子图，在给定最小支持度时挖掘出所有的频繁子图，并利用非频繁检测和搜索顺序选择实现优化，还设计了一种名为Sorted-Greedy的轻量级数据划分方法.实验结果表明，FSMBUS的效率要比现有单图上最新的算法快一个数量级，并支持更低最小支持度阈值以及更大规模图数据的挖掘，同时FSMBUS比其Hadoop的移植版要快2~4倍.

关键词：频繁子图, 大规模单图, 分布式挖掘, Spark, 负载均衡,