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

IEEE Access

Yinglong Ma¹  Zhipeng Yang¹  Rongrong Zheng² 

[1] School of Control and Computer Engineering, North China Electric Power University, Beijing, China;State Grid Information and Telecommunication Group Company Ltd., Beijing, China;

关键词: Graph partitioning;    balanced graph partitioning;    parallel graph computing;    richness of implicit knowledge;    knowledge cohesion;   

DOI  :  10.1109/ACCESS.2019.2926753

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown