Multi-Level Refinement Algorithm of Weighted Hypergraph Partitioning Problem

Abstract

The formal description of weighted hypergraph partitioning problem is presented. We describe the solution of the weighted hypergraph partitioning problem based on the multi-level method. We propose the multi-level discrete particle swarm optimization refinement algorithm, whose each particle’s position in |V|-dimensional can be considered as the corresponded partitioning. During the refinement process of the uncoarsening phase, the algorithm projects successively each particle’s corresponded partitioning back to the next-level finer hypergraph, and the degree of particle’s freedom increases with the increase in solution space’s dimension. The algorithm also regards the gain of vertex as particle information for the heuristic search and successfully searches the solution space based on the intelligent behavior between individuals’ collaboration. Furthermore, the improved compressed storage format of weighted hypergraph is presented and the two-dimensional auxiliary array is designed for counting the vertices of each hypergraph in different partitions. The rapid method of calculating the vertex’s gain and the cut’s size are proposed to avoid traversing each vertex of hyperedge and reduce the algorithm’s time complexity and space complexity. Experimental results show that the algorithm not only can find the better partitioning of weighted hypergraph than the move-based method but also can improve the search capability of the refinement algorithm.

Keywords

• weighted hypergraph
• partitioning algorithm
• multilevel method
• refinement algorithm