  Designing effective algorithms for community detection is an important and
challenging problem in {\em large-scale} graphs, studied extensively in the
literature. Various solutions have been proposed, but many of them are
centralized with expensive procedures (requiring full knowledge of the input
graph) and have a large running time.
  In this paper, we present a distributed algorithm for community detection in
the {\em stochastic block model} (also called {\em planted partition model}), a
widely-studied and canonical random graph model for community detection and
clustering. Our algorithm called {\em CDRW(Community Detection by Random
Walks)} is based on random walks, and is localized and lightweight, and easy to
implement. A novel feature of the algorithm is that it uses the concept of {\em
local mixing time} to identify the community around a given node.
  We present a rigorous theoretical analysis that shows that the algorithm can
accurately identify the communities in the stochastic block model and
characterize the model parameters where the algorithm works. We also present
experimental results that validate our theoretical analysis. We also analyze
the performance of our distributed algorithm under the CONGEST distributed
model as well as the $k$-machine model, a model for large-scale distributed
computations, and show that it can be efficiently implemented.
