Embodiments of the invention include methods for identifying one or more clusters in a streaming graph, the method includes receiving a stream of edges and sampling the stream of edges to create a structural reservoir and support reservoir. The method also includes creating a sampled graph from the structural reservoir and identifying the one or more clusters in the sampled graph by grouping one or more connected vertices in the sampled graph.