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.