2018/08/07 by Hossein Esfandiari, Silvio Lattanzi, Esfandiari, Hossein +3 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1808.02546
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.