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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/games.R
\name{sample_pa}
\alias{sample_pa}
\alias{pa}
\title{Generate random graphs using preferential attachment}
\usage{
sample_pa(
n,
power = 1,
m = NULL,
out.dist = NULL,
out.seq = NULL,
out.pref = FALSE,
zero.appeal = 1,
directed = TRUE,
algorithm = c("psumtree", "psumtree-multiple", "bag"),
start.graph = NULL
)
pa(...)
}
\arguments{
\item{n}{Number of vertices.}
\item{power}{The power of the preferential attachment, the default is one,
i.e. linear preferential attachment.}
\item{m}{Numeric constant, the number of edges to add in each time step This
argument is only used if both \code{out.dist} and \code{out.seq} are omitted
or NULL.}
\item{out.dist}{Numeric vector, the distribution of the number of edges to
add in each time step. This argument is only used if the \code{out.seq}
argument is omitted or NULL.}
\item{out.seq}{Numeric vector giving the number of edges to add in each time
step. Its first element is ignored as no edges are added in the first time
step.}
\item{out.pref}{Logical, if true the total degree is used for calculating
the citation probability, otherwise the in-degree is used.}
\item{zero.appeal}{The \sQuote{attractiveness} of the vertices with no
adjacent edges. See details below.}
\item{directed}{Whether to create a directed graph.}
\item{algorithm}{The algorithm to use for the graph generation.
\code{psumtree} uses a partial prefix-sum tree to generate the graph, this
algorithm can handle any \code{power} and \code{zero.appeal} values and
never generates multiple edges. \code{psumtree-multiple} also uses a
partial prefix-sum tree, but the generation of multiple edges is allowed.
Before the 0.6 version igraph used this algorithm if \code{power} was not
one, or \code{zero.appeal} was not one. \code{bag} is the algorithm that
was previously (before version 0.6) used if \code{power} was one and
\code{zero.appeal} was one as well. It works by putting the ids of the
vertices into a bag (multiset, really), exactly as many times as their
(in-)degree, plus once more. Then the required number of cited vertices are
drawn from the bag, with replacement. This method might generate multiple
edges. It only works if \code{power} and \code{zero.appeal} are equal one.}
\item{start.graph}{\code{NULL} or an igraph graph. If a graph, then the
supplied graph is used as a starting graph for the preferential attachment
algorithm. The graph should have at least one vertex. If a graph is supplied
here and the \code{out.seq} argument is not \code{NULL}, then it should
contain the out degrees of the new vertices only, not the ones in the
\code{start.graph}.}
\item{...}{Passed to \code{sample_pa()}.}
}
\value{
A graph object.
}
\description{
Preferential attachment is a family of simple stochastic algorithms for building
a graph. Variants include the Barabási-Abert model and the Price model.
}
\details{
This is a simple stochastic algorithm to generate a graph. It is a discrete
time step model and in each time step a single vertex is added.
We start with a single vertex and no edges in the first time step. Then we
add one vertex in each time step and the new vertex initiates some edges to
old vertices. The probability that an old vertex is chosen is given by
\deqn{P[i] \sim k_i^\alpha+a}{P[i] ~ k[i]^alpha + a} where \eqn{k_i}{k[i]}
is the in-degree of vertex \eqn{i} in the current time step (more precisely
the number of adjacent edges of \eqn{i} which were not initiated by \eqn{i}
itself) and \eqn{\alpha}{alpha} and \eqn{a} are parameters given by the
\code{power} and \code{zero.appeal} arguments.
The number of edges initiated in a time step is given by the \code{m},
\code{out.dist} and \code{out.seq} arguments. If \code{out.seq} is given and
not NULL then it gives the number of edges to add in a vector, the first
element is ignored, the second is the number of edges to add in the second
time step and so on. If \code{out.seq} is not given or null and
\code{out.dist} is given and not NULL then it is used as a discrete
distribution to generate the number of edges in each time step. Its first
element is the probability that no edges will be added, the second is the
probability that one edge is added, etc. (\code{out.dist} does not need to
sum up to one, it normalized automatically.) \code{out.dist} should contain
non-negative numbers and at east one element should be positive.
If both \code{out.seq} and \code{out.dist} are omitted or NULL then \code{m}
will be used, it should be a positive integer constant and \code{m} edges
will be added in each time step.
\code{sample_pa()} generates a directed graph by default, set
\code{directed} to \code{FALSE} to generate an undirected graph. Note that
even if an undirected graph is generated \eqn{k_i}{k[i]} denotes the number
of adjacent edges not initiated by the vertex itself and not the total
(in- + out-) degree of the vertex, unless the \code{out.pref} argument is set to
\code{TRUE}.
}
\examples{
g <- sample_pa(10000)
degree_distribution(g)
}
\references{
Barabási, A.-L. and Albert R. 1999. Emergence of scaling in
random networks \emph{Science}, 286 509--512.
de Solla Price, D. J. 1965. Networks of Scientific Papers \emph{Science},
149 510--515.
}
\seealso{
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_forestfire}()},
\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_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}
|
