Research On Distributed Partitioning And Path Finding Algorithms For Large-Scale Natural Graph

Recently,graph computing has been widely used in many fields.With the increase of graph data scale,distributed graph computing systems have become an effective tool for processing large-scale graph.Graph partitioning is basis of distributed graph computation,but most partitioning algorithms don't consider natural graph's typical power-law characteristics,resulting in poor partition quality.The real graph data is usually a natural graph with the power-law distribution,and the existing distributed graph partitioning algorithms cannot meet demand.Therefore,this thesis studies the partitioning problem in large-scale natural graph.The main contributions and innovations of this thesis are as follows.(1)It proposes a hierarchical partitioning algorithm based on the degrees of vertices.In this thesis,the structural features and data locality of the natural graph are fully utilized.Those vertices with high degrees are taken as the core,and the hierarchical partitions are sequentially performed according to their neighboring vertices.(2)It proposes a vertices transfer algorithm based on simulated annealing.In view of two shortcomings of the traditional vertex transfer strategy:easy to fall into local optimal and invalid transfer,this thesis introduces simulated annealing algorithm to optimize the initial partitioning result.(3)It studies the path finding problems in personal computer and distributed environments.Firstly,aiming at the circuit finding problem of large-scale sparse directed graphs under ordinary PC,a parallel algorithm based on multi-threading is proposed.Then,for the distributed graph computing framework GraphX,another algorithm based on the hierarchical partitioning algorithm to find the shortest path is proposed.(4)It applies the proposed algorithms in analysis of enterprise debt data.This thesis models the enterprise debt relationship,and applies the circuit finding algorithm to debt problem for real enterprise data.This thesis performs experiments to verify the feasibility and effectiveness of the proposed algorithms.The results show that the proposed algorithm can solve the problem of graph partitioning and path finding problems for large-scale natural graphs effectively.