Multi-level spectral graph partitioning method. (27th September 2017)

• Record Type: Journal Article
• Authors: Fatih Talu, Muhammed
• Is Part Of: Journal of statistical mechanics. (2017:Sep.)
• Publication Date: 2017-09-27
• Subjects: 11; Statistical mechanics -- Periodicals; Mechanics -- Statistical methods -- Periodicals; 530.1305
• DOI: 10.1088/1742-5468/aa85ba
• Languages: English
• ISSNs: 1742-5468

Abstract

Abstract: In this article, a new method for multi-level and balanced division of non-directional graphs (MSGP) is introduced. Using the eigenvectors of the Laplacian matrix of graphs, the method has a spectral approach which has superiority over local methods (Kernighan–Lin and Fiduccia-Mattheyses) with a global division ability. Bisection, which is a spectral method, can divide the graph by using the Fiedler vector, while the recursive version of this method can divide into multiple levels. However, the spectral methods have two disadvantages: (1) high processing costs; (2) dividing the sub-graphs independently. With a better understanding of the eigenvectors of the whole graph, and by discovering the confidential information owned, MSGP can divide the graphs into balanced and multi-leveled without recursive processing. Inspired by Haar wavelets, it uses the eigenvectors with a binary heap tree. The comparison results in seven existing methods (some are community detection algorithms) on regular and irregular graphs which clearly demonstrate that MSGP works about 14, 4 times faster than the others to produce a proper partitioning result.