Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Analyzing the forest fire model
Speaker:Claire Mathieu
coming from:Ecole Normal Superieur, Paris
Speakers Bio:
Event Type:MPI Colloquium Series Distinguished Speaker
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 5 November 2015
Duration:60 Minutes
Building:E2.1 Center for Bioinformatics
Please note: New Room!
Distance in the Forest Fire Model How far are you from Eve?

Leskovec, Kleinberg and Faloutsos (2005) observed that many social
networks exhibit properties such as shrinking (i.e. bounded) diameter, densification, and
(power-law) heavy tail degree distributions. To explain these phenomena, they
introduced a generative model, called the Forest Fire model, and using
simulations showed that this model indeed exhibited these properties; however,
proving this rigorously was left as an open problem.

In this talk, we analyse one of these properties, shrinking diameter. We
define a restricted version of their model that incorporates the main features
that seem to contribute towards this property, and prove that the graphs
generated by this model exhibit shrinking distance to the seed graph. We prove that an even
simpler model, the random walk model, already exhibits this phenomenon.

This is joint work with Varun Kanade, Reut Levi, Zvi Lotker, and Frederik Mallmann-Trenn.

Claire Mathieu,
directrice de recherches CNRS et professeur attaché à l'ENS

Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Kurt Mehlhorn/AG1/MPII/DE, 07/10/2015 10:14 AM Last modified:Uwe Brahm/MPII/DE, 11/05/2015 07:01 AM
  • Christina Fries, 11/02/2015 03:48 PM
  • Kurt Mehlhorn, 07/21/2015 12:04 PM
  • Kurt Mehlhorn, 07/10/2015 10:16 AM
  • Kurt Mehlhorn, 07/10/2015 10:14 AM -- Created document.