Parallel Algorithm for Core Maintenance in Dynamic Graphs

Abstract

This paper initiates the studies of parallel algorithm for core maintenance in dynamic graphs. The core number is a fundamental index reflecting the cohesiveness of a graph, which is widely used in large-scale graph analytics. We investigate the parallelism in the core update process when multiple edges and vertices are inserted. Specifically, we discover a structure called superior edge set, the insertion of edges in which can be processed in parallel. Based on the structure of superior edge set, an efficient parallel algorithm is then devised. To the best of our knowledge, the proposed algorithm is the first parallel one for the fundamental core maintenance problem. Finally, extensive experiments are conducted on different types of real-world and synthetic datasets, and the results illustrate the efficiency, stability and scalability of the proposed algorithm. The algorithm shows a significant speedup in the processing time compared with previous results that sequentially handle edge and vertex insertions.