Exact Vertex Migration Model of Graph Partitioning Based on Mixed 0–1 Linear Programming and Iteration Algorithm

Graph partitioning problem is a classical NP-hard problem. The improvement of graph partitioning results by vertex migration is an important class of methods for graph partitioning. The goal of graph partitioning is getting a partition with the least number of cut edges, while also satisfying the capacity limit of the partition. In this paper, an optimization model for vertex migration is proposed, considering the influence between neighboring vertices, so that the objective function value of the model is exactly equal to the amount of cut edge variation. The model is converted into a mixed 0–1 linear programming by introducing variables. Then, a heuristic iterative algorithm is designed, in which the mixed 0–1 linear programming model is transformed into a series of small-scale models that contain less integer variables. In the experiment, the method in this paper is simulated and compared with balanced label propagation methods and their related methods. The improvement effect of these methods based on three different initialization methods is analyzed. Extensive numerical experiments on five commonly used datasets validate the effectiveness and efficiency of the proposed method.