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

Abstract: Mining frequent subgraphs in a single large-scale graph is of huge demand with the rapid growth of the social networking. However, it is inefficient for the serial algorithms to mine frequent subgraphs in low support when mining for a single large-scale graph. Meanwhile, few existing distributed algorithms can’t support the growth pattern mining, and the Hadoop framework they worked is not suitable for iterative running. In this paper, a distributed algorithm named FSMBUS for mining frequent subgraph in a single large-scale graph under Spark framework is proposed. It constructs the parallel computing candidate subgraphs by suboptimal CAM Tree, which returns all the frequent subgraphs for given user-defined minimum support. Additionally, infrequent patterns’ test and searching order chosen is introduced to optimize the algorithm. Sorted-Greedy method is designed for data partition to balance the workload. Our experiments show that FSMBUS runs faster and more effective than the existing algorithms with real datasets,and even can run with the lower support threshold and the larger graph datasets as well. At the same time, FSMBUS runs 2～4 times faster on Spark framework than that on Hadoop framework.

Key words: frequent subgraph, single large-scale graph, distribute mining, Spark, workload balance