Parallel and Streaming Algorithms for K-Core Decomposition

Hossein Esfandiari, Silvio Lattanzi, Vahab Mirrokni
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1397-1406, 2018.

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 this Paper

BibTeX
@InProceedings{pmlr-v80-esfandiari18a, title = {Parallel and Streaming Algorithms for K-Core Decomposition}, author = {Esfandiari, Hossein and Lattanzi, Silvio and Mirrokni, Vahab}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1397--1406}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/esfandiari18a/esfandiari18a.pdf}, url = {https://proceedings.mlr.press/v80/esfandiari18a.html}, 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.} }
Endnote
%0 Conference Paper %T Parallel and Streaming Algorithms for K-Core Decomposition %A Hossein Esfandiari %A Silvio Lattanzi %A Vahab Mirrokni %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-esfandiari18a %I PMLR %P 1397--1406 %U https://proceedings.mlr.press/v80/esfandiari18a.html %V 80 %X 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.
APA
Esfandiari, H., Lattanzi, S. & Mirrokni, V.. (2018). Parallel and Streaming Algorithms for K-Core Decomposition. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1397-1406 Available from https://proceedings.mlr.press/v80/esfandiari18a.html.

Related Material