Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs

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.