Parallel Heuristics for Balanced Graph Partitioning Based on Richness of Implicit Knowledge

Abstract

Balanced graph partitioning (BGP) has a wide range of applications that involve many large-scale distributed data processing problems. However, most of the existing approaches to parallel graph partitioning neglect the problem of the richness of implicit knowledge (RIK) residing in big graph and the knowledge cohesion after graph partitioning. In this paper, we propose a parallel balanced graph partitioning framework called JA-BE-JA-RIK, which improves the original heuristic JA-BE-JA algorithm by evaluating RIK such that parallel BGP can be more efficiently made under the condition of obtaining the good edge-cut value and high knowledge cohesion. We introduce the concept about RIK and further present a quantitative measure to dynamically evaluate the RIK values during parallel BGP. Based on the Hadoop platform, we also implemented both frameworks and JA-BE-JA. The extensive experiments were made for illustrating efficacy of our JA-BE-JA-RIK approach in comparison with the traditional JA-BE-JA algorithm. The experimental results show that our parallel BGP approach can obtain the RIK value as higher as possible within a closer number of edge-cuts in comparison with the traditional JA-BE-JA algorithm.

Keywords

• Graph partitioning
• balanced graph partitioning
• parallel graph computing
• richness of implicit knowledge
• knowledge cohesion