CMU team wins the ‘Test of Time’ award at KDD 2016 for their 2005 paper:

Graphs Over Time: Densification Laws, Shrinking Diameters and Possible Explanations
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos

KDD is the flagship conference for large-scale data mining. Jure was a phd student at SCS/MLD (and currently a professor at Stanford). Jon was visiting CMU for his sabbatical. The paper made the surprising discoveries that real graphs become denser over time, following a power-law pattern, and that their diameter shrinks (as opposed to growing slowly, that was the common wisdom until then). 

The paper had already received the ‘best research paper’ award in KDD 2005.