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.
