Research On Core Maintenance Algorithms Of Symmetry Breaking In Large Scale Graphs

Symmetry breaking is an important research direction of distributed algorithms.In recent years,the problem of core maintenance has been widely studied in the field of physics as the subproblem of symmetric breaking.Previous core maintenance algorithm cannot efficiently handle the case of the insertion/deletion of vertices.In particular,the matching based algorithms can process one edge associated to a vertex in each iteration and the superior edge based algorithms can only process one superior edge associated to a vertex in each iteration.In the case of the insertion/deletion of vertices,the edges associated to these vertices must be processed through multiple iterations.This will result in redundant computation and make the algorithms inefficient.In order to solve the limitations of the previous algorithms,a structure called joint edge set is proposed.The joint edge set structure preferentially processes high superior degree vertices and ensure that all edges associated to these vertices can be processed in one iteration.Theoretical proof shows that the insertion/deletion of a joint edge set makes each vertex change its core number by at most 1.Compared with the matching or superior edge set structure,the joint edge set structure requires fewer iterations to maintain vertices' core number which need less redundant computations.After dividing the joint edge set to disjoint edge sets,the disjoint edge set can be processed by different threads to take advantage of the multicore processes.In addition,the distributed core maintenance problem can be easily solved using the conclusions obtained in the joint edge set structure.The proposed distributed core maintenance algorithm need fewer rounds and less communication overhead.A large number of experimental results on real-world,synthetic and temporal graphs show that the joint edge set based algorithms can achieve high performance,stability and scalability.Compared with the matching based and superior edge based algorithms,the joint edge set based algorithms show a significant speedup up to 60 x in the processing time in the case of insertion.In addition,the proposed distributed core maintenance algorithm can effectively reduce the number of rounds and communication overhead compared with the distributed core decomposition algorithm.