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
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/make.R
\name{realize_degseq}
\alias{realize_degseq}
\title{Creating a graph from a given degree sequence, deterministically}
\usage{
realize_degseq(
out.deg,
in.deg = NULL,
allowed.edge.types = c("simple", "loops", "multi", "all"),
method = c("smallest", "largest", "index")
)
}
\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{allowed.edge.types}{Character, specifies the types of allowed edges.
\dQuote{simple} allows simple graphs only (no loops, no multiple edges).
\dQuote{multiple} allows multiple edges but disallows loop.
\dQuote{loops} allows loop edges but disallows multiple edges (currently
unimplemented). \dQuote{all} allows all types of edges. The default is
\dQuote{simple}.}
\item{method}{Character, the method for generating the graph; see below.}
}
\value{
The new graph object.
}
\description{
It is often useful to create a graph with given vertex degrees. This function
creates such a graph in a deterministic manner.
}
\details{
Simple undirected graphs are constructed using the Havel-Hakimi algorithm
(undirected case), or the analogous Kleitman-Wang algorithm (directed case).
These algorithms work by choosing an arbitrary vertex and connecting all its
stubs to other vertices. This step is repeated until all degrees have been
connected up.
The \sQuote{method} argument controls in which order the vertices are
selected during the course of the algorithm.
The \dQuote{smallest} method selects the vertex with the smallest remaining
degree. The result is usually a graph with high negative degree assortativity.
In the undirected case, this method is guaranteed to generate a connected
graph, regardless of whether multi-edges are allowed, provided that a
connected realization exists. See Horvát and Modes (2021) for details.
In the directed case it tends to generate weakly connected graphs, but this
is not guaranteed. This is the default method.
The \dQuote{largest} method selects the vertex with the largest remaining
degree. The result is usually a graph with high positive degree assortativity,
and is often disconnected.
The \dQuote{index} method selects the vertices in order of their index.
}
\examples{
g <- realize_degseq(rep(2, 100))
degree(g)
is_simple(g)
## Exponential degree distribution, with high positive assortativity.
## Loop and multiple edges are explicitly allowed.
## 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 <- realize_degseq(degs, method = "largest", allowed.edge.types = "all")
all(degree(g4) == degs)
## Power-law degree distribution, no loops allowed but multiple edges
## are okay.
## 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 <- realize_degseq(degs, allowed.edge.types = "multi")
all(degree(g5) == degs)
}
\references{
V. Havel,
Poznámka o existenci konečných grafů (A remark on the existence of finite graphs),
Časopis pro pěstování matematiky 80, 477-480 (1955).
https://eudml.org/doc/19050
S. L. Hakimi,
On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph,
Journal of the SIAM 10, 3 (1962).
\doi{10.1137/0111010}
D. J. Kleitman and D. L. Wang,
Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors,
Discrete Mathematics 6, 1 (1973).
\doi{10.1016/0012-365X(73)90037-X}
Sz. Horvát and C. D. Modes,
Connectedness matters: construction and exact random sampling of connected networks (2021).
\doi{10.1088/2632-072X/abced5}
}
\seealso{
\code{\link[=sample_degseq]{sample_degseq()}} for a randomized variant that samples
from graphs with the given degree sequence.
}
\keyword{graphs}
\section{Related documentation in the C library}{\href{https://igraph.org/c/html/latest/igraph-Generators.html#igraph_realize_degree_sequence}{\code{igraph_realize_degree_sequence()}}.}
|
