Modeling real-world networks using Kronecker multiplication
published: March 20, 2007, recorded: March 2007, views: 1748
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
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.
Download slides: leskovec_jure.ppt (2.2 MB)
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !