Parallel Graph Partitioning Framework for Solving the Maximum Clique Problem Using Hadoop

摘要

Graph pattern mining is an important part of the emerging social network science, and the research of the maximum clique problem is one of the most important research branches. In the big data environment, the mass of nodes and complexity of edges in the graph set a higher requirement on the speed and accuracy of the maximum clique (MCP) study. In this paper, we present a parallel graph partitioning framework for solving the maximum clique problem(PPMC) based on Hadoop. Firstly, This paper presents a new graph partition method based on degree sorting(GPD), the subgraph scale is greatly reduced. In order to balance the workload of solving the maximum clique problems. Secondly, the improved ant algorithm proposed by our team is used to solve the maximum clique of each subgraph. Finally, the framework is deployed on Hadoop distributed cloud computing platform and tested by Stanford large-scale datasets. The experimental results show that GPD algorithm can greatly reduce the subgraph scale, the subgraph number, and the complexity of time and space of solving the maximum clique problem of large-scale instances. And the efficiency and scalability of the Hadoop based parallel graph partitioning framework for solving the maximum clique problems has been further proved.