Research On Partition Methods On Large-Scale Dynamic Graph Based On Multi-Level Division

The graph structure is widely used in many fields such as social network,biological information network and intelligent transportation network,etc.because it can represent the relationship among entities in the real world accurately.With the rapid development of information technology,the graph data scale is becoming increasingly,and the distributed parallel computing becomes the effective way to solve the large-scale graph data processing.However the premise of applying distributed parallel computing is how to partition the graph and assign to a number of computers quickly and effectively,and ensure load balancing as far as possible,avoid the waste of storage space caused by the large deviation.At the same time,the real applications,the figure is often dynamic change over time,how to effectively the large-scale dynamic figure segmentation becomes the key to processing graph data,and thus become one of the highlights in agro-scientific research in the current map data processing technology.This article in view of the current map segmentation problem carried on the thorough studies have found that in the current data growth background,the scale and speed of segmentation result map segmentation efficiency,and the segmentation of redundant storage,etc,put forward the higher request,the existing image segmentation methods have been unable to effectively solve large-scale dynamic graph partition problem.In view of the above problems,this paper,based on two adjacent moments,has a transient smoothing effect of certain similarity in the partition structure of the graph,and the dynamic graph segmentation problem is divided into two stages to solve.Firstly,based on the initial static graph structure,and based on the hierarchical division thought frame,some nodes exchange algorithms are proposed to divide.Secondly for dynamic graph structure,the solution is to time T,for the unit to collect the dynamic changes of the figure in T time slice and identify whether these changes involves the boundary nodes,and gives the corresponding logical mobile strategy,finally have to dynamic optimization algorithm is used to change the logic to adjust the mobile strategy results so as to adapt to the figure collected node or edge of change.The whole process of this algorithm is called MPA.For large-scale dynamic graph partition problems,MPA method proposed in this paper through the compression and reduction,to a certain extent,effectively solve the problem of large scale figure segmentation,as far as possible to ensure each compute node load balancing,and reduce calculation process by redundant storage storage space waste problem,and the final segmentation result of quality is improved.