Efficient and Local Parallel Random Walks
  Random walks are a fundamental primitive used in many machine learning
algorithms with several applications in clustering and semi-supervised
learning. Despite their relevance, the first efficient parallel algorithm to
compute random walks has been introduced very recently (Lacki et al.).
Unfortunately their method has a fundamental shortcoming: their algorithm is
non-local in that it heavily relies on computing random walks out of all nodes
in the input graph, even though in many practical applications one is
interested in computing random walks only from a small subset of nodes in the
graph. In this paper, we present a new algorithm that overcomes this limitation
by building random walk efficiently and locally at the same time. We show that
our technique is both memory and round efficient, and in particular yields an
efficient parallel local clustering algorithm. Finally, we complement our
theoretical analysis with experimental results showing that our algorithm is
significantly more scalable than previous approaches.
