View article

Given an undirected connected graph G=(V, E) with vertex set V and edge set E, the minimum conductance graph partitioning problem is to partition V into two disjoint subsets such that the conductance, ie, the ratio of the number of cut edges to the smallest volume of two partition subsets is minimized. This problem has a number of practical applications in various areas such as community detection, bioinformatics, and computer vision. However, the problem is computationally challenging, especially for large problem instances. This work presents the first iterated multilevel simulated annealing algorithm for large-scale graph conductance minimization. The algorithm features a novel solution-guided coarsening method and an effective solution refinement procedure based on simulated annealing. Computational experiments demonstrate the high performance of the algorithm on 66 very large real-world sparse …