Speaker: Jure Leskovec Time: Wednesday 12-1pm Place: NSH 1507 Title: Realistic models for graphs over time Abstract: I will present our work on modeling temporal graph evolution. First, I will motivate the work by showing some surprising measurements on real data, and then we will see the graph models and their properties. We studied a wide range of real graphs/networks, and we observed some surprising phenomena. First, graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes shrinks over time, in contrast to the conventional wisdom that distance should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)). Next, we will explore models of graph generation that cause a graph to systematically densify, and to experience a decrease in effective diameter even as its size increases. We propose a graph generator that is mathematically tractable and matches this collection of properties. The main idea is 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 the properties of static and evolving graphs. I will conclude with a long list of open questions. :) This is joint work with Jon Kleinberg and Christos Faloutsos.