  The task of \emph{community detection} in a graph formalizes the intuitive
task of grouping together subsets of vertices such that vertices within
clusters are connected tighter than those in disparate clusters. This paper
approaches community detection in graphs by constructing Markov random walks on
the graphs. The mixing properties of the random walk are then used to identify
communities. We use coupling from the past as an algorithmic primitive to
translate the mixing properties of the walk into revealing the community
structure of the graph. We analyze the performance of our algorithms on
specific graph structures, including the stochastic block models (SBM) and LFR
random graphs.
