# Parallel and Streaming Algorithms for K-Core Decomposition

arXiv: https://arxiv.org/abs/1808.02546 · HTML: https://mlsanity.com/paper/1808.02546/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2018.

## Built on by (most cited first, 2 of 2)

- [Where Do We Go From Here? Guidelines For Offline Recommender Evaluation](https://mlsanity.com/paper/2211.01261/) (2022)
- [K-Core Decomposition on Super Large Graphs with Limited Resources](https://mlsanity.com/paper/2112.14840/) (2021)

## Abstract (arXiv)

The k-core decomposition is a fundamental primitive in many machine learning and data mining applications. We present the first distributed and the first streaming algorithms to compute and maintain an approximate k-core decomposition with provable guarantees. Our algorithms achieve rigorous bounds on space complexity while bounding the number of passes or number of rounds of computation. We do so by presenting a new powerful sketching technique for k-core decomposition, and then by showing it can be computed efficiently in both streaming and MapReduce models. Finally, we confirm the effectiveness of our sketching technique empirically on a number of publicly available graphs.