## Scalable Modeling of Real Graphs using Kronecker Multiplication

author: Jure Leskovec, Computer Science Department, Stanford University
published: June 23, 2007,   recorded: June 2007,   views: 902
Categories
You might be experiencing some problems with Your Video player.

# Slides

0:00 Slides Modeling Real Graphs using Kronecker Multiplication Modeling large networks The problem Why is this important? Statistical properties of networks The model: Kronecker graphs Idea: Recursive graph generation Kronecker product: Graph Kronecker product: Definition Kronecker graphs Kronecker product: Graph Stochastic Kronecker graphs Kronecker graphs: Intuition Properties of Kronecker graphs Model estimation: approach Fitting Kronecker graphs Challenge 1: Node correspondence Challenge 2: calculating P(G|T,s) Model estimation: solution Solution 1: Node correspondence Sampling node correspondences Solution 2: Calculating P(G|T,s) Solution 2: Calculating P(G|T,s)01 Experiments: synthetic data Experiments: real networks AS graph (N=6500, E=26500) AS: comparing graph properties AS: comparing graph properties01 Epinions graph (N=76k, E=510k) Epinions graph (N=76k, E=510k)01

# Report a problem or upload files

If 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.

# Description

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? We propose to use "Kronecker graphs", which naturally obey all of the above properties, and we present KronFit, 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, KronFit takes linear time, by exploiting the structure of Kronecker product and by using sampling. Experiments on large real and synthetic graphs show that KronFit 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.