Parallel Core Maintenance of Dynamic Graphs
Wen Bai, Yuncheng Jiang, Yong Tang, Yayang Li
Abstract
A <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -core is the special cohesive subgraph where each vertex has at least <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> degree. It is widely used in graph mining applications such as community detection, visualization, and clique discovery. Because dynamic graphs frequently evolve, obtaining their <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -cores via decomposition is inefficient. Instead, previous studies proposed various methods for updating <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -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 <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -core maintenance theorem and propose two effective parallel methods to update <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -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.