  We study the problem of graph clustering where the goal is to partition a
graph into clusters, i.e. disjoint subsets of vertices, such that each cluster
is well connected internally while sparsely connected to the rest of the graph.
In particular, we use a natural bicriteria notion motivated by Kannan, Vempala,
and Vetta which we refer to as {\em expander decomposition}. Expander
decomposition has become one of the building blocks in the design of fast graph
algorithms, most notably in the nearly linear time Laplacian solver by Spielman
and Teng, and it also has wide applications in practice.
  We design algorithm for the parametrized version of expander decomposition,
where given a graph $G$ of $m$ edges and a parameter $\phi$, our algorithm
finds a partition of the vertices into clusters such that each cluster induces
a subgraph of conductance at least $\phi$ (i.e. a $\phi$ expander), and only a
$\widetilde{O}(\phi)$ fraction of the edges in $G$ have endpoints across
different clusters. Our algorithm runs in $\widetilde{O}(m/\phi)$ time, and is
the first nearly linear time algorithm when $\phi$ is at least $1/\log^{O(1)}
m$, which is the case in most practical settings and theoretical applications.
Previous results either take $\Omega(m^{1+o(1)})$ time, or attain nearly linear
time but with a weaker expansion guarantee where each output cluster is
guaranteed to be contained inside some unknown $\phi$ expander. Our result
achieve both nearly linear running time and the strong expander guarantee for
clusters. Moreover, a main technique we develop for our result can be applied
to obtain a much better \emph{expander pruning} algorithm, which is the key
tool for maintaining an expander decomposition on dynamic graphs. Finally, we
note that our algorithm is developed from first principles based on relatively
simple and basic techniques, thus making it very likely to be practical.
