Balanced graph partitioning based on mixed 0-1 linear programming and iteration vertex relocation algorithm

Zhengxi Yang (), Zhipeng Jiang (), Wenguo Yang () and Suixiang Gao ()
Additional contact information
Zhengxi Yang: University of Chinese Academy of Sciences
Zhipeng Jiang: University of Chinese Academy of Sciences
Wenguo Yang: University of Chinese Academy of Sciences
Suixiang Gao: University of Chinese Academy of Sciences

Journal of Combinatorial Optimization, 2023, vol. 45, issue 5, No 11, 17 pages

Abstract: Abstract Graph partitioning is a classical NP problem. The goal of graphing partition is to have as few cut edges in the graph as possible. Meanwhile, the capacity limit of the shard should be satisfied. In this paper, a model for graph partitioning is proposed. Then the model is converted into a mixed 0-1 linear programming by introducing variables. In order to solve this model, we select some variables to design the vertex relocation model. This work designs a variable selection strategy according to the effect of vertex relocation on the number of local edges. For purpose of implementing graph partitioning on large scale graph, we design an iterative algorithm to solve the model by selecting some variables in each iteration. The algorithm relocates the shard of the vertex according to the solution of the model. In the experiment, the method in this paper is simulated and compared with BLP and its related methods in the different shard sizes on the five social network datasets. The simulation results show that the method of this paper works well. In addition, we compare the effects of different parameter values and variables selection strategies on the partitioning effect.

Keywords: Graph partitioning; 0-1 mixed linear programming; Iteration algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01051-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:5:d:10.1007_s10878-023-01051-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01051-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().