  This paper initiates the studies of parallel algorithms for core maintenance
in dynamic graphs. The core number is a fundamental index reflecting the
cohesiveness of a graph, which are widely used in large-scale graph analytics.
The core maintenance problem requires to update the core numbers of vertices
after a set of edges and vertices are inserted into or deleted from the graph.
We investigate the parallelism in the core update process when multiple edges
and vertices are inserted or deleted. Specifically, we discover a structure
called superior edge set, the insertion or deletion of edges in which can be
processed in parallel. Based on the structure of superior edge set, efficient
parallel algorithms are then devised for incremental and decremental core
maintenance respectively. To the best of our knowledge, the proposed algorithms
are the first parallel ones for the fundamental core maintenance problem. The
algorithms show a significant speedup in the processing time compared with
previous results that sequentially handle edge and vertex insertions/deletions.
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 algorithms.
