Clustering graphs, where the number of triangles is a constant fraction of the number of paths of length $2$, appear frequently in real-world networks. Recently Chung showed that general clustering graphs are surprisingly structured in that they admit a regularity lemma; every clustering graph can be decomposed into a bounded number of random-like parts. We show that the regularity partition for clustering graphs can be computed in time $O(nM(\Delta(G)))$ where $M(n)$ is the complexity of $n\times n$ matrix multiplication and $\Delta(G)$ is the maximum degree of the graph. In particular, we show that it is possible to efficiently find subcommunities of a clustering graph which have robust clustering; even after removing many edges, the subcommunity has a large clustering coefficient. Our algorithm is parallelizable and can be implemented in $NC^2$. As a consequence of the proof, we show that sparse clustering graphs are closely related to dense quasirandom graphs.