A Dynamic Graph Partition Method Based On Community Detection Algorithm

With the rapid development of the network,the amount of information based on the network is growing rapidly,which makes the scale of the graph also expand.Because large-scale graph data can not be processed in a single machine environment,distributed graph computing emerges as the times require.Distributed graph computing needs to distribute the graph data evenly to each node,and the reasonable partition of graph is the premise of distributed graph computing.The real world graph is in the process of continuous dynamic evolution.How to partition the dynamic graph reasonably is a research hotspots.Aiming at the problem of dynamic graph partitioning,the main contents of this paper are as follows:Firstly,we study the influence of the new graph community on the quality of dynamic graph partition.The updated vertex in the dynamic graph in a given period of time is regarded as a new graph,which is partitioned by different community discovery algorithms,and the subgraphs with different modularity are obtained.Through experiments,the partition results generated by different community discovery algorithms are compared.The results show that the greater the modularity,the stronger the community and the better the quality of dynamic graph partition.It is proved that the community of the new graph affects the quality of dynamic graph partition,which lays a foundation for the next step of designing dynamic graph partition method.Secondly,aiming at the problem of dynamic graph partition,a partition method based on community discovery is proposed.The basic idea is to collect a given number of graph update operations.For the join operation of vertices,the community discovery algorithm is used to pre-partition these vertices,and the community results generated by the pre-partition are inserted into the current graph that has been divided.The remaining vertex deletion and edge join/delete operations are updated in turn according to the collected information.Experiments on open data sets show that the number of cross edges and load balance of this method are reduced by 13%and 42.3%compared with the traditional streaming partition method.It can be concluded that the partition quality of this method is obviously better than that of the traditional stream partition method,and it can efficiently process the dynamic graph and reduce the communication overhead between subgraphs.Finally,in order to optimize the partition result of the dynamic graph,make the internal connection of the partitioned subgraphs close,the coupling degree between subgraphs is low,and avoid the re-partition of the whole dynamic graph,a dynamic graph vertex update method based on simulated annealing is proposed.Traditional vertex updating methods only judge whether the vertex position is transferred according to the adjacent nodes,which will result in local optimization.Based on the traditional vertex updating method,this method adds the factor of random disturbance.Through the design of energy function,update probability and cooling plan,it can avoid the result of vertex updating falling into local optimum,and make the connection edges between subgraphs minimum,so as to achieve the global optimum effect.Through experiments,this method is compared with the traditional vertex update method and the dynamic graph partition method based on community discovery.The results show that compared with the traditional vertex update method,this method reduces the number of crossed edges by 12.4%,and the load balance is reduced by 11.7.%.Compared with the dynamic graph partition method based on community discovery,the number of crossed edges is reduced by 9.3%,and the load balance degree is reduced by 2.2%.It can be obtained that the optimized method only achieves the partition of dynamic graphs through partial vertex position updates.Effectively avoid re-dividing the entire dynamic graph,and improve the quality of graph partition.