Research On The Large-scale Evolution Graph Data Partition Method Based On Vertex-Cut

In recent years, with the rapid development and prosperity of mobile applications and wireless networking technologies, as well as e-commerce, social network and other areas, the amount of Internet information is stored at the explosive rate, and has more close relationship with the natural world. Graph structure has the irreplaceable advantages in the current abstract representation of the natural world and receives extensive attention and research interest. This paper studies on the large-scale graphs and finds two characteristics: First, the power-law distribution of the structure, i.e. the degree of a small part of graph nodes is huge, and most nodes own low degree; the second is evolution of the time, i.e. the graph changes over time. They raise new challenges for graph structure processing.The research for large-scale graphs in this paper focus on the partitioning the graph in parallel and maintain the structure dynamically. First, this paper puts forward a partition method for large-scale graphs based on the vertex-cut heuristic parallel strategy which has high efficiency. And during the distributed partition process, this paper introduces the anti-entropy propagation communication algorithm to reduce the communication cost, and improve the effectiveness of the partition results.Second, for the evolution of the large-scale graph over time, this paper presents a partial adjustment strategy based on the sliding window to avoid the repartition of the whole graph which adapts to characteristics of the evolution of the large-scale graph, improves the efficiency and reduces the cost of system operation.Finally, experiments verify the result from the system efficiency and effectiveness of the methods and strategies above have the advantage of high efficiency, small communication cost, and partition results meet the application requirements; the dynamic maintenance strategy of evolution graph can sense the evolution trends timely to update the framework as to effectively balance the subgraph scale, improve system availability and reduce system communication cost.