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

Download PDF

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 \emph{pairwise $h$-attainability index} and \emph{$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.