Parallel and Streaming Algorithms for K-Core Decomposition
Abstract
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.
Cite
Text
Esfandiari et al. "Parallel and Streaming Algorithms for K-Core Decomposition." International Conference on Machine Learning, 2018.Markdown
[Esfandiari et al. "Parallel and Streaming Algorithms for K-Core Decomposition." International Conference on Machine Learning, 2018.](https://mlanthology.org/icml/2018/esfandiari2018icml-parallel/)BibTeX
@inproceedings{esfandiari2018icml-parallel,
title = {{Parallel and Streaming Algorithms for K-Core Decomposition}},
author = {Esfandiari, Hossein and Lattanzi, Silvio and Mirrokni, Vahab},
booktitle = {International Conference on Machine Learning},
year = {2018},
pages = {1397-1406},
volume = {80},
url = {https://mlanthology.org/icml/2018/esfandiari2018icml-parallel/}
}