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(\varDelta (G)))\) where M(n) is the complexity of \(n\times n\) matrix multiplication and \(\varDelta (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.