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

doi:10.1007/s40305-023-00534-9

Abstract

Abstract: 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.

Key words: Graph partitioning, Mixed 0–1 linear programming, Vertex migration

CLC Number:

Zheng-Xi Yang, Zhi-Peng Jiang, Wen-Guo Yang, Sui-Xiang Gao. Exact Vertex Migration Model of Graph Partitioning Based on Mixed 0-1 Linear Programming and Iteration Algorithm[J]. Journal of the Operations Research Society of China, 2025, 13(4): 919-945.

TrendMD

References

[1] Newman, M.E.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)
[2] Peng, B., Zhang, L., Zhang, D.: A survey of graph theoretical approaches to image segmentation. Pattern Recogn. 46(3), 1020–1038 (2013)
[3] Kahng, A.B., Lienig, J., Markov, I.L., Hu, J.: VLSI physical design-from graph partitioning to timing closure (2011). http://vlsicad.eecs.umich.edu/KLMH/downloads/book/chapter5/chap5-111206.pdf
[4] Boyd, D.M., Ellison, N.B.: Social network sites: definition, history, and scholarship. J. Comput. Mediat. Commun. 13(1), 210–230 (2007)
[5] Pothen, A., Simon, H.D., Liou, K.-P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11(3), 430–452 (1990)
[6] Hungershöfer, J., Wierum, J.-M.: On the quality of partitions based on space-filling curves. In: International Conference on Computational Science, pp. 36–45. Springer (2002)
[7] Abbas, Z., Kalavri, V., Carbone, P., Vlassov, V.: Streaming graph partitioning: an experimental study. Proc. VLDB Endow. 11(11), 1590–1603 (2018)
[8] Duong, Q., Goel, S., Hofman, J., Vassilvitskii, S.: Sharding social networks. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pp. 223–232 (2013)
[9] Karypis, G., Kumar, V.: Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices (1997). https://api.semanticscholar. org/CorpusID:7458399
[10] Lisser, A., Rendl, F.: Graph partitioning using linear and semidefinite programming. Math. Program. 95, 91–101 (2003)
[11] Jovanovic, R., Voß, S.: A mixed integer program for partitioning graphs with supply and demand emphasizing sparse graphs. Optimiz. Lett. 10, 1693–1703 (2016)
[12] Miyazawa, F.K., Moura, P.F.S., Ota, M.J., Wakabayashi, Y.: Integer programming approaches to balanced connected k-partition. arXiv:1911.05723 (2019)
[13] Fan, N., Pardalos, P.M.: Linear and quadratic programming approaches for the general graph partitioning problem. J. Global Optim. 48, 57–71 (2010)
[14] Fan, N., Zheng, Q.P., Pardalos, P.M.: On the two-stage stochastic graph partitioning problem. In: COCOA (2011). https://doi.org/10.1007/978-3-642-22616-8_39
[15] Henzinger, A., Noe, A., Schulz, C.: Ilp-based local search for graph partitioning. J. Exp. Algorithm. (JEA) 25, 1–26 (2018)
[16] Moussawi, A.E., Seghouani, N.B., Bugiotti, F.: Bgrap: Balanced graph partitioning algorithm for large graphs (2021). https://doi.org/10.26421/JDI2.2-2
[17] Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49(2), 291–307 (1970)
[18] Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: 19th Design Automation Conference, pp. 175–181. IEEE (1982)
[19] Ugander, J., Backstrom, L.: Balanced label propagation for partitioning massive graphs. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pp. 507–516 (2013)
[20] Sanders, P., Schulz, C.:Thinklocally, actglobally:highlybalancedgraphpartitioning.In:International Symposium on Experimental Algorithms, pp. 164–175. Springer (2013)
[21] Deng, Z., Suel, T.: Optimizing iterative algorithms for social network sharding. In: 2021 IEEE International Conference on Big Data (Big Data), pp. 400–408. IEEE (2021)
[22] Karp, R.M.: Reducibility among combinatorial problems. In: 50 Years of Integer Programming (1972). https://link.springer.com/chapter/10.1007/978-3-540-68279-0_8
[23] Lawler, E.L., Wood, D.E.: Branch-and-bound methods: a survey. Oper. Res. 14, 699–719 (1966)
[24] Nemhauser, G.L., Wolsey, L.A.: Integer and combinatorial optimization. In: Wiley Interscience Series in Discrete Mathematics and Optimization (1988). https://dl.acm.org/doi/book/10.5555/42805
[25] Mitchell, J.E.: Branch-and-cut algorithms for combinatorial optimization problems (1988). https://doi.org/10.1002/9780470400531.eorms0117
[26] Marinescu, R., Dechter, R.: Evaluating the impact of and/or search on 0–1 integer linear programming. Constraints 15(1), 29–63 (2010)
[27] Munapo, E.: Solving the binary linear programming model in polynomial time. Am. J. Oper. Res. 6(1), 1–7 (2016)
[28] Leskovec, J., Krevl, A.: SNAP Datasets. http://snap.stanford.edu/data/(2014)