Analyzing the forest fire model

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