通常需要创建一个具有给定顶点度的图。此函数以随机方式创建这样的图。
用法
sample_degseq(
out.deg,
in.deg = NULL,
method = c("configuration", "vl", "fast.heur.simple", "configuration.simple",
"edge.switching.simple")
)
degseq(..., deterministic = FALSE)参数
- out.deg
数值向量，度的序列（对于无向图）或出度的序列（对于有向图）。对于无向图，其总和应为偶数。对于有向图，其总和应与
in.deg的总和相同。- in.deg
对于有向图，入度序列。默认情况下，此值为
NULL，并且创建无向图。- method
字符，用于生成图的方法。请参见详细信息。
- ...
如果“deterministic”为 true，则传递给
realize_degseq()；否则，传递给sample_degseq()。- deterministic
构造是否应该是确定性的
详细信息
“configuration”方法（以前称为“simple”）实现配置模型。对于无向图，它将所有顶点 ID 放入一个包中，使得包中顶点的重数与其度相同。然后，它从包中抽取配对，直到包变空。此方法可能会生成环（自）边和多重边。对于有向图，该算法基本相同，但是对于入度和出度使用两个单独的包。生成无向图的概率与 \((\prod_{i<j} A_{ij} ! \prod_i A_{ii} !!)^{-1}\) 成正比，其中 A 表示邻接矩阵，!! 表示双阶乘。此处假定 A 在其对角线上具有自环数的两倍。有向图的相应表达式为 \((\prod_{i,j} A_{ij}!)^{-1}\)。因此，所有简单图（仅在邻接矩阵中具有 0 和 1）的概率是相同的，而非简单图的概率取决于其边和自环重数。
“fast.heur.simple”方法（以前称为“simple.no.multiple”）生成简单图。它类似于“configuration”，但尝试避免多重边和环边，如果卡住则从头开始重新生成。它可以生成度序列的所有简单实现，但不保证均匀地采样它们。此方法相对较快，并且如果提供的度序列是图形化的，它最终会成功，但是迭代次数没有上限。
“configuration.simple”方法（以前称为“simple.no.multiple.uniform”）与“configuration”相同，但是如果生成的图不是简单的，则拒绝它并重新开始生成。它以相同的概率生成所有简单图。
“vl”方法近似均匀地采样无向连通图。这是一种基于度保持边交换的 Monte Carlo 方法。如果要生成无向连通图并且执行时间不是问题，则应首选此生成器。igraph 使用 Fabien Viger 的原始实现；有关该算法，请参见https://www-complexnetworks.lip6.fr/~latapy/FV/generation.html和论文https://arxiv.org/abs/cs/0502085。
“edge.switching.simple”是一种基于度保持边交换的 MCMC 采样器。它生成简单无向图或有向图。
参见
simplify() 以摆脱多重边和/或环边，realize_degseq() 以获得确定性变体。
随机图模型（博弈）bipartite_gnm(), erdos.renyi.game(), sample_(), sample_bipartite(), sample_chung_lu(), sample_correlated_gnp(), sample_correlated_gnp_pair(), sample_dot_product(), sample_fitness(), sample_fitness_pl(), sample_forestfire(), sample_gnm(), sample_gnp(), sample_grg(), sample_growing(), sample_hierarchical_sbm(), sample_islands(), sample_k_regular(), sample_last_cit(), sample_pa(), sample_pa_age(), sample_pref(), sample_sbm(), sample_smallworld(), sample_traits_callaway(), sample_tree()
作者
Gabor Csardi csardi.gabor@gmail.com
示例
## The simple generator
undirected_graph <- sample_degseq(rep(2, 100))
degree(undirected_graph)
#> [1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#> [38] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#> [75] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
is_simple(undirected_graph) # sometimes TRUE, but can be FALSE
#> [1] TRUE
directed_graph <- sample_degseq(1:10, 10:1)
degree(directed_graph, mode = "out")
#> [1] 1 2 3 4 5 6 7 8 9 10
degree(directed_graph, mode = "in")
#> [1] 10 9 8 7 6 5 4 3 2 1
## The vl generator
vl_graph <- sample_degseq(rep(2, 100), method = "vl")
degree(vl_graph)
#> [1] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#> [38] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
#> [75] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
is_simple(vl_graph) # always TRUE
#> [1] TRUE
## Exponential degree distribution
## We fix the seed as there's no guarantee
## that randomly picked integers will form a graphical degree sequence
## (i.e. that there's a graph with these degrees)
## withr::with_seed(42, {
## exponential_degrees <- sample(1:100, 100, replace = TRUE, prob = exp(-0.5 * (1:100)))
## })
exponential_degrees <- c(
5L, 6L, 1L, 4L, 3L, 2L, 3L, 1L, 3L, 3L, 2L, 3L, 6L, 1L, 2L,
6L, 8L, 1L, 2L, 2L, 5L, 1L, 10L, 6L, 1L, 2L, 1L, 5L, 2L, 4L,
3L, 4L, 1L, 3L, 1L, 4L, 1L, 1L, 5L, 2L, 1L, 2L, 1L, 8L, 2L, 7L,
5L, 3L, 8L, 2L, 1L, 1L, 2L, 4L, 1L, 3L, 3L, 1L, 1L, 2L, 3L, 9L,
3L, 2L, 4L, 1L, 1L, 4L, 3L, 1L, 1L, 1L, 1L, 2L, 1L, 3L, 1L, 1L,
2L, 1L, 2L, 1L, 1L, 3L, 3L, 2L, 1L, 1L, 1L, 1L, 3L, 1L, 1L, 6L,
6L, 3L, 1L, 2L, 3L, 2L
)
## Note, that we'd have to correct the degree sequence if its sum is odd
is_exponential_degrees_sum_odd <- (sum(exponential_degrees) %% 2 != 0)
if (is_exponential_degrees_sum_odd) {
exponential_degrees[1] <- exponential_degrees[1] + 1
}
exp_vl_graph <- sample_degseq(exponential_degrees, method = "vl")
all(degree(exp_vl_graph) == exponential_degrees)
#> [1] TRUE
## An example that does not work
if (FALSE) { # rlang::is_interactive()
## withr::with_seed(11, {
## exponential_degrees <- sample(1:100, 100, replace = TRUE, prob = exp(-0.5 * (1:100)))
## })
exponential_degrees <- c(
1L, 1L, 2L, 1L, 1L, 7L, 1L, 1L, 5L, 1L, 1L, 2L, 5L, 4L, 3L,
2L, 2L, 1L, 1L, 2L, 1L, 3L, 1L, 1L, 1L, 2L, 2L, 1L, 1L, 2L, 2L,
1L, 2L, 1L, 4L, 3L, 1L, 1L, 1L, 1L, 1L, 1L, 2L, 3L, 1L, 4L, 3L,
1L, 2L, 4L, 2L, 2L, 2L, 1L, 1L, 2L, 2L, 4L, 1L, 2L, 1L, 3L, 1L,
2L, 3L, 1L, 1L, 2L, 1L, 2L, 3L, 2L, 2L, 1L, 6L, 2L, 1L, 1L, 1L,
1L, 1L, 2L, 2L, 1L, 4L, 2L, 1L, 3L, 4L, 1L, 1L, 3L, 1L, 2L, 4L,
1L, 3L, 1L, 2L, 1L
)
## Note, that we'd have to correct the degree sequence if its sum is odd
is_exponential_degrees_sum_odd <- (sum(exponential_degrees) %% 2 != 0)
if (is_exponential_degrees_sum_odd) {
exponential_degrees[1] <- exponential_degrees[1] + 1
}
exp_vl_graph <- sample_degseq(exponential_degrees, method = "vl")
}
## Power-law degree distribution
## We fix the seed as there's no guarantee
## that randomly picked integers will form a graphical degree sequence
## (i.e. that there's a graph with these degrees)
## withr::with_seed(1, {
## powerlaw_degrees <- sample(1:100, 100, replace = TRUE, prob = (1:100)^-2)
## })
powerlaw_degrees <- c(
1L, 1L, 1L, 6L, 1L, 6L, 10L, 2L, 2L, 1L, 1L, 1L, 2L, 1L, 3L,
1L, 2L, 43L, 1L, 3L, 9L, 1L, 2L, 1L, 1L, 1L, 1L, 1L, 4L, 1L,
1L, 1L, 1L, 1L, 3L, 2L, 3L, 1L, 2L, 1L, 3L, 2L, 3L, 1L, 1L, 3L,
1L, 1L, 2L, 2L, 1L, 4L, 1L, 1L, 1L, 1L, 1L, 1L, 2L, 1L, 7L, 1L,
1L, 1L, 2L, 1L, 1L, 3L, 1L, 5L, 1L, 4L, 1L, 1L, 1L, 5L, 4L, 1L,
3L, 13L, 1L, 2L, 1L, 1L, 2L, 1L, 2L, 1L, 1L, 1L, 1L, 1L, 2L,
5L, 3L, 3L, 1L, 1L, 3L, 1L
)
## Note, that we correct the degree sequence if its sum is odd
is_exponential_degrees_sum_odd <- (sum(powerlaw_degrees) %% 2 != 0)
if (is_exponential_degrees_sum_odd) {
powerlaw_degrees[1] <- powerlaw_degrees[1] + 1
}
powerlaw_vl_graph <- sample_degseq(powerlaw_degrees, method = "vl")
all(degree(powerlaw_vl_graph) == powerlaw_degrees)
#> [1] TRUE
## An example that does not work
if (FALSE) { # rlang::is_interactive()
## withr::with_seed(2, {
## powerlaw_degrees <- sample(1:100, 100, replace = TRUE, prob = (1:100)^-2)
## })
powerlaw_degrees <- c(
1L, 2L, 1L, 1L, 10L, 10L, 1L, 4L, 1L, 1L, 1L, 1L, 2L, 1L, 1L,
4L, 21L, 1L, 1L, 1L, 2L, 1L, 4L, 1L, 1L, 1L, 1L, 1L, 14L, 1L,
1L, 1L, 3L, 4L, 1L, 2L, 4L, 1L, 2L, 1L, 25L, 1L, 1L, 1L, 10L,
3L, 19L, 1L, 1L, 3L, 1L, 1L, 2L, 8L, 1L, 3L, 3L, 36L, 2L, 2L,
3L, 5L, 2L, 1L, 4L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 2L,
1L, 4L, 1L, 1L, 1L, 2L, 1L, 1L, 1L, 4L, 18L, 1L, 2L, 1L, 21L,
1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L
)
## Note, that we correct the degree sequence if its sum is odd
is_exponential_degrees_sum_odd <- (sum(powerlaw_degrees) %% 2 != 0)
if (is_exponential_degrees_sum_odd) {
powerlaw_degrees[1] <- powerlaw_degrees[1] + 1
}
powerlaw_vl_graph <- sample_degseq(powerlaw_degrees, method = "vl")
all(degree(powerlaw_vl_graph) == powerlaw_degrees)
}