Parallel Optimization Of All-pairs Shortest Distances Maintenance Algorithm For Dynamic Large Graph

The shortest path problem of all point pair has an important application in social network,biological network and network routing processing.Most of the methods proposed in the literature are aimed at static graph.In the application scenarios where edge and weight need to change frequently,a large number of repeated calculations will bring unnecessary overhead.For this reason,many researches focus on the shortest distance of dynamic graph,among which all pairs shortest distances for batch inserts / deletions incremental maintenance algorithm is supported Algorithm(APSDs algorithm)is a new and efficient method to deal with the whole point to the shortest distance maintenance problem of dynamic graph.This algorithm is based on disk and supports the processing of large graph(the number of vertices exceeds 10000).APSDs algorithm needs to do path extension and calculate distance iteratively on the basis of the edge set inserted / deleted in batch,find the point pair whose shortest distance changes(detection stage)and update its shortest distance(update stage).The whole path extension is realized by BFS.Therefore,with the increase of graph scale,the cost of the algorithm increases significantly(the time complexity of each insertion / deletion edge level traversal reaches o(n ^ 2)),so this paper considers optimizing the original APSDs algorithm in the multi-threaded environment.The basic parallel partition ideas and methods are as follows(the specific partition should be based on the premise of ensuring the correctness of the algorithm):(1)The original APSDs algorithm needs to do BFS.If the graph is divided,it needs to be non connected graph,but the graph studied in this paper has no limitation on connectivity.Therefore,the input data of each sub process(stage)in the algorithm is divided.Finally,this parallel algorithm is implemented on the parallel computing model based on shared storage.Due to the different access logic of public resources(the shortest distance of all point pairs)for batch insertion and batch deletion,different parallel methods are given in this paper.(2)The parallel method of APSDs batch insertion algorithm: the update phase of the batch insertion is in the detection phase.This paper uses the local characteristics of the algorithm for reading and writing public resources(within the range of point pairs of the extended path and the merged path)to execute the whole iterative process in parallel,and gives two partition schemes under different application scenarios.(3)Parallel method of APSDs batch deletion algorithm: different from(2),the algorithm has global read and write of public resources in the detection phase,so it can’t parallel the whole iteration,only parallel processing can be done for each iteration process.The read and write logic of public resources in the update phase is similar to(2),and parallel processing can be done for the whole iteration.Finally,the parallel algorithm is verified in the open data set.The experimental results show that:(1)it has better acceleration effect in the case of large-scale graph;(2)the acceleration ratio increases with the increase of insert / delete edge set,and tends to be flat when reaching a certain scale.