The paper "Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication" by Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and Christos Faloutsos has won the Test of Time Award from the 2015 ECML/PKDD conference.
The paper states, "How can we generate realistic graphs? In addition, how can we do so with a mathematically tractable model that makes it feasible to analyze their properties rigorously? Real graphs obey a long list of surprising properties: ... All published graph generators either fail to match several of the above properties, are very complicated to analyze mathematically... Here we propose ... to use a non-standard matrix operation, the Kronecker product, to generate graphs that we refer to as “Kronecker graphs”. We show that Kronecker graphs naturally obey all the above properties."
(Aside: see Charlie Van Loan's J. Computational and Applied Math. paper "The ubiquitous Kronecker product" open archive)
ECML/PKDD is a federated conference that brings together the European Conference on Machine Learning with the conference on Principles and Practice of Knowledge Discovery in Databases.
The award is designed to recognize the impact over time of a paper that first appeared at the ECML/PKDD conference ten years earlier.
