1. OPUS at UTS
  2. Faculty of Engineering and Information Technology
  3. General Collection

Maintaining Top-<inline-formula><tex-math notation="LaTeX">$t$</tex-math></inline-formula> Cores in Dynamic Graphs

Publisher:
Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:
Journal Article
Citation:
IEEE Transactions on Knowledge and Data Engineering, 2023, PP, (99), pp. 1-14
Issue Date:
2023-01-01
Closed Access
Filename Description Size
Maintaining_Top-t_Cores_in_Dynamic_Graphs_published_early access.pdfAccepted version931.33 kB
Adobe PDF
Copyright Clearance Process
  • Recently Added
  • In Progress
  • Closed Access
This item is closed access and not available.
Full metadata record
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.
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10453/176047

Faculty of Engineering and Information Technology
General Collection