Given a large, real graph, how can we generate a synthetic graph that matches its properties, i.e., it has similar degree distribution, similar (small) diameter, similar spectrum, etc?

First, we propose a graph generator that is mathematically tractable and generates realistic graphs. 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 all the above properties; in fact, we can rigorously prove that they do so.

Once we have the model, we fit it to real graph to generate a synthetic graph that matches its properties, i.e., it has similar degree distribution, similar (small) diameter, similar spectrum, etc?

We present a fast and scalable algorithm for fitting the Kronecker graph generation model to real networks. A naive approach to fitting would take super-exponential time. In contrast, our algorithm takes linear time, by exploiting the structure of Kronecker matrix multiplication and by using sampling.

Experiments on large real and synthetic graphs show that our approach recovers the true parameters and indeed mimics very well the patterns found in the target graphs. Once fitted, the model parameters and the resulting synthetic graphs can be used for anonymization, extrapolations, and graph summarization.

The presentation starts in Slovenian language and switches to English a few minutes into the lecture.
Another lecture on the same topic can be found at Scalable Modeling of Real Graphs using Kronecker Multiplication.