 |
|
|
|
|
|
|
|
|
|
|
|
|
 |
|
|||||||||||
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
 |
 |
|
||||||||||
 |
|
|||||||||||
 |
|
|||||||||||
 |
 |
|
||||||||||
| Seminar Schedule (Seminar Organizer: Prof. Ziv Bar-Joseph) | |
Machine Learning Lunchtime Chats
|
Spring 2007 Seminar
Date: April 3, 2007 Time: 3:00 PM - 4:00 PM Location: 5409 Wean Hall Speaker: Jurij Leskovec PhD Candidate Title: Modeling Networks using Kronecker Multiplication Abstract: Inspired by the studies of networks such as the Internet, social networks, and biological networks researchers have developed a variety of techniques and models to help us understand or predict the behavior of these systems. In this talk I will present our recent findings on network evolution which motivated the development of Kronecker graph generative model that is easy to analyze and yet generates realistic networks. First, we show that Kronecker graphs naturally obey all the statistical properties found in real-world networks. Second, we present a fast and scalable algorithm for fitting the Kronecker graph generation model to real networks. While naive approach to fitting takes super-exponential time, our algorithm takes time linear in the number of edges. 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.