Research And Implementation Of Incremental Graph Partition Based On Distributed Environment

With the continuous development of the Internet,the network continues to expand,And then forming a number of large-scale network graph.The research on these graphs has become a trend.However,because the scale of the graph is very large,the single machine can not meet the demand of graph computing,we turn to the distributed clusters to solve the problem of large-scale graph computation.Before distributed graph calculation,we firstly need to divide the graph into multiple subgraphs.In order to ensure the load balance,we need to ensure the size of each partition is generally same.At the same time,in order to reduce the communication between the various nodes,we need to ensure that the cutting edge between the various partitions as little as possible.In addition,we are faced with not only the problem of large-scale graph,in many cases,the structure of the graph evolved along with time continuously.This means that we can not re-divide the whole graph as soon as the structure of the graph changes,because of expensive computational cost and long off-line processing time.When the scale of the graph becomes very large,the graph partitioning task will not be able to continue.Therefore,the research on distributed incremental graph partitioning algorithm is very important.In this paper,a large-scale incremental graph partitioning algorithm is analyzed in detail,the details are as follows:Based on the characteristics of the incremental graph,when the structure of the graph changes,this paper does not re-divide the whole graph.But only move and adjust affected nodes.This way will greatly reduces the time consumption of graph partitioning.ur method consider four different modification events of incremental graph partitioning.This way ensure the load balance and as far as possible to reduce cutting edge.On the basis of the above-mentioned strategy,this paper adopts tabu search algorithm to avoid the local optimal solution as far as possible.The above strategy is a heuristic method based on greedy algorithm,which is most likely trapped in the trap of local optimal solution.We adopt the tabu search algorithm,which makes the node movement process jump out of the local optimal solution trap as much as possible through multiple iterations and taboo rule restrictions.Finally,a distributed incremental graph partitioning system is designed on the basis of the above model,and the effectiveness and feasibility of the system are verified by experiments.