TY - JOUR

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

AU - Liu, Qing

AU - Zhu, Xuliang

AU - Huang, Xin

AU - Xu, Jianliang

N1 - Funding Information:
This work is supported by Research Grants Council of Hong Kong under GRF/ECS Projects 22200320, 12200819, 12200917, CRF Project C6030-18GF, and Guangdong Basic and Applied Basic Research Foundation (Project No. 2019B1515130001). Jianliang Xu is the corresponding author.
Publisher Copyright:
© by the owner/author(s).

PY - 2021/5

Y1 - 2021/5

N2 - 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.

AB - 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.

UR - http://vldb.org/pvldb/vol14-volume-info/

UR - http://www.scopus.com/inward/record.url?scp=85115151967&partnerID=8YFLogxK

U2 - 10.14778/3461535.3461542

DO - 10.14778/3461535.3461542

M3 - Conference article

AN - SCOPUS:85115151967

SN - 2150-8097

VL - 14

SP - 1531

EP - 1543

JO - Proceedings of the VLDB Endowment

JF - Proceedings of the VLDB Endowment

IS - 9

T2 - 47th International Conference on Very Large Data Bases, VLDB 2021

Y2 - 16 August 2021 through 20 August 2021

ER -