igraph (version 0.5.5-2)

forest.fire.game: Forest Fire Network Model

Description

This is a growing network model, which resembles of how the forest fire spreads by igniting trees close by.

Usage

forest.fire.game (nodes, fw.prob, bw.factor = 1, ambs = 1, directed = TRUE, 
    verbose = igraph.par("verbose"))

Arguments

nodes

The number of vertices in the graph.

fw.prob

The forward burning probability, see details below.

bw.factor

The backward burning ratio. The backward burning probability is calculated as bw.factor*fw.prob.

ambs

The number of ambassador vertices.

directed

Logical scalar, whether to create a directed graph.

verbose

Logical scalar, whether to draw a progress bar.

Value

• A simple graph, possibly directed if the directed argument is TRUE.

concept

• Random graph model
• Forest fire model

Details

The forest fire model intends to reproduce the following network characteristics, observed in real networks:

• Heavy-tailed in-degree distribution.
• Heavy-tailed out-degree distribution.
• Communities.
• Densification power-law. The network is densifying in time, according to a power-law rule.
• Shrinking diameter. The diameter of the network decreases in time.

The network is generated in the following way. One vertex is added at a time. This vertex connects to (cites) ambs vertices already present in the network, chosen uniformly random. Now, for each cited vertex $v$ we do the following procedure:

1. We generate two random number,$x$and$y$, that are geometrically distributed with means$p/(1-p)$and$rp(1-rp)$. ($p$isfw.prob,$r$isbw.factor.) The new vertex cites$x$outgoing neighbors and$y$incoming neighbors of$v$, from those which are not yet cited by the new vertex. If there are less than$x$or$y$such vertices available then we cite all of them.
2. The same procedure is applied to all the newly cited vertices.

References

Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. KDD '05: Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, 177--187, 2005.

See Also

barabasi.game for the basic preferential attachment model.

Examples

g <- forest.fire.game(10000, fw.prob=0.37, bw.factor=0.32/0.37)
dd1 <- degree.distribution(g, mode="in")
dd2 <- degree.distribution(g, mode="out")
if (interactive()) {
  plot(seq(along=dd1)-1, dd1, log="xy")
  points(seq(along=dd2)-1, dd2, col=2, pch=2)
}