Column Generation Algorithms for the Minimum Normalized Cuts problem
This talk deals with the k-way normalized cut problem in complex networks. It presents a methodology using mathematical optimization to provide mixed integer linear programming formulations for the problem. The paper also develops a branch-and-price algorithm for the above mentioned problem which scales better than the compact formulations. Additionally, it is also presented a heuristic algorithm able to approximate large scale problems in those cases where the exact methods are not applicable. Extensive computational experiments assess the usefulness of these methods to solve the k-way normalized cut problem. Finally, a case study is reported on the segmentation of actual images showing the applicability of the methods in this paper to detect community structures in graphs.
Keywords: Normalized cuts Complex networks Community detection Mathematical programming Image segmentation