CMU team wins ‘test of time’ award in ECML/PKDD 2015
The paper details are:
- Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, Christos Faloutsos:
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication. ECML/PKDD 2005: 133-145
ECML/PKDD is one of the top data mining conferences. Both Jure and Deepayan were SCS phd students in 2005, advised by Christos, while Jon was on sabbatical at CMU. Both Jure and Deepayan are now tenure-track faculty, at Stanford and U.Texas-Austin, respectively.
The paper showed how to generate realistic graphs, using recursion and self-similarity. Not only the resulting graphs obey several “power laws” that real graphs obey, but they also have a very simple, recursive mechanism, the so-called Kronecker matrix multiplication, that has been studied extensively, and leads to simple and elegant proofs about the graph properties. Its simpler version, “RMAT” is the basis behind the graph500 benchmark which is used to generate benchmarks for supercomputer competitions on graph analytics.