[Solomonov Seminar] 182. Solomonov seminar

[Marko Grobelnik]

Vabim vas na 182. Solomonov seminar, ki bo v torek 13. marca,
ob 13:00 uri v Veliki predavalnici IJS. Posnetke preteklih 
seminarjev najdete na naslovu http://videolectures.net/solomon/

Tokrat bomo gostili Jureta Leskovca - nasega cloveka, ki studira na 
Carnegie Mellon University v Pittsburghu. Predstavil bo svoje delo,
ki je bilo sicer objavljeno na vecih konferencah, na temo modeliranja
grafov oz. omreznih struktur. 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jure Leskovec:
         Modeling real-world networks using Kronecker multiplication

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.