Maintaining Top-$t$ Cores in Dynamic Graphs
Yikai Zhang, Jeffrey Xu Yu, Ying Zhang, Lu Qin · IEEE Transactions on Knowledge and Data Engineering · 2023
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.