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
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/games.R
\name{sample_degseq}
\alias{degree.sequence.game}
\alias{degseq}
\alias{sample_degseq}
\title{Generate random graphs with a given degree sequence}
\usage{
sample_degseq(out.deg, in.deg = NULL, method = c("simple", "vl",
"simple.no.multiple"))
degseq(...)
}
\arguments{
\item{out.deg}{Numeric vector, the sequence of degrees (for undirected
graphs) or out-degrees (for directed graphs). For undirected graphs its sum
should be even. For directed graphs its sum should be the same as the sum of
\code{in.deg}.}
\item{in.deg}{For directed graph, the in-degree sequence. By default this is
\code{NULL} and an undirected graph is created.}
\item{method}{Character, the method for generating the graph. Right now the
\dQuote{simple}, \dQuote{simple.no.multiple} and \dQuote{vl} methods are
implemented.}
\item{...}{Passed to \code{sample_degree}.}
}
\value{
The new graph object.
}
\description{
It is often useful to create a graph with given vertex degrees. This is
exactly what \code{sample_degseq} does.
}
\details{
The \dQuote{simple} method connects the out-stubs of the edges (undirected
graphs) or the out-stubs and in-stubs (directed graphs) together. This way
loop edges and also multiple edges may be generated. This method is not
adequate if one needs to generate simple graphs with a given degree
sequence. The multiple and loop edges can be deleted, but then the degree
sequence is distorted and there is nothing to ensure that the graphs are
sampled uniformly.
The \dQuote{simple.no.multiple} method is similar to \dQuote{simple}, but
tries to avoid multiple and loop edges and restarts the generation from
scratch if it gets stuck. It is not guaranteed to sample uniformly from the
space of all possible graphs with the given sequence, but it is relatively
fast and it will eventually succeed if the provided degree sequence is
graphical, but there is no upper bound on the number of iterations.
The \dQuote{vl} method is a more sophisticated generator. The algorithm and
the implementation was done by Fabien Viger and Matthieu Latapy. This
generator always generates undirected, connected simple graphs, it is an
error to pass the \code{in.deg} argument to it. The algorithm relies on
first creating an initial (possibly unconnected) simple undirected graph
with the given degree sequence (if this is possible at all). Then some
rewiring is done to make the graph connected. Finally a Monte-Carlo
algorithm is used to randomize the graph. The \dQuote{vl} samples from the
undirected, connected simple graphs unformly. See
\url{http://www-rp.lip6.fr/~latapy/FV/generation.html} for details.
}
\examples{
## The simple generator
g <- sample_degseq(rep(2,100))
degree(g)
is_simple(g) # sometimes TRUE, but can be FALSE
g2 <- sample_degseq(1:10, 10:1)
degree(g2, mode="out")
degree(g2, mode="in")
## The vl generator
g3 <- sample_degseq(rep(2,100), method="vl")
degree(g3)
is_simple(g3) # always TRUE
## Exponential degree distribution
## Note, that we correct the degree sequence if its sum is odd
degs <- sample(1:100, 100, replace=TRUE, prob=exp(-0.5*(1:100)))
if (sum(degs) \%\% 2 != 0) { degs[1] <- degs[1] + 1 }
g4 <- sample_degseq(degs, method="vl")
all(degree(g4) == degs)
## Power-law degree distribution
## Note, that we correct the degree sequence if its sum is odd
degs <- sample(1:100, 100, replace=TRUE, prob=(1:100)^-2)
if (sum(degs) \%\% 2 != 0) { degs[1] <- degs[1] + 1 }
g5 <- sample_degseq(degs, method="vl")
all(degree(g5) == degs)
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\seealso{
\code{\link{sample_gnp}}, \code{\link{sample_pa}},
\code{\link{simplify}} to get rid of the multiple and/or loops edges.
}
\keyword{graphs}
|
