Research On Algorithms Of Graph Uniform Partition

The graph uniform partition problem is to divide the vertex set V of graph G into several parts of similar size V₁...,V_p,satisfying max_{i∈{1,2...P}}|V_i|≤（1+?）[n/p],?∈R_≥0,so that the cutting weight between each part is as small as possible.The problem of graph uniform partition is an important problem in graph theory and has important applications in many industrial fields.Developed by Karypis Laboratories,Metis software is cur-rently the most widely used graph partition solution tool which has perfect api support for C++and Fortran.More and more organizations hope to independently develop soft-ware for solving uniform partition of graph,so that considering their own needs,they can flexibly choose between the quality of solution results and the speed of solution.This paper aims to conducting algorithm research for the self-customized development of graph uniform partition solving software similar to Metis software,hoping to obtain similar partition results in less time than Metis software.In this paper,the algorithm is explored for small scale graph（100-200 points）and large scale graph（10,000-20,000 points）.A neighborhood search algorithm is proposed on small scale graph and random sampling is added in case of dense graph.In the exper-iment,on sparse graph,the running time of neighborhood search algorithm is reduced by 94.8%and the sum of cutting edge weight is increased by 3.8%on average com-pared with Metis.On dense graph,the running time of neighborhood search algorithm is reduced by 61.4%on average,andthe sum of cutting edge weight is reduced by 0.6%on average compared with Metis software.On sparse graph,the running time of the neighborhood search algorithm with random sampling is reduced by 90.4%,and the sum of cutting edge weight is increased by 4.1%compared with Metis software.On dense graph,the neighborhood search algorithm with random sampling reduces the running time of dense graph by 81.6%on average and the sum of cutting edge weight decreases by 0.2%on average compared with Metis software.On large scale graphs,a multi-level partition algorithm based on S3 contraction and a dynamic sequential streaming algorithm are proposed.In the experiment,the running time of multilevel partition algo-rithm is reduced by 14.3%on average,and the sum of cutting edge weight is increased by 3.3%on average compared with Metis software.The running time of dynamic se-quential streaming algorithm is reduced by 68.2%on average and the sum of cutting edge weight is increased by 5.6%on average compared with Metis software.