Graph Partitioning Algorithms And Its Applications In Distributed Network Environment

Graph partitioning has extensive applications in the fields of science and engineering, including VLSI design, parallel computing, data mining and image segmentation, etc. The graph partitioning problem has been generally concerned by scholars at home and abroad and has been received considerable research. These researches can be categorized into two groups: some researches focus on developing graph partitioning algorithms, while others focus on the existing problems of graph partitioning application in different fields. The graph partitioning problem is NP-complete, which attracts the researchers to develop efficient algorithms for solving it constantly. In this thesis, we do a systematic review of the graph partitioning algorithms and the graph partitioning tools. We also do some research on several applications of graph partitioning in distributed network environment, such as parallel computing, industrial network optimization design and efficient storage of road network (spatial network) data. There are some problems when graph partitioning is used in these applications. Thus we propose the improved methods and models to solve these important problems by using0-1programming theory, nonlinear programming theory, combination optimization theory, clustering graph model, clustering hypergraph model and data aggregate technology, etc. We also give the corresponding verification algorithms and some experiments have been done to prove the correctness and effectiveness of the proposed methods and models. The main contributions of this thesis are as follows:(1) We do a systematic and completely review and summarization of the graph partitioning algorithms. Along with the development of graph partitioning problem and the further research, some recent research results on the graph partitioning algorithms and some popular graph partitioning tools are presented.(2) When graph partitioning is applied in distributed parallel computing systems, it can only express symmetric and bi-direction data dependencies. Thus a parallel computing graph partitioning model based on0-1programming is proposed. This model can express the applications of asymmetric and unidirectional dependencies, which can solve the limitations of the graph partitioning model. Moreover, the proposed model can accurately distinguish the sender and receiver of the communication. Some experimental results show that the proposed model can reduce communication volume averagely by5%and has small load imbalance comparing with standard graph partitioning model.(3) When standard graph partitioning model is employed in parallel computing, it can not accurately represent the communication volume and does not take into account the effects of communication latency and the distribution of the communication volume on parallel performance. Thus we give an improved graph partitioning model that uses boundary cuts as the cost metric, which can accurately represent the communication volume and can take into account the effects of communication latency and the distribution of the communication volume using a multi-object cost fuction. On that basis, we further extend the improved graph partitioning model and propose a more complicated model that is the improved hypergraph partitioning model. The improved hypergraph partitioning model not only can overcome the limitations of graph partitionging model but also can take into account the effects of communication latency and the distribution of the communication volume. We also propose the corresponding algorithms to verify the proposed models and some experimental results show the correctness and effectiveness of the proposed models.(4) In order to solve the industrial network optimization design problem in distributed network control, a nonlinear0-1program scheme is proposed to model the problem. The proposed model is then solved using NEOS server, a common optimization solver available over the Internet. The proposed approach can overcome the shortcomings of graph partitioning strategy, because the results obtained by graph partitioning scheme need to be further approximated to get the solution to the problem. The experiments on some data sets show that the nonlinear0-1program scheme is effective. For small-scale networks, nonlinear0-1programming scheme is generally better than graph partitioning strategy. Meanwhile, we propose the combination of nonlinear0-1program with graph partitioning strategy to solve the problem.(5) In order to aggregate query processing effectively in distributed traffic control, road network data should be organized and stored effectively. The state-of-the-art clustering graph model for allocation of data to disk pages is not able to correctly capture the disk access cost of successor retrieval operations. Thus an improved method based on clustering graph model is proposed, which uses boundary cuts to measure the cost of successor retrieval operations. Moreover, we utilize the query logs for predicting the future network usage frequencies and hence disk access patterns. Then graph partitioning is used to allocate the road network data to disk pages, resulting in increased efficiency and effectiveness in data organization and storage. So the cost of disk accesses during aggregate query processing can be reduced greatly and some experimental results demonstrate the effectiveness of the proposed method.