Maintaining Top-$t$ Cores in Dynamic Graphs

Yikai Zhang, Jeffrey Xu Yu, Ying Zhang, Lu Qin

Abstract

Graphs have been widely used in many applications. One important graph analytics is to explore cohesive subgraphs in a large graph. Among several cohesive subgraphs studied, $k$-core is one that can be computed in linear time for a static graph. Since graphs are evolving in real applications, in this paper, we study core maintenance which is to reduce the computational cost to compute $k$-cores for a graph when graphs are updated from time to time dynamically. We identify drawbacks of the existing efficient algorithm, which needs a large search space to find the vertices that need to be updated, and has high overhead to maintain the index built, when a graph is updated. We propose a new order-based approach to maintain an order, called $k$-order, among vertices, while a graph is updated. Our new algorithm can significantly outperform the state-of-the-art algorithm up to 3 orders of magnitude for the 11 large real graphs tested. In addition, we also study the problem of partial core maintenance, which is to maintain the top-$t$ cores of the graph for a given positive integer $t$. By instead maintaining only a small subset of cores, further improvement in performance can be obtained.
BibTeX
@article{zhang2024maintaining,
  author = {Yikai Zhang and Jeffrey Xu Yu and Ying Zhang and Lu Qin},
  title = {{Maintaining Top-$t$ Cores in Dynamic Graphs}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2024},
  doi = {10.1109/tkde.2023.3332638},
}

Loading related content...

Figure