In one general embodiment, a computer-implemented method is provided for analyzing a dynamic graph. The computer-implemented method includes generating two or more sample graphs by sampling edges of a current snapshot of a dynamic graph. Additionally, the computer-implemented method includes generating two or more partial results by executing an algorithm on the sample graphs. Still yet, the computer-implemented method includes combining the partial results, from executing the algorithm on the sample graphs, into a final result.