Multilevel Graph Partitioning Based On Weighted Laplacian Method

Graph partitioning plays an important role in the field of graph processing,and it has a great influence on some more areas of computer science,such as computer vision and data mining.Due to the importance of large-scale graph partitioning problem in practice as well as its properties,the methods for large-scale graph partitioning are quite different from ones on small-size graphs,and it became a challenging task for decades.In order to improve the quality of graph partitioning and reduce the running time of a variety of graph partitioning algorithms,this dissertation is inspired by the multilevel graph partitioning framework and spectral clustering method,and we proposed a new graph partitioning method on large-scale graphs.The main work of this dissertation includes the following:(1)The graph partitioning on edge-weighted graphs or vertex-weighted graphs has been fully studied.Doubly-weighted graphs are some kinds of weighted graphs with weights on both edges and vertices.They have an important application in many prac-tical problems,such as path programming,the problem of best circles,which has not yet been fully studied.In this dissertation,we proposed the weighted Laplacian method,which solves the problem of graph partitioning on doubly-weighted graphs.Inspired by the spectral clustering method,this method uses the weighted Laplacian on the graph to deal with the minimum cut problem,where the weighted Laplacian is a generalization of the graph Laplacian.Under the help of weighted Laplacian,we transform the minimum cut problem on the doubly-weighted graph into an eigendecomposition problem,which is called the weighted Laplacian method.The k-partitioning on the doubly-weighted graph can be finally generated by calculating the first k smallest eigenvectors of the weighted Laplacian and then clustering these vectors.By studying the properties of weighted Laplacian as well as the Euler-Lagrange equation for calculating the mini-mum value of the cut,it is proved that the result produced by the method is the optimal solution of the relaxed graph partitioning problem.According to the related work of spectral clustering,it can be seen that the weighted Laplacian method almost always gives the optimal solution to the original graph partitioning problem.(2)We proved the equivalence among the balanced minimum cut problem,the minimum cut problem on the doubly-weighted graph,and the initial clustering problem,where the initial clustering problem is an intermediate problem derived by multilevel graph partitioning.This kind of equivalence shows that the minimum cut problem on the doubly-weighted graph is essentially a balanced minimum cut problem,and the initial clustering problem can be transformed into the minimum cut problem,thus the weighted Laplacian method can be used to study the initial clustering problem.We proposed a weighted spectral clustering algorithm based on the weighted Laplacian method,which fits the initial clustering stage of multilevel graph partitioning.Experimental results verified that the weighted spectral clustering algorithm always produced the best results in terms of partitioning quality,and it is also similar to the spectral clustering algorithm in terms of running time.(3)Furthermore,we proved that there exists a polynomial-time approximate al-gorithm for the minimum cut problem on the quasi-regular graph,which illustrates the best coarsening rules in the multilevel graph partitioning framework.Our proof used the regularity lemma on quasi-regular graphs,which shows that how to divided the quasi-regular graphs into a group of approximated random graph.The proof is con-structive,thus explained what is the form of the best coarsening rule on the quasi-regular graph in terms of partitioning quality of the original graph,which was also verified in our experimental results.