An Improved Hill Climbing Algorithm for Graph Partitioning.

This article focuses on an improved hill climbing algorithm based on clustering for the graph partitioning problem, which aims to divide a graph into balanced partitions while minimizing the number of edges between them (edgecuts). The proposed algorithm, called IHCGP, treats clusters of highly connected vertices as units ("hills") to move during iterative refinement, using a new metric that adaptively balances edgecuts reduction and partition size balance. Experimental results on various real-world graphs demonstrate that IHCGP outperforms existing methods by effectively escaping local minima and achieving better tradeoffs between edgecuts and balance, particularly in graphs with high clustering coefficients. The study also analyzes parameter effects, scalability with respect to partition number and graph size, and robustness to randomness in label propagation, confirming IHCGP's efficiency and applicability to large-scale graph partitioning tasks.