Parallel Core Maintenance of Dynamic Graphs

A $k$ -core is the special cohesive subgraph where each vertex has at least $k$ degree. It is widely used in graph mining applications such as community detection, visualization, and clique discovery. Because dynamic graphs frequently evolve, obtaining their $k$ -cores via decomposition is inefficient. Instead, previous studies proposed various methods for updating $k$ -cores based on inserted (removed) edges. Unfortunately, the parallelism of existing approaches is limited due to their theoretical constraints. To further improve the parallelism of maintenance algorithms, we refine the $k$ -core maintenance theorem and propose two effective parallel methods to update $k$ -cores for insertion and removal cases. Experimental results show that our methods outperform the state-of-the-art algorithms on real-world graphs by one order of magnitude.