Local algorithms for distance-generalized core decomposition over large dynamic graphs

Qing Liu, Xuliang Zhu, Xin Huang, Jianliang Xu

Research output: Contribution to journalConference articlepeer-review

Abstract

The distance-generalized core, also called (k, h)-core, is defined as the maximal subgraph in which every vertex has at least k vertices at distance no longer than h. Compared with k-core, (k, h)-core can identify more fine-grained subgraphs and, hence, is more useful for the applications such as network analysis and graph coloring. The state-of-the-art algorithms for (k, h)-core decomposition are peeling algorithms, which iteratively delete the vertex with the minimum h-degree (i.e., the least number of neighbors within h hops). However, they suffer from some limitations, such as low parallelism and incapability of supporting dynamic graphs. To address these limitations, in this paper, we revisit the problem of (k, h)-core decomposition. First, we introduce two novel concepts of pairwise h-attainability index and n-order H-index based on an insightful observation. Then, we thoroughly analyze the properties of n-order H-index and propose a parallelizable local algorithm for (k, h)-core decomposition. Moreover, several optimizations are presented to accelerate the local algorithm. Furthermore, we extend the proposed local algorithm to address the (k, h)-core maintenance problem for dynamic graphs. Experimental studies on real-world graphs show that, compared to the best existing solution, our proposed algorithms can reduce the (k, h)-core decomposition time by 1-3 orders of magnitude and save the maintenance cost by 1-2 orders of magnitude.

Original languageEnglish
Pages (from-to)1531-1543
Number of pages13
JournalProceedings of the VLDB Endowment
Volume14
Issue number9
DOIs
Publication statusPublished - May 2021
Event47th International Conference on Very Large Data Bases, VLDB 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Scopus Subject Areas

  • Computer Science (miscellaneous)
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Local algorithms for distance-generalized core decomposition over large dynamic graphs'. Together they form a unique fingerprint.

Cite this