1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/games.R
\name{sample_forestfire}
\alias{sample_forestfire}
\title{Forest Fire Network Model}
\usage{
sample_forestfire(nodes, fw.prob, bw.factor = 1, ambs = 1, directed = TRUE)
}
\arguments{
\item{nodes}{The number of vertices in the graph.}
\item{fw.prob}{The forward burning probability, see details below.}
\item{bw.factor}{The backward burning ratio. The backward burning
probability is calculated as \code{bw.factor*fw.prob}.}
\item{ambs}{The number of ambassador vertices.}
\item{directed}{Logical scalar, whether to create a directed graph.}
}
\value{
A simple graph, possibly directed if the \code{directed} argument is
\code{TRUE}.
}
\description{
This is a growing network model, which resembles of how the forest fire
spreads by igniting trees close by.
}
\details{
The forest fire model intends to reproduce the following network
characteristics, observed in real networks: \itemize{ \item Heavy-tailed
in-degree distribution. \item Heavy-tailed out-degree distribution. \item
Communities. \item Densification power-law. The network is densifying in
time, according to a power-law rule. \item 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) \code{ambs} vertices already present
in the network, chosen uniformly random. Now, for each cited vertex \eqn{v}
we do the following procedure: \enumerate{ \item We generate two random
number, \eqn{x} and \eqn{y}, that are geometrically distributed with means
\eqn{p/(1-p)} and \eqn{rp(1-rp)}. (\eqn{p} is \code{fw.prob}, \eqn{r} is
\code{bw.factor}.) The new vertex cites \eqn{x} outgoing neighbors and
\eqn{y} incoming neighbors of \eqn{v}, from those which are not yet cited by
the new vertex. If there are less than \eqn{x} or \eqn{y} such vertices
available then we cite all of them. \item The same procedure is applied to
all the newly cited vertices. }
}
\note{
The version of the model in the published paper is incorrect in the
sense that it cannot generate the kind of graphs the authors claim. A
corrected version is available from
\url{http://www.cs.cmu.edu/~jure/pubs/powergrowth-tkdd.pdf}, our
implementation is based on this.
}
\examples{
fire <- sample_forestfire(50, fw.prob = 0.37, bw.factor = 0.32 / 0.37)
plot(fire)
g <- sample_forestfire(10000, fw.prob = 0.37, bw.factor = 0.32 / 0.37)
dd1 <- degree_distribution(g, mode = "in")
dd2 <- degree_distribution(g, mode = "out")
# The forest fire model produces graphs with a heavy tail degree distribution.
# Note that some in- or out-degrees are zero which will be excluded from the logarithmic plot.
plot(seq(along.with = dd1) - 1, dd1, log = "xy")
points(seq(along.with = dd2) - 1, dd2, col = 2, pch = 2)
}
\references{
Jure Leskovec, Jon Kleinberg and Christos Faloutsos. Graphs over
time: densification laws, shrinking diameters and possible explanations.
\emph{KDD '05: Proceeding of the eleventh ACM SIGKDD international
conference on Knowledge discovery in data mining}, 177--187, 2005.
}
\seealso{
\code{\link[=sample_pa]{sample_pa()}} for the basic preferential attachment
model.
Random graph models (games)
\code{\link{erdos.renyi.game}()},
\code{\link{sample_}()},
\code{\link{sample_bipartite}()},
\code{\link{sample_chung_lu}()},
\code{\link{sample_correlated_gnp}()},
\code{\link{sample_correlated_gnp_pair}()},
\code{\link{sample_degseq}()},
\code{\link{sample_dot_product}()},
\code{\link{sample_fitness}()},
\code{\link{sample_fitness_pl}()},
\code{\link{sample_gnm}()},
\code{\link{sample_gnp}()},
\code{\link{sample_grg}()},
\code{\link{sample_growing}()},
\code{\link{sample_hierarchical_sbm}()},
\code{\link{sample_islands}()},
\code{\link{sample_k_regular}()},
\code{\link{sample_last_cit}()},
\code{\link{sample_pa}()},
\code{\link{sample_pa_age}()},
\code{\link{sample_pref}()},
\code{\link{sample_sbm}()},
\code{\link{sample_smallworld}()},
\code{\link{sample_traits_callaway}()},
\code{\link{sample_tree}()}
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\concept{games}
\keyword{graphs}
\section{Related documentation in the C library}{\href{https://igraph.org/c/html/latest/igraph-Generators.html#igraph_forest_fire_game}{\code{igraph_forest_fire_game()}}.}
|
