Research On Graph Partitioning Algorithms In Distributed Environment

Since the 1980 s,the study of complex systems has emerged,and it is considered to be an important breakthrough in solving the difficulties faced by research in various fields.Complex networks are an important tool for studying complex systems.For example,logistics,road planning,social networks,biological research,etc.can be abstracted into a complex network of edges and vertices,studied by means of related technologies of complex networks.But the basic units in the system often reach tens of thousands or even hundreds of millions,which makes the study of complex networks have to solve real-time,large-scale computing problems with efficient computing tools.Distributed computing technology is one of the most mature,widely used and most feasible computing acceleration technologies.Therefore,it is very important to study the distributed computing technology of complex networks.Before doing distributed computing,the original complex network needs to be divided into several sub-networks.How to ensure the relative balance of each sub-network and minimize the communication overhead between networks is the key to the performance of distributed computing.Graph partitioning technology is an effective means to solve this problem.Graph partitioning algorithm can be divided into point partitioning algorithm and edge partitioning algorithm according to different partitioning methods.The rapid growth of data sets new demands on the partitioning quality and efficiency of graph partitioning algorithm.The main work of this thesis is reflected in the following aspects:(1)For the current graph partition based on vertex-cut algorithm does not balance the relationship between partition quality and partition efficiency.This thesis proposes a streaming graph partitioning model based on sliding window(Graph Win).By introducing the sliding window mechanism,the model dynamically adjusts the amount of information(including vertex degree information and clustering information)referenced in each partition according to the current partition quality and partition time,so as to achieve the purpose of improving the partition quality as much as possible under the premise of ensuring the partition efficiency.In addition,the score function of Graph Win model is improved on the basis of traditional streaming partition algorithm.It includes adaptive balance score function,degree score function and clustering score function.The effects of balance,vertex degree and clustering coefficient of partition are considered comprehensively.The experimental results show that compared with other algorithms,Graph Win model can effectively reduce the average duplication to some extent.(2)For the current graph partition based on edge-cut algorithm is inefficient,this thesis proposes a fast graph partitioning model based on CPU(Graph GPU).Graph GPU model is divided into initial partitioning stage and optimal partitioning stage: In the initial stage,Boruvka algorithm is used to do initial clustering of original graph data,and the vertices with higher affinity are partitioned into the same partition as possible;in the optimal partitioning stage,bucket exchange algorithm is used to further optimize the initial partitioning results.Because Boruvka algorithm and bucket switching algorithm are parallel,Graph GPU model is based on CPU + GPU heterogeneous parallel computing framework.The experimental results show that compared with the existing mature graph partitioning algorithms,the Graph GPU model can improve the partitioning efficiency and reduce the edge-cutting rate.