The paper "Maximizing the Spread of Influence through a Social Network" from 2003, by David Kempe (CUCS PhD '03), Jon Kleinberg, and Eva Tardos has won one of three inaugural SIGKDD Test of Time Awards. This year's awards recognize outstanding papers from past KDD Conferences beyond the last decade that have had an important impact on the data mining research community.
The citation reads, "This paper considers questions involving the spread of information, innovations, and behaviors in social networks, providing algorithms with provable performance guarantees for a fundamental problem in this area: for promoting an innovation, what are the most effective starting points in the network? The paper identifies a technically rich structure inherent in the problem, and establishes a framework that has subsequently been used in areas ranging from social media and marketing to the diffusion of innovations and the study of inequality. At a mathematical level, it also establishes a link to the theory of submodular functions that has been central to subsequent research in this domain." Click Here