  Finding sparse cuts is an important tool in analyzing large-scale distributed
networks such as the Internet and Peer-to-Peer networks, as well as large-scale
graphs such as the web graph, online social communities, and VLSI circuits. In
distributed communication networks, they are useful for topology maintenance
and for designing better search and routing algorithms.
  In this paper, we focus on developing fast distributed algorithms for
computing sparse cuts in networks. Given an undirected $n$-node network $G$
with conductance $\phi$, the goal is to find a cut set whose conductance is
close to $\phi$. We present two distributed algorithms that find a cut set with
sparsity $\tilde O(\sqrt{\phi})$ ($\tilde{O}$ hides $\polylog{n}$ factors).
Both our algorithms work in the CONGEST distributed computing model and output
a cut of conductance at most $\tilde O(\sqrt{\phi})$ with high probability, in
$\tilde O(\frac{1}{b}(\frac{1}{\phi} + n))$ rounds, where $b$ is balance of the
cut of given conductance. In particular, to find a sparse cut of constant
balance, our algorithms take $\tilde O(\frac{1}{\phi} + n)$ rounds.
  Our algorithms can also be used to output a {\em local} cluster, i.e., a
subset of vertices near a given source node, and whose conductance is within a
quadratic factor of the best possible cluster around the specified node. Both
our distributed algorithm can work without knowledge of the optimal $\phi$
value and hence can be used to find approximate conductance values both
globally and with respect to a given source node. We also give a lower bound on
the time needed for any distributed algorithm to compute any non-trivial sparse
cut --- any distributed approximation algorithm (for any non-trivial
approximation ratio) for computing sparsest cut will take $\tilde
\Omega(\sqrt{n} + D)$ rounds, where $D$ is the diameter of the graph.
