##
Distance in the Forest Fire Model — How far are you from Eve?

### Varun Kanade

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 work, 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.

Based on joint work with Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn
and Claire Mathieu.